python找出最小生成树的n-1条边源代码

以下是使用Prim算法和Kruskal算法找出最小生成树的n-1条边的Python代码。

使用Prim算法：

import heapq

def prim(n, edges):
    # 初始化节点和边的信息
    graph = [[] for _ in range(n)]
    for a, b, w in edges:
        graph[a].append((b, w))
        graph[b].append((a, w))
    
    # 初始化起点和已访问的节点
    start = 0
    visited = set([start])
    
    # 初始化边的堆
    edges = graph[start]
    heapq.heapify(edges)
    
    # 初始化最小生成树的边集合和权值
    mst_edges = []
    mst_weight = 0
    
    # 执行Prim算法
    while len(mst_edges) < n - 1:
        # 从堆中取出距离当前集合最近的边
        w, u = heapq.heappop(edges)
        if u not in visited:
            # 将该边加入到最小生成树的边集合中
            mst_edges.append((u, w))
            mst_weight += w
            
            # 将该节点加入到已访问的节点中，并将其相邻的边加入到堆中
            visited.add(u)
            for v, w in graph[u]:
                if v not in visited:
                    heapq.heappush(edges, (w, v))
    
    return mst_edges, mst_weight

使用Kruskal算法：

def kruskal(n, edges):
    # 初始化父节点
    parent = [i for i in range(n)]
    
    # 定义并查集的操作
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
    
    # 对边按照权值从小到大排序
    edges.sort(key=lambda x: x[2])
    
    # 初始化最小生成树的边集合和权值
    mst_edges = []
    mst_weight = 0
    
    # 执行Kruskal算法
    for a, b, w in edges:
        if find(a) != find(b):
            # 如果该边的两个端点不在同一个连通分量中，就将其加入到最小生成树的边集合中
            mst_edges.append((a, b, w))
            mst_weight += w
            union(a, b)
            if len(mst_edges) == n - 1:
                break
    
    return mst_edges, mst_weight

以上代码中，n表示节点的数量，edges是一个列表，其中每个元素是一个三元组(a, b, w)，表示节点a和节点b之间有一条权值为w的边。mst_edges是最小生成树的边集合，mst_weight是最小生成树的权值。