Python实现：基于不相交集数据结构的Kruskal算法课程实验

Sure! Here's an example implementation of Kruskal's algorithm using a disjoint-set data structure in Python: ```python class DisjointSet: def __init__(self, size): self.parent = [i for i in range(size)] self.rank = [0] * size 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): root1 = self.find(u) root2 = self.find(v) if self.rank[root1] < self.rank[root2]: self.parent[root1] = root2 elif self.rank[root1] > self.rank[root2]: self.parent[root2] = root1 else: self.parent[root2] = root1 self.rank[root1] += 1 def sortededges(vertices, edges): edges.sort(key=lambda x: x[2]) # Sort edges by weight in ascending order mst = [] ds = DisjointSet(vertices) # Create a disjoint-set data structure for u, v, weight in edges: if ds.find(u) != ds.find(v): # Check if adding the edge creates a cycle mst.append((u, v, weight)) # Add the edge to the minimum spanning tree ds.union(u, v) # Merge the sets of u and v return mst ``` To use this implementation, you need to provide the number of vertices (`vertices`) and a list of edges (`edges`), where each edge is represented as a tuple `(u, v, weight)`. Please note that this is a basic implementation and there are alternative ways to implement a disjoint-set data structure. Depending on your specific requirements and constraints, you may need to make modifications to the code. ######[AI写代码神器 | 1636点数解答 | 2023-12-29 16:57:35]