分别使用Prim算法和Kruskal算法求连通图的最小生成树。

### Prim算法与Kruskal算法的实现及区别 #### 实现方法 Prim算法的核心是从某一个起点出发，逐步扩展已有的最小生成树。它通过维护一个候选边集合，在每一步中选择权值最小的边加入当前的生成树，同时确保不会形成环路。这种方法适合于稠密图，因为它的复杂度主要依赖于顶点数而非边数。 ```python import sys def prim(graph, start): n = len(graph) visited = [False] * n key = [sys.maxsize] * n parent = [-1] * n key[start] = 0 for _ in range(n): u = min_key(key, visited) visited[u] = True for v in range(n): if graph[u][v] and not visited[v] and graph[u][v] < key[v]: key[v] = graph[u][v] parent[v] = u result = [] for i in range(1, n): result.append((parent[i], i, graph[parent[i]][i])) return result def min_key(key, visited): min_val = sys.maxsize min_index = -1 for v in range(len(key)): if not visited[v] and key[v] < min_val: min_val = key[v] min_index = v return min_index ``` Kruskal算法则是基于边的操作，先将所有的边按照其权重升序排列，然后逐一挑选最短的边，只要该边不构成回路即可被纳入最终的最小生成树之中。此过程可以借助并查集数据结构来高效判断新加入的边是否会引发循环问题。这种策略更适合稀疏图的应用场景。 ```python class UnionFind: def __init__(self, size): self.parent = list(range(size)) def find(self, node): while self.parent[node] != node: node = self.parent[node] return node def union_set(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.parent[rootY] = rootX def kruskal(edges, num_nodes): edges.sort(key=lambda edge: edge[2]) uf = UnionFind(num_nodes) mst = [] for edge in edges: src, dest, weight = edge if uf.find(src) != uf.find(dest): uf.union_set(src, dest) mst.append(edge) return mst ``` [^1] #### 主要差异 两种算法的主要差别体现在以下几个方面： - **适用范围**：Prim算法更适用于密集型网络（即具有较多边的情况），而Kruskal则倾向于处理较为松散或者大型但连接较少的数据结构。 - **时间效率**：假设输入图为G=(V,E)，其中|V|=n且|E|=m，则Prim的时间复杂度通常为O(n²)[^2]，如果使用二叉堆优化可降至O(m log n); Kruskal由于涉及排序操作以及后续多次查找合并操作，整体性能大约处于O(m log m)=O(m log n)[^3]. - **空间需求**：相对而言，Kruskal可能需要额外存储整个边上信息的空间开销较大一些；相比之下，Prim只需要记录邻接矩阵或列表形式下的局部更新情况就够了。 - **逻辑流程上的不同之处在于起始条件的选择方式及其迭代过程中关于节点间关系判定的具体手段有所区分。** [^2]