Python 中最小生成树问题的贪心解法
最小生成树问题是指，在一个带权无向连通图中，找到一颗生成树，
使得树上所有边的权值之和最小。其中，生成树是指保留所有节点，但只保留足以连通所有节点的边的树。
贪心算法是解决最小生成树问题的一个有效方法，下面给出详细的贪心算法介绍和代码演示。
- Kruskal 算法
Kruskal 算法是目前最常用的最小生成树算法之一，它的核心思路是将边按照权值从小到大进行排序，
然后依次寻找最小生成树上的边。
具体流程如下：
（1）将图中的所有边按照权值从小到大排序；
（2）依次取出排完序后的边，如果该边的两个端点不在同一个连通块中，就将它们合并到同一个连通块中，并把该边加入最小生成树中。
（3）重复上述步骤，直到找到 n-1 条边为止或者所有的边都已被考虑完毕。
代码实现如下：
class UnionFindSet: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root, y_root = self.find(x), self.find(y) if x_root == y_root: return False if self.rank[x_root] > self.rank[y_root]: self.parent[y_root] = x_root elif self.rank[x_root] < self.rank[y_root]: self.parent[x_root] = y_root else: self.parent[y_root] = x_root self.rank[x_root] += 1 return True class Kruskal: def __init__(self, n, edges): self.ufs = UnionFindSet(n) self.edges = edges def min_spanning_tree(self): mst = [] self.edges.sort(key=lambda e: e[2]) for e in self.edges: if self.ufs.union(e[0], e[1]): mst.append(e) if len(mst) == n - 1: break return mst
其中，UnionFindSet 是并查集，Kruskal 是主程序。
下面用一个简单的例子来说明 Kruskal 算法的实现：
假设我们有如下的图：
A -----2---- B | \ | 1 5 4 | \ | C----- 3---- D
我们将每条边表示成一个元组 (u, v, w)，其中 u、v 分别代表边的两个端点，w 表示边的权值。
edges = [(0, 1, 2), (0, 2, 1), (0, 3, 5), (1, 3, 4), (2, 3, 3)]
然后，我们创建 Kruskal 类并初始化。
kruskal = Kruskal(4, edges)
接下来调用 min_spanning_tree 方法即可得到最小生成树。
mst = kruskal.min_spanning_tree() print(mst) # 输出 [(0, 2, 1), (0, 1, 2), (2, 3, 3)]
- Prim 算法
Prim 算法也是一种常用的最小生成树算法，它的核心思想是将已经构建好的树向外扩展，
每次加进去一条到树中距离最短的边，直到整张图连接起来。
具体流程如下：
（1）任选一个节点作为初始节点，并将其加入到已构建好的树中；
（2）找出所有连接已构建好的树和未加入树中节点的边，并选取其中权重最小的边作为新的树边。
（3）将新的树边连接到树中，并将新加入的节点加入到已构建好的树中。
（4）重复步骤 (2) 和 (3)，直到所有节点都被加入到树中为止。
代码实现如下：
class Prim: def __init__(self, n, edges): self.n = n self.edges = edges self.adj = [[] for _ in range(n)] for u, v, w in edges: self.adj[u].append((v, w)) self.adj[v].append((u, w)) def min_spanning_tree(self): mst = [] visited = [False] * self.n heap = [(0, 0)] # 在堆中维护 (dist, node) 这样的元组 while heap: dist, node = heappop(heap) if visited[node]: continue visited[node] = True if node != 0: mst.append((parent, node, dist)) for child, weight in self.adj[node]: if not visited[child]: heappush(heap, (weight, child)) heapify(heap) return mst
其中，Prim 是主程序。
下面同样用一个简单的例子来说明 Prim 算法的实现：
假设我们有如下的图：
A -----2---- B | \ | 1 5 4 | \ | C----- 3---- D
我们将每条边表示成一个元组 (u, v, w)，其中 u、v 分别代表边的两个端点，w 表示边的权值。
edges = [(0, 1, 2), (0, 2, 1), (0, 3, 5), (1, 3, 4), (2, 3, 3)]
然后创建 Prim 类并初始化。
prim = Prim(4, edges)
接下来调用 min_spanning_tree 方法即可得到最小生成树。
mst = prim.min_spanning_tree() print(mst) # 输出 [(0, 2, 1), (2, 3, 3), (0, 1, 2)]
相关文章