计算带权无向图的最小生成树

带权无向图的最小生成树可以使用 Kruskal 算法或 Prim 算法来计算。

Kruskal 算法的基本思想是先将所有边按权值从小到大排序，然后逐步将边加入最小生成树中，如果加入某条边会形成环，则不加入该边。具体实现中，可以使用并查集来判断是否形成环。

Prim 算法的基本思想是从一个任意节点开始，逐步扩展生成树，每次将与当前最小生成树相邻的权值最小的边加入最小生成树，直到所有的节点都被加入为止。具体实现中，可以使用堆来维护当前与 MST 相邻的边中权值最小的边。

两种算法的时间复杂度均为 O(E log E) 或 O(E log V)，其中 E 表示边数，V 表示节点数。具体选择哪种算法可以根据实际情况进行决定。

下面是使用 Prim 算法计算带权无向图最小生成树的代码示例：

import heapq

def prim(graph):
    n = len(graph)
    visited = [False] * n
    mst = []
    heap = []
    
    # 从节点0开始，将其加入最小生成树集合
    visited[0] = True
    for j in range(n):
        if graph[0][j] != 0:
            heapq.heappush(heap, (graph[0][j], 0, j))
    
    # 遍历所有节点
    while len(mst) < n-1 and heap:
        # 找到当前最小边
        w, u, v = heapq.heappop(heap)
        if visited[u] and visited[v]:
            continue
        # 将其加入最小生成树
        mst.append((u, v, w))
        # 将与新节点相邻的边加入堆中
        if not visited[u]:
            visited[u] = True
            for j in range(n):
                if graph[u][j] != 0:
                    heapq.heappush(heap, (graph[u][j], u, j))
        if not visited[v]:
            visited[v] = True
            for j in range(n):
                if graph[v][j] != 0:
                    heapq.heappush(heap, (graph[v][j], v, j))
    
    return mst

在这段代码中，我们使用了 Python 内置的 heapq 模块来实现堆的功能，其中 heap 列表用于存储当前与最小生成树相邻的边。在遍历过程中，我们不断从 heap 中取出权值最小的边，将其加入最小生成树中，并将其相邻的边加入 heap 中。在加入新的边时，我们需要判断其连接的两个节点是否已经在最小生成树集合中，以避免出现环的情况。

希望对你有所帮助！