Python实现Kruskal算法：基于不相交集数据结构的最小生成树求解

Here's an implementation of Kruskal's algorithm using a disjoint-set data structure implemented with trees in Python: ```python class DisjointSet: def __init__(self, vertices): self.rank = {u: 0 for u in vertices} self.parent = {u: u for u in vertices} def find(self, u): if self.parent[u] != u: self.parent[u] = self.find(self.parent[u]) return self.parent[u] def union(self, u, v): root_u = self.find(u) root_v = self.find(v) if root_u != root_v: if self.rank[root_u] < self.rank[root_v]: self.parent[root_u] = root_v else: self.parent[root_v] = root_u if self.rank[root_u] == self.rank[root_v]: self.rank[root_u] += 1 def makeset(self, u): self.rank[u] = 0 self.parent[u] = u def sortededges(graph): edges = [(weight, u, v) for u, connections in graph.items() for v, weight in connections.items()] edges.sort() mst = [] ds = DisjointSet(list(graph.keys())) for weight, u, v in edges: root_u = ds.find(u) root_v = ds.find(v) if root_u != root_v: mst.append((weight, u, v)) ds.union(u, v) return mst # Example usage: graph = { 'A': {'B': 7, 'D': 5}, 'B': {'A': 7, 'C': 8, 'D': 9}, 'C': {'B': 8, 'D': 15, 'E': 10}, 'D': {'A': 5, 'B': 9, 'C': 15, 'E': 6}, 'E': {'C': 10, 'D': 6}, } mst = sortededges(graph) print("Minimum Spanning Tree edges:", mst) ``` This code defines a `DisjointSet` class that implements the required operations (`makeset`, `find`, and `union`) using trees. The `sortededges` function takes a graph represented as a dictionary and returns the edges of the minimum spanning tree using Kruskal's algorithm. In this implementation, the graph is assumed to be undirected. ######[AI写代码神器 | 531点数解答 | 2023-12-29 16:59:27]