最小生成树python写法

### 使用Python实现最小生成树算法 #### Kruskal算法 Kruskal算法通过逐步加入边来构建最小生成树，每次选择当前可用的最短边，只要这条边不会形成环路。该过程持续到所有的节点都被连接起来。 ```python def find(parent, i): if parent[i] == i: return i return find(parent, parent[i]) def union(parent, rank, x, y): root_x = find(parent, x) root_y = find(parent, y) if root_x != root_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 def kruskal_algorithm(graph): result = [] index, edges = 0, 0 graph = sorted(graph, key=lambda item: item[2]) parent = []; rank = [] for node in range(len(graph)): parent.append(node) rank.append(0) while edges < len(graph) - 1 and index < len(graph): u, v, w = graph[index] index = index + 1 x = find(parent, u) y = find(parent ,v) if x != y: edges = edges + 1 result.append([u, v, w]) union(parent, rank, x, y) minimumCost = 0 for u, v, weight in result: minimumCost += weight print(f"{u} -- {v} == {weight}") print("Minimum Spanning Tree", minimumCost) ``` 此段代码展示了如何利用Kruskal算法找到给定图中的最小生成树[^1]。 #### Prim算法 Prim算法从任意一个顶点开始，逐渐扩展已有的部分生成树直到覆盖所有顶点。每一步都添加一条能够使得新旧两部分相连且权值最小的边进入现有集合中。 ```python import sys import heapq def prim_algorithm(graph, start_vertex=0): mst = set() edges = [(0, start_vertex, None)] min_span_tree = [] total_weight = 0 while edges: weight, vertex_u, vertex_v = heapq.heappop(edges) if vertex_u not in mst or vertex_v not in mst: if vertex_v is not None: min_span_tree.append((vertex_u, vertex_v)) total_weight += weight if vertex_u not in mst: mst.add(vertex_u) for edge in graph[vertex_u]: adjacent_node, cost = edge heapq.heappush(edges, (cost, adjacent_node, vertex_u)) if vertex_v not in mst: mst.add(vertex_v) for edge in graph[vertex_v]: adjacent_node, cost = edge heapq.heappush(edges, (cost, adjacent_node, vertex_v)) print(min_span_tree) print(total_weight) ``` 这段程序实现了基于优先队列优化版本的Prim算法用于计算加权无向图上的最小生成树[^3]。