Kruskal算法是一种用来查找最小生成树的算法[1]，由Joseph Kruskal在1956年发表[2]。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。
目录 1 步骤 2 证明 3 时间复杂度 4 示例 5 伪代码 6 参考源程序 6.1 C++ 实现 7 参考文献 步骤 新建图 � G， � G中拥有原图中相同的节点，但没有边 将原图中所有的边按权值从小到大排序 从权值最小的边开始，如果这条边连接的两个节点于图 � G中不在同一个连通分量中，则添加这条边到图 � G中 重复3，直至图 � G中所有的节点都在同一个连通分量中 证明 这样的步骤保证了选取的每条边都是桥，因此图 � G构成一个树。 为什么这一定是最小生成树呢？关键还是步骤3中对边的选取。算法中总共选取了 � − 1 n-1条边，每条边在选取的当时，都是连接两个不同的连通分量的权值最小的边 要证明这条边一定属于最小生成树，可以用反证法：如果这条边不在最小生成树中，它连接的两个连通分量最终还是要连起来的，通过其他的连法，那么另一种连法与这条边一定构成了环，而环中一定有一条权值大于这条边的边，用这条边将其替换掉，图仍旧保持连通，但总权值减小了。也就是说，如果不选取这条边，最后构成的生成树的总权值一定不会是最小的。 时间复杂度 通过使用路径压缩的并查集，平均时间复杂度为 � ( | � | log | � | ) {\displaystyle O(|E|\log |V|)}，其中 � E和 � V分别是图的边集和点集。
此外，如果同时使用路径压缩和按秩合并，时间复杂度可以优化到 � ( | � | � ( | � | ) ) {\displaystyle O(|E|\alpha (|V|))}，其中 �\alpha 表示反阿克曼函数。
示例 图例 说明 Kruskal Algorithm 1.svg AD和CE是最短的两条边，长度为5，其中AD被任意选出，以高亮表示。 Kruskal Algorithm 2.svg 现在CE是不属于环的最短边，长度为5，因此第二个以高亮表示。 Kruskal Algorithm 3.svg 下一条边是长度为6的DF，同样地以高亮表示。 Kruskal Algorithm 4.svg 接下来的最短边是AB和BE，长度均为7。AB被任意选中，并以高亮表示。边BD用红色高亮表示，因为B和D之间已经存在一条（标为绿色的）路径，如果选择它将会构成一个环（ABD）。 Kruskal Algorithm 5.svg 以高亮表示下一条最短边BE，长度为7。这时更多的边用红色高亮标出：会构成环BCE的BC、会构成环DBEA的DE以及会构成环FEBAD的FE。 Kruskal Algorithm 6.svg 最终，标记长度为9的边EG，得到最小生成树，结束算法过程。 伪代码 KRUSKAL-FUNCTION(G, w) 1 F := 空集合 2 for each 图 G 中的顶点 v 3 do 将 v 加入森林 F 4 所有的边(u, v) ∈ E依权重 w 递增排序 5 for each 边(u, v) ∈ E 6 do if u 和 v 不在同一棵子树 7 then F := F ∪ {(u, v)} 8 将 u 和 v 所在的子树合并 参考源程序 C++ 实现 以下代码基于路径压缩和按秩合并的并查集，时间复杂度 � ( | � | � ( | � | ) ) {\displaystyle O(|E|\alpha (|V|))}。
#include <bits/stdc++.h>
struct DSU {
std::vector
int main() { int n, m; // 点数，边数 std::cin >> n >> m; std::vector<std::tuple<int, int, int>> edge(m); // 边集，三元组分别表示边权和边的两个端点 for (auto &[w, u, v] : edge) std::cin >> u >> v >> w; std::sort(edge.begin(), edge.end()); // 按边权升序排序 DSU dsu(n); // 初始化并查集 long long result = 0; // 最小生成树边权和 for (auto &[w, u, v] : edge) if (dsu.Merge(u, v)) result += w; // 合并两个连通分量并统计答案 std::cout << result << std::endl; return 0; }
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: