Prim算法计算器

伪代码

Prim 从任意一个起点开始生长出单棵树。每一步都选取恰好有一个端点已在树内的最便宜的边，仅凭这一条规则就足以保证最优，并且永远不需要回溯。

Prim(图, 起点):
    树内 = {起点}
    pq = 含起点所有出边的优先队列
    mst = []

    当树内尚未包含所有结点时:
        (u, v, w) = pq.取出最小()
        若 v 已在树内: 跳过        // 过期条目

        mst.追加((u, v, w))
        树内.加入(v)
        对每条边 (v, x, w2):
            若 x 不在树内: pq.插入((v, x, w2))

正确性依赖于割性质：对结点的任意一种二分划分，跨越该割的最便宜的边必定属于某棵最小生成树。Prim 把这条性质用在「已在树内」与「尚未加入」这道割上，因此每次取跨越割的最便宜边总是安全的。这条性质也解释了为何完全不需要回溯：一条已被接受的边，绝不会因为后来出现的信息而变成错误选择，这一点与 TSP 之类的问题截然不同。

分步示例演算

在一个小型加权图上从 A 开始生长最小生成树，此处贪心选择会刻意舍弃一条看似更便宜的直接边。

示例图: 无向边 A-B (2)、A-C (3)、B-C (1)、C-D (4) 和 B-D (7)。

1. 从 A 起步. 树中只有 A。从它出发的边是权重 2 的 A-B 与权重 3 的 A-C，两者都跨越 {A} 与其余结点之间的这道割。
2. 选取 A-B (2). A-B 是更便宜的跨越边，于是 B 加入树中。此时边界上有权重 3 的 A-C、权重 1 的 B-C 和权重 7 的 B-D。
3. 选取 B-C (1). 权重 1 的 B-C 现在成为最便宜的跨越边，比权重 3 的直接边 A-C 更便宜，于是 C 经由 B 加入。直接边 A-C 从未被使用。这一步值得留意：与起点相邻的结点未必就通过起点接入。
4. A-C 变为内部边. 由于 A 与 C 都已在树中，边 A-C 的两个端点都在内部，当它浮出队列时会被丢弃。这正是过期条目检查在发挥作用。
5. 选取 C-D (4). 剩下的跨越边是权重 4 的 C-D 与权重 7 的 B-D。C-D 更便宜，于是 D 加入，树已覆盖全部四个结点，算法结束。

最小生成树由 A-B、B-C 和 C-D 构成，总权重为 2 + 1 + 4 = 7。注意它恰好有三条边，比四个结点少一条，任何生成树都必然如此。还要注意这里的树是一条链，这提醒我们最小生成树并不是最短路径树：树中从 A 到 D 的距离是 7，而图中最短路径 A 到 C 到 D 为 3 + 4 = 7，A 到 B 到 D 则为 9。两个问题优化的是不同的量，把二者混为一谈是这一主题上最常见的概念性错误。

复杂度及其来源

时间: O(E log V) · 空间: O(V + E)

使用二叉堆时，每条边至多被插入一次、取出一次，各为 O(log E)；由于 E 至多为 V 的平方，log E 与 log V 只相差常数因子，因此总体为 O(E log V)。每个结点恰好被加入树一次，这把外层循环的迭代次数限制在 V 次。若改用斐波那契堆并以减小键值代替惰性插入，界限可改进到 O(E + V log V)，在稠密图上渐进更优，但常数因子通常使其在实践中并不划算。在非常稠密的图上，最朴素的做法反而胜出：维护一个数组记录到每个树外结点的最便宜边，每轮扫描一次即可，复杂度为 O(V 的平方)，当 E 接近 V 的平方时就优于 O(E log V)。因此数据结构的选择取决于稠密程度，而非某种一概而论的偏好。

何时使用普里姆最小生成树算法，何时不宜

Prim 与 Kruskal 都能给出最小生成树。选哪个取决于稠密程度、边的到达顺序以及图是否连通。

常见陷阱

• 把最小生成树与最短路径树混为一谈. 这是两个不同的目标。最小生成树最小化整棵树的总权重；最短路径树最小化从某个源点到每个结点的距离。在上面的例子中，最小生成树里从 A 到 D 的路径代价为 7，而一般来说最小生成树可能让某些结点对之间的距离远大于必要值。如果你关心的是从某个点出发的距离，需要的是 Dijkstra 而不是 Prim。
• 省略过期条目检查. 惰性堆中会积累一些边，它们的远端后来已通过别的路径进入树中。把这样的边取出并加入会形成环，破坏树结构。在接受一条边之前务必检查目标是否已在树内，这与 Dijkstra 中对应的那道守卫完全同理。
• 在非连通图上运行它. Prim 从一个起点生长一棵树，当找不到跨越边时便停止。因此在非连通图上它只会返回某一个连通分量的生成树，而且不会报错。若你需要的是最小生成森林，请从每个未访问的结点重新启动，或改用天然支持这一情形的 Kruskal。
• 以为最小生成树唯一. 当多条边权重相同时，可能存在许多总权重相同的最小生成树。只有所有边权互不相同时，这棵树才是唯一的。测试应当比较总权重而绝不是边的集合，否则完全正确的实现也会被判为失败。
• 把它用于有向图. Prim 与 Kruskal 意义下的生成树是无向图的概念。有向情形的对应物是最小生成树形图，需要 Chu-Liu/Edmonds 算法；Prim 在那里会给出错误答案而且不会报错。

常见问题

Prim 算法有什么用？

它求最小生成树，也就是连接一个加权无向图全部结点的最便宜边集。它用于设计低成本网络，如电网、光纤与电信线路、供水管网和芯片布线，同时也支撑单链接聚类以及某些图像分割方法。

Prim 算法的时间复杂度是多少？

使用常见实现的二叉堆时为 O(E log V)。斐波那契堆给出 O(E + V log V)，在稠密图上渐进更优但常数更差。在非常稠密的图上，O(V 的平方) 的简单数组扫描反而更快，因为它完全避开了堆的开销。

Prim 算法与 Kruskal 算法有什么区别？

Prim 从一个起始结点向外生长出单棵连通的树，每次都加入能触及新结点的最便宜的边。Kruskal 把所有边排序后，逐条加入不会形成环的边，生长出一片最终合并为一棵树的森林。Prim 适合稠密图，Kruskal 适合稀疏图或边已排序的情形，两者都给出最小生成树。

最小生成树和最短路径树是一回事吗？

不是。最小生成树最小化其所有边的总权重；最短路径树最小化从某个源点到每个结点的距离。二者常常不同，即便存在一条很短的直接边，最小生成树也可能让两个结点在树中相距很远，因为使用那条边会抬高总权重。

起始结点会改变结果吗？

在权重出现并列时它可能改变具体选中哪些边，但绝不会改变总权重。从任何起点出发，Prim 都会给出一棵最小生成树。若所有边权互不相同，这棵树是唯一的，起始结点则毫无影响。