生成树算法python

### 关于生成树算法的 Python 实现 #### Prim 算法 Prim 算法是一种用于寻找加权连通图中的最小生成树的经典方法。其核心思想是从任意顶点出发，逐步扩展到其他顶点，直到覆盖整个图。 以下是基于优先队列优化版本的 Prim 算法实现： ```python import heapq def prim(graph, start_vertex): visited = set() min_heap = [(0, start_vertex)] mst_cost = 0 mst_edges = [] while min_heap: weight, current_vertex = heapq.heappop(min_heap) if current_vertex in visited: continue visited.add(current_vertex) mst_cost += weight for neighbor, edge_weight in graph[current_vertex]: if neighbor not in visited: heapq.heappush(min_heap, (edge_weight, neighbor)) mst_edges.append((current_vertex, weight)) return mst_cost, mst_edges[:-1] # 示例输入 graph = { 'A': [('B', 1), ('C', 4)], 'B': [('A', 1), ('C', 2), ('D', 5)], 'C': [('A', 4), ('B', 2), ('D', 1)], 'D': [('B', 5), ('C', 1)] } mst_cost, mst_edges = prim(graph, 'A') print(f"Minimum Spanning Tree Cost: {mst_cost}") print("Edges:", mst_edges) ``` 上述代码实现了带权重无向图上的 Prim 算法[^1]。 --- #### Kruskal 算法 Kruskal 算法通过按边权重升序排列并逐一加入集合来构建最小生成树，同时利用不相交集（Union-Find）数据结构检测环路。 下面是 Kruskal 算法的一个典型实现： ```python class UnionFind: def __init__(self, vertices): self.parent = {v: v for v in vertices} def find(self, vertex): if self.parent[vertex] != vertex: self.parent[vertex] = self.find(self.parent[vertex]) return self.parent[vertex] def union(self, u, v): root_u = self.find(u) root_v = self.find(v) if root_u != root_v: self.parent[root_v] = root_u def kruskal(edges, vertices): edges.sort(key=lambda x: x[2]) # Sort by weight uf = UnionFind(vertices) mst_cost = 0 mst_edges = [] for u, v, w in edges: if uf.find(u) != uf.find(v): uf.union(u, v) mst_cost += w mst_edges.append((u, v, w)) return mst_cost, mst_edges # 示例输入 edges = [ ('A', 'B', 1), ('A', 'C', 4), ('B', 'C', 2), ('B', 'D', 5), ('C', 'D', 1) ] vertices = ['A', 'B', 'C', 'D'] mst_cost, mst_edges = kruskal(edges, vertices) print(f"Minimum Spanning Tree Cost: {mst_cost}") print("Edges:", mst_edges) ``` 此代码展示了如何使用 Kruska 算法找到给定图的最小生成树。 --- #### 总结 两种算法各有优劣： - **Prim 算法**更适合稠密图，因为它的时间复杂度主要依赖于节点数 \(O(V^2)\)，而堆优化可以降低至 \(O(E \log V)\)。 - **Kruskal 算法**则适用于稀疏图，时间复杂度为 \(O(E \log E)\)。 尽管两者都能有效解决问题，但在实际应用中需根据具体场景选择合适的算法。 ---