### Kruskal算法的Python实现 Kruskal算法是一种用于寻找图中最小生成树的有效算法。该算法基于贪婪策略，逐步选择权重最小的边加入到生成树集合中，前提是这些边不会形成环路[^1]。 以下是Kruskal算法的一个标准Python实现： #### 实现代码 ```python class Graph: def __init__(self, vertices): self.V = vertices # Number of vertices self.graph = [] # Default dictionary to store graph # Function to add an edge to the graph def add_edge(self, u, v, w): self.graph.append([u, v, w]) # A utility function to find the parent of a node using path compression def find_parent(self, parent, i): if parent[i] == i: return i return self.find_parent(parent, parent[i]) # A function that does union of two sets by rank def union(self, parent, rank, x, y): root_x = self.find_parent(parent, x) root_y = self.find_parent(parent, y) if rank[root_x] < rank[root_y]: parent[root_x] = root_y elif rank[root_x] > rank[root_y]: parent[root_y] = root_x else: parent[root_y] = root_x rank[root_x] += 1 # The main function to construct MST using Kruskal's algorithm def kruskal_mst(self): result = [] # This will store the resultant MST i = 0 # An index variable, used for sorted edges e = 0 # An index variable, used for result[] # Step 1: Sort all the edges in non-decreasing order of their weight. self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Create V subsets with single elements for node in range(self.V): parent.append(node) rank.append(0) # Number of edges to be taken is equal to V-1 while e < self.V - 1 and i < len(self.graph): # Step 2: Pick the smallest edge and increment the index for next iteration u, v, w = self.graph[i] i += 1 x = self.find_parent(parent, u) y = self.find_parent(parent, v) # If including this edge doesn't cause cycle, include it in result and increment the index of result # for next edge if x != y: e += 1 result.append([u, v, w]) self.union(parent, rank, x, y) # Print the contents of result[] min_cost = 0 for u, v, weight in result: min_cost += weight print(f"{u} -- {v} == {weight}") print(f"Minimum Cost Spanning Tree: {min_cost}") # Example usage g = Graph(4) g.add_edge(0, 1, 10) g.add_edge(0, 2, 6) g.add_edge(0, 3, 5) g.add_edge(1, 3, 15) g.add_edge(2, 3, 4) print("Edges in the constructed MST:") g.kruskal_mst() ``` 上述代码实现了Kruskal算法的核心逻辑，包括按权重排序边、检测并避免环路以及构建最终的最小生成树。 --- ### 关键概念解释 1. **路径压缩优化**: `find_parent` 函数采用了路径压缩技术，使得查找操作的时间复杂度接近常数时间 \(O(\alpha(V))\) ，其中 \(\alpha\) 是反阿克曼函数[^2]。 2. **按秩合并**: 在执行联合操作时，优先将较小的子集连接到较大的子集中，从而减少树的高度，提高效率[^3]。 3. **贪婪选择原则**: 每次选取当前可用的最短边，只要这条边不构成回路就将其纳入生成树集合中[^4]。 --- ### 输出示例 对于上面的例子，程序会输出如下内容： ``` Edges in the constructed MST: 0 -- 3 == 5 2 -- 3 == 4 0 -- 1 == 10 Minimum Cost Spanning Tree: 19 ``` 这表明最小生成树由三条边组成，总权值为19。 ---