python实现最小生成树算法输出最小生成树的边数并给出示例输入和输出

最小生成树算法有多种，常见的有Prim算法和Kruskal算法。这里给出Prim算法的实现，并输出最小生成树的边数。

示例输入：

7 12
0 1 2
1 2 4
2 3 5
3 4 6
4 5 8
5 6 9
6 0 11
0 2 3
1 3 7
2 4 8
3 5 10
4 6 12

其中第一行的两个数字表示节点数和边数，后面的每一行表示一条边，依次为起点、终点和边权重。

示例输出：

11

下面是Python实现Prim算法的代码：

import heapq

def prim(n, edges):
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((w, v))
        graph[v].append((w, u))

    mst = []
    visited = [False] * n
    visited[0] = True
    heap = graph[0][:]  # 将节点0的所有边加入堆中
    heapq.heapify(heap)

    while heap:
        w, v = heapq.heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        mst.append((v, w))
        for edge in graph[v]:
            if not visited[edge[1]]:
                heapq.heappush(heap, edge)

    return sum([edge[1] for edge in mst])

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
print(prim(n, edges))

在本例中，Prim算法的时间复杂度为$O(m\log n)$，其中m为边数，n为节点数。