数据结构与算法 / 系统课时

Prim 和 Kruskal 怎么选

Prim 和 Kruskal 怎么选

Prim 和 Kruskal 都能求无向连通带权图的最小生成树,但它们处理边的方式完全不同。实际选型时,最重要的不是记住两个名字,而是看图的稀疏程度、输入形式以及手头是否适合使用堆或并查集。

学习目标

  • 理解 Prim 与 Kruskal 构造最小生成树时的核心差异
  • 能根据顶点数、边数和数据存储形式选择合适算法
  • 能用代码验证两种算法得到相同的最小生成树权值

两种算法从哪里开始不同

Prim 始终维护一棵正在扩张的树。从任意顶点开始,每次选择一条连接“已进入生成树顶点”和“未进入顶点”的最小权边,把新顶点纳入树中。因此它关心的是当前树与外部之间有哪些候选边。

Kruskal 不从某个顶点出发,而是把全部边按权重从小到大处理。只要当前边连接的是两个不同连通分量,就接受这条边;如果两端已经连通,加入它会产生环,因此跳过。判断两端是否属于同一分量通常使用并查集。

两者依据的都是最小生成树的割性质,但维护状态不同:Prim 维护“一个不断扩大的连通区域”,Kruskal 维护“若干逐渐合并的连通分量”。

稀疏图和稠密图怎样影响选择

设顶点数为 VV,边数为 EE。使用邻接表和二叉堆时,Prim 通常可以做到 O(Elog⁡V)O(E\log V);Kruskal 的主要成本是排序全部边,为 O(Elog⁡E)O(E\log E),并查集操作的额外成本接近线性。

如果图很稀疏,边本来就以边列表形式存在,Kruskal 往往最直接:排序后依次执行并查集即可。它不需要维护每个顶点到当前生成树的最小连接代价。

如果图非常稠密,例如接近完全图,边数约为顶点数平方量级,那么使用邻接矩阵实现的 Prim 可以直接做到 O(V2)O(V^2),既避免显式排序大量边,实现也比较稳定。

场景 更自然的选择 原因
稀疏图、已有边列表 Kruskal 排序边后直接配合并查集
稠密图、邻接矩阵 Prim O(V2)O(V^2) 实现简单,不必排序全部边
邻接表且希望从某点逐步扩张 Prim 堆可以只维护当前边界候选边
已有成熟并查集代码 Kruskal 环检测与分量合并非常直接
图可能不连通且需要最小生成森林 Kruskal 同一流程可自然得到各连通分量的生成树

用同一张图验证结果

下面的完整 Python 程序分别用堆实现 Prim、用并查集实现 Kruskal。示例图的最小生成树唯一权值为 6,因此两种实现即使选择边的先后顺序不同,总权值也应一致。

python
import heapq

vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
    ('A', 'B', 1),
    ('A', 'C', 4),
    ('B', 'C', 2),
    ('B', 'D', 5),
    ('C', 'D', 1),
    ('C', 'E', 3),
    ('D', 'E', 2),
]


def prim(vertices, edges):
    graph = {v: [] for v in vertices}
    for u, v, w in edges:
        graph[u].append((w, u, v))
        graph[v].append((w, v, u))

    visited = {vertices[0]}
    heap = list(graph[vertices[0]])
    heapq.heapify(heap)
    mst = []

    while heap and len(visited) < len(vertices):
        w, u, v = heapq.heappop(heap)
        if v in visited:
            continue
        visited.add(v)
        mst.append((u, v, w))
        for candidate in graph[v]:
            if candidate[2] not in visited:
                heapq.heappush(heap, candidate)

    if len(visited) != len(vertices):
        raise ValueError('graph is disconnected')
    return mst


def kruskal(vertices, edges):
    parent = {v: v for v in vertices}
    rank = {v: 0 for v in vertices}

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]:
            rank[ra] += 1
        return True

    mst = []
    for u, v, w in sorted(edges, key=lambda item: item[2]):
        if union(u, v):
            mst.append((u, v, w))
            if len(mst) == len(vertices) - 1:
                break

    if len(mst) != len(vertices) - 1:
        raise ValueError('graph is disconnected')
    return mst


prim_mst = prim(vertices, edges)
kruskal_mst = kruskal(vertices, edges)
print('Prim:', prim_mst, 'weight =', sum(w for _, _, w in prim_mst))
print('Kruskal:', kruskal_mst, 'weight =', sum(w for _, _, w in kruskal_mst))

预期输出

text
Prim: [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 1), ('D', 'E', 2)] weight = 6
Kruskal: [('A', 'B', 1), ('C', 'D', 1), ('B', 'C', 2), ('D', 'E', 2)] weight = 6

当存在相同权重的候选边时,最小生成树可能不唯一,因此两种算法输出的边集合不一定完全相同;只要都包含 V−1V-1 条边、保持连通且总权值达到最小即可。

选型时真正要检查什么

不要只按“Prim 适合稠密图、Kruskal 适合稀疏图”机械选择。工程实现还要看数据已经以什么形式存在。一个稀疏图如果已经维护了邻接表和优先队列,Prim 可能更省转换成本;一个规模不大的稠密图如果输入天然就是边列表,Kruskal 也完全可用。

还要区分连通图和非连通图。严格来说,非连通图不存在覆盖全部顶点的单棵最小生成树。Kruskal 在继续扫描边时会自然产生最小生成森林;Prim 若要达到同样效果,则需要对每个尚未访问的连通分量重新启动一次。

因此,选型可以归结为三个问题:边是否远少于顶点数平方、输入更接近邻接结构还是边列表、实现中更方便维护堆还是并查集。复杂度相近时,优先采用与现有数据结构最匹配、最容易验证正确性的方案。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Prim 和 Kruskal 怎么选

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通