最小生成树解题模板

### 关于最小生成树算法的解题模板 #### Kruskal 算法示例代码 Kruskal 算法的核心思想是通过不断选取权重最小的边来构建最小生成树，同时确保不会形成环路。以下是基于并查集实现的 Kruskal 算法模板： ```python class UnionFind: def __init__(self, n): self.parent = list(range(n)) def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.parent[rootY] = rootX def kruskal(edges, n): edges.sort(key=lambda edge: edge[2]) # 按照权重从小到大排序 uf = UnionFind(n) mst_weight = 0 mst_edges = [] for u, v, w in edges: if uf.find(u) != uf.find(v): # 如果两个节点不在同一个连通分量中 uf.union(u, v) mst_weight += w mst_edges.append((u, v, w)) if len(mst_edges) != n - 1: # 判断是否构成一棵生成树 return None return mst_edges, mst_weight ``` 上述代码实现了 Kruska 算法的基础逻辑[^2]。 --- #### Prim 算法示例代码 Prim 算法则采用贪心策略逐步扩展已有的生成树集合。以下是基于邻接矩阵实现的 Prim 算法模板： ```python import heapq def prim(graph, start=0): n = len(graph) visited = [False] * n min_heap = [(0, start)] # (weight, node) mst_weight = 0 mst_edges = [] while min_heap: weight, u = heapq.heappop(min_heap) if visited[u]: continue visited[u] = True mst_weight += weight for v, w in enumerate(graph[u]): if not visited[v] and w > 0: heapq.heappush(min_heap, (w, v)) mst_edges.append((u, v, w)) if sum(visited) != n: # 判断是否所有节点都被访问过 return None return mst_edges, mst_weight ``` 此代码展示了如何利用堆优化的方式加速 Prim 算法的执行效率[^1]。 --- #### 示例应用 假设有一个无向加权图表示如下（邻接表形式），可以通过调用以上函数解决最小生成树问题： 输入样例： ```plaintext edges = [ (0, 1, 7), (0, 3, 5), (1, 2, 8), (1, 3, 9), (2, 3, 7), (2, 4, 5), (3, 4, 15), (3, 5, 6), (4, 5, 8), (4, 6, 9), (5, 6, 11) ] n = 7 # 节点数 m = len(edges) # 边数 ``` 运行 `kruskal(edges, n)` 或者将 `graph` 构建为邻接矩阵后运行 `prim(graph)` 即可得到对应的最小生成树及其总权重[^3]。 ---