### 使用 Python 实现 Kruskal 算法计算最小生成树 Kruskal 算法是一种用于求解图的最小生成树的经典算法。其核心思想是从所有边中按权值从小到大依次选取，通过并查集检测是否存在环路来决定是否加入当前边至最小生成树中[^2]。 以下是基于上述描述的具体实现方法： #### 1. 并查集（Union-Find）结构 为了高效地判断新加入的边是否会形成环路，通常采用并查集数据结构。该结构支持两种操作：`find` 和 `union`。其中，`find` 用来查询某个顶点所属的集合编号；`union` 则将两个不同的集合合并为一个集合。 ```python class UnionFind: def __init__(self, n): self.parent = list(range(n)) def find(self, u): while u != self.parent[u]: self.parent[u] = self.parent[self.parent[u]] # 路径压缩优化 u = self.parent[u] return u def union(self, u, v): root_u = self.find(u) root_v = self.find(v) if root_u != root_v: self.parent[root_u] = root_v return True return False ``` #### 2. 边的数据表示 每条边可以用三元组 `(weight, node1, node2)` 表示，分别代表边的权重以及它所连接的两个节点。 #### 3. 主体逻辑 先对所有的边按照权重升序排列，随后逐一尝试将其纳入最小生成树中。如果某条边不会造成循环，则将其保留下来，并更新总代价；反之则舍弃之。当成功添加了 \(n-1\) 条有效边之后即可终止程序运行。 ```python def kruskal(edges, num_nodes): edges.sort(key=lambda edge: edge[0]) # 按照权重排序 uf = UnionFind(num_nodes) mst_cost = 0 mst_edges = [] for weight, u, v in edges: if uf.union(u, v): # 如果不构成环路 mst_cost += weight mst_edges.append((u, v)) if len(mst_edges) == num_nodes - 1: return (mst_cost, mst_edges) else: raise ValueError("The graph is not connected.") # 图不是连通的情况处理 ``` 以上即为完整的 Kruska l算法 python 实现过程[^3]。 #### 测试案例 下面给出一段测试代码展示如何调用上面定义好的函数完成实际问题解决。 ```python if __name__ == "__main__": # 定义一些样例输入 example_edges = [ (7, 'A', 'B'), (5, 'A', 'D'), (9, 'B', 'C'), (8, 'B', 'D'), (7, 'B', 'E'), (5, 'C', 'E'), (15,'D','E'), (6, 'D','F'), (8, 'E','F'), (9, 'E','G'), (11,'F','G') ] nodes_set = set() for _, u, v in example_edges: nodes_set.add(u) nodes_set.add(v) mapping = {node:i for i,node in enumerate(nodes_set)} mapped_edges = [(w,mapping[u],mapping[v]) for w,u,v in example_edges] cost, selected_edges = kruskal(mapped_edges, len(mapping)) print(f"Total Cost of MST: {cost}") print("Edges included:") for e in selected_edges: print(f"{list(mapping.keys())[e[0]]} -- {list(mapping.keys())[e[1]]}") ```