6 Kruskal和Prim算法

在前一篇文章中，我们深入探讨了图的高级算法中的最短路径算法，包括 Dijkstra 算法和 Floyd 算法。这些算法为我们解决图中的最短路径问题提供了强大的工具。本篇教程则将重点介绍“最小生成树”问题，具体来说，我们将探讨两种著名的算法——Kruskal 算法和 Prim 算法，帮助我们计算一个带权无向图的最小生成树。

什么是最小生成树？

最小生成树（Minimum Spanning Tree, MST）是一个无向图的生成树，它包含了图中所有的顶点，并且边的总权重最小。在一些网络设计问题中，找到最小生成树可以帮助我们以最小的成本连接所有节点。

示例图

考虑一个带权无向图如下所示：

  A
 /|\
4 | 6
 / | \
B--2--C
|\   /|
1| 5 |3
 |/   |
 D----E
     7

在这个图中，边的权重依次为：

• AB: 4
• AC: 6
• BC: 2
• BD: 1
• CE: 3
• DE: 7

我们希望找到一棵包含所有节点的树，并使得树中边的权重和最小。

Kruskal 算法

Kruskal 算法是一种贪心算法，其工作原理为：每次选择权重最小的边，前提是不形成环，直到连接所有顶点。

Kruskal 算法步骤

1. 初始化：将所有边按权重从小到大排序。
2. 选择边：逐一选择边，如果选择的边不会形成环，则将其加入生成树中。
3. 停止条件：当生成树中的边数量达到顶点数量减一时，停止。

示例实现

我们可以用以下 Python 代码来实现 Kruskal 算法：

class DisjointSet:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

    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):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            else:
                self.parent[root_u] = root_v
                if self.rank[root_u] == self.rank[root_v]:
                    self.rank[root_v] += 1

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])  # 按权重排序
    ds = DisjointSet(n)
    mst = []
    total_weight = 0
    
    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):  # 判断是否在同一集合
            ds.union(u, v)
            mst.append((u, v, weight))
            total_weight += weight
    
    return mst, total_weight

# 示例边
edges = [(0, 1, 4), (0, 2, 6), (1, 2, 2), (1, 3, 1), (2, 4, 3), (3, 4, 7)]
mst, total_weight = kruskal(edges, 5)
print("最小生成树边:", mst)
print("总权重:", total_weight)

Prim 算法

Prim 算法也是一种贪心算法，与 Kruskal 算法不同的是，Prim 算法从一个顶点开始，不断地扩展生成树，选择与当前树相连的权重最小的边。

Prim 算法步骤

1. 初始化：选择一个起始顶点，将其标记，并将与其相连的边加入最小边集合。
2. 扩展树：从当前的最小边集合中选择权重最小的边，并将新顶点标记为已包含在树中。
3. 重复：直到所有顶点都被包含在树中。

示例实现

以下是 Prim 算法的 Python 实现：

import heapq

def prim(graph, start):
    mst = []
    visited = set()
    min_heap = [(0, start)]  # (权重, 节点)

    while min_heap and len(visited) < len(graph):
        weight, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        mst.append((weight, u))

        for v, w in graph[u]:
            if v not in visited:
                heapq.heappush(min_heap, (w, v))

    return mst[1:], sum(weight for weight, _ in mst[1:])

# 示例图的邻接表表示
graph = {
    0: [(1, 4), (2, 6)],  # A
    1: [(0, 4), (2, 2), (3, 1)],  # B
    2: [(0, 6), (1, 2), (4, 3)],  # C
    3: [(1, 1), (4, 7)],  # D
    4: [(2, 3), (3, 7)]   # E
}

mst, total_weight = prim(graph, 0)
print("最小生成树边:", mst)
print("总权重:", total_weight)

总结

在本篇中，我们重点讨论了最小生成树的两种算法：Kruskal 算法和 Prim 算法。Kruskal 算法通过选择最小边来构建树，而 Prim 算法则是通过扩展已有的树，将新顶点加入树中。两种算法各有优缺点，具体选用哪种可以根据图的特点和需求来决定。在接下来的文章中，我们将探讨并查集的基本操作及其与最小生成树的关系。