[教程]Python求解最小生成树：掌握Kruskal算法与Prim算法，轻松构建无向图最优连接

引言最小生成树（Minimum Spanning Tree，MST）是图论中的一个重要概念，它用于寻找一个无向连通加权图的最小生成树。最小生成树包含图中的所有顶点，并且所有边的权重之和尽可能小。在许多...

引言

最小生成树（Minimum Spanning Tree，MST）是图论中的一个重要概念，它用于寻找一个无向连通加权图的最小生成树。最小生成树包含图中的所有顶点，并且所有边的权重之和尽可能小。在许多实际应用中，如网络设计、电路设计、城市交通规划等，最小生成树问题都具有重要意义。

Python作为一种功能强大的编程语言，提供了多种方法来求解最小生成树问题。本文将详细介绍两种经典算法：Kruskal算法和Prim算法，并展示如何在Python中实现它们。

Kruskal算法

Kruskal算法是一种基于贪心策略的算法，其基本思想是按照边的权重从小到大排序，然后逐条选取边，确保每条边都不会形成环。以下是Kruskal算法的步骤：

1. 将所有边按照权重从小到大排序。
2. 初始化一个空的最小生成树T。
3. 遍历排序后的边，对于每条边：
   • 如果这条边连接的两个顶点不在T中，则将其添加到T中。
   • 如果这条边连接的两个顶点已经在T中，则跳过这条边。
4. 重复步骤3，直到T中包含所有顶点。

Kruskal算法Python实现

import heapq
class Graph: def __init__(self, vertices): self.V = vertices self.graph = [] def add_edge(self, u, v, w): self.graph.append([u, v, w]) def find(self, parent, i): if parent[i] == i: return i return self.find(parent, parent[i]) def union(self, parent, rank, x, y): rootx = self.find(parent, x) rooty = self.find(parent, y) if rank[rootx] < rank[rooty]: parent[rootx] = rooty elif rank[rootx] > rank[rooty]: parent[rooty] = rootx else: parent[rooty] = rootx rank[rootx] += 1 def kruskal_mst(self): result = [] i, e = 0, 0 self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] for node in range(self.V): parent.append(node) rank.append(0) while e < self.V - 1: u, v, w = self.graph[i] i = i + 1 x = self.find(parent, u) y = self.find(parent, v) if x != y: e = e + 1 result.append([u, v, w]) self.union(parent, rank, x, y) return result
# 示例
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)
mst = g.kruskal_mst()
print("Edge \tWeight")
for u, v, weight in mst: print(f"{u} - {v}\t{weight}")

Prim算法

Prim算法也是一种基于贪心策略的算法，其基本思想是从某个顶点开始，不断选择与当前生成树相连的最小权值的边，将其对应的顶点加入到生成树中。以下是Prim算法的步骤：

1. 选择一个顶点作为起始点，并将其加入生成树T。
2. 对于T中的每个顶点v，计算v到T中其他顶点的最小边权值。
3. 选择一个最小边权值，将其对应的边和顶点加入到T中。
4. 重复步骤2和3，直到T中包含所有顶点。

Prim算法Python实现

import heapq
class Graph: def __init__(self, vertices): self.V = vertices self.graph = [] def add_edge(self, u, v, w): self.graph.append([u, v, w]) def prim_mst(self): result = [] visited = [False] * self.V min_heap = [(0, 0)] # (weight, vertex) total_weight = 0 while min_heap: weight, vertex = heapq.heappop(min_heap) if visited[vertex]: continue visited[vertex] = True total_weight += weight result.append((vertex, weight)) for u, v, w in self.graph: if u == vertex and not visited[v]: heapq.heappush(min_heap, (w, v)) return result, total_weight
# 示例
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)
mst, total_weight = g.prim_mst()
print("Edge \tWeight")
for u, weight in mst: print(f"{u} - {u}\t{weight}")
print(f"Total weight: {total_weight}")

总结

本文介绍了两种经典的最小生成树算法：Kruskal算法和Prim算法，并展示了如何在Python中实现它们。通过掌握这两种算法，我们可以轻松构建无向图的最优连接，为解决实际问题提供有力支持。