最小生成树实现

最小生成树（Minimum Spanning Tree，MST）是一种在加权无向图中找到一棵包含所有节点的树，并且边的权值之和最小的树。

常见的实现算法有Prim算法和Kruskal算法。

Prim算法：
1. 选定一个起点，将其加入集合U中
2. 遍历U中节点的所有邻居节点，将其与U中的节点建立边，并记录边的权值
3. 从权值最小的边所连接的节点中选定一个未加入U集合的节点，将其加入U集合中，重复2和3直到图中所有节点都被加入U集合中
4. 所有被加入U集合中的边就是最小生成树

Kruskal算法：
1. 将所有边按照权值从小到大排列
2. 遍历所有边，如果边的两个节点不在同一个集合中，则将它们所在的集合合并，并将这条边加入最小生成树中
3. 重复2直到所有节点都在同一个集合中

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

def prim(graph, start):
    n = len(graph)
    visited = [False] * n
    visited[start] = True
    edges = []
    for i in range(n - 1):
        min_weight = float('inf')
        min_edge = None
        for u in range(n):
            if visited[u]:
                for v in range(n):
                    if not visited[v] and graph[u][v] < min_weight:
                        min_weight = graph[u][v]
                        min_edge = (u, v)
        edges.append(min_edge)
        visited[min_edge[1]] = True
    return edges

其中graph是邻接矩阵表示的图，start是起点。函数返回最小生成树的边列表。