查看“︁克鲁斯克尔演算法”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
}}
{{算法信息框
| image = [[File:MST_kruskal_en.gif|255px|克鲁斯克尔算法的图解]]
| class = [[最小生成树]]
| data = [[并查集]]
| best-time = 
| average-time = <math>O (| E| \log | V|)</math> 或 <math>O (| E| \alpha (| V|))</math>
| space = <math>O (| E| + | V|)</math>
| Var1 = <math>V</math>
| Def1 = 点集
| Var2 = <math>E</math>
| Def2 = 边集
| time = 
}}
{{图搜索算法}}
'''克魯斯克爾演算法'''（{{lang-en|Kruskal's algorithm}}）是一種用來尋找[[最小生成樹]]的演算法<ref name=":0">{{Cite book|title = Introduction To Algorithms|url = https://archive.org/details/introductiontoal00corm_558|last = Cormen|first = Thomas|publisher = MIT Press|year = 2009|isbn = 978-0262258104|location = |pages = [https://archive.org/details/introductiontoal00corm_558/page/631 631]|last2 = Charles E Leiserson, Ronald L Rivest, Clifford Stein|edition = Third}}</ref>，由[[美國]]數學家[[約瑟夫·克魯斯卡爾|約瑟夫·克魯斯克爾]]在1956年發表<ref>{{Cite journal | last1 = Kruskal | first1 = J. B. | authorlink1 = Joseph Kruskal| doi = 10.1090/S0002-9939-1956-0078686-7 | title = On the shortest spanning subtree of a graph and the traveling salesman problem | journal = [[Proceedings of the American Mathematical Society]] | volume = 7 | issue = 1 | pages = 48–50 | year = 1956| jstor = 2033241| pmid =  | pmc = }}</ref>。用來解決同樣問題的還有[[普林演算法]]和{{tsl|en|Borůvka's algorithm|布盧瓦卡演算法}}等。三種演算法都是[[贪心法|贪心算法]]的應用。和布盧瓦卡演算法不同的地方是，克魯斯克爾演算法在圖中存在相同權值的邊時也有效。

== 步骤 ==
# 新建图<math>G</math>，<math>G</math>中拥有原图中相同的节点，但没有边
# 将原图中所有的边按权值从小到大排序
# 从权值最小的边开始，如果这条边连接的两个节点于图<math>G</math>中不在同一个连通分量中，则添加这条边到图<math>G</math>中
# 重複3，直至图<math>G</math>中所有的节点都在同一个连通分量中

== 证明 ==
#这样的步骤保证了选取的每条边都是桥，因此图<math>G</math>构成一个树。
#为什麽这一定是最小生成树呢？关键还是步骤3中对边的选取。演算法中总共选取了<math>n-1</math>条边，每条边在选取的当时，都是连接两个不同的连通分量的权值最小的边
#要证明这条边一定属于最小生成树，可以用反证法：如果这条边不在最小生成树中，它连接的两个连通分量最终还是要连起来的，通过其他的连法，那麽另一种连法与这条边一定构成了环，而环中一定有一条权值大于这条边的边，用这条边将其替换掉，图仍旧保持连通，但总权值减小了。也就是说，如果不选取这条边，最后构成的生成树的总权值一定不会是最小的。

== 時間複雜度 ==
通过使用路径压缩的[[并查集]]，平均时间复杂度为<math>O(|E| \log |V|)</math>，其中<math>E</math>和<math>V</math>分别是图的边集和点集。

此外，如果同时使用路径压缩和按秩合并，[[并查集#时间复杂度|时间复杂度]]可以优化到 <math>\Omicron(|E| \alpha (|V|))</math>，其中<math>\alpha</math>表示[[阿克曼函數#反函數|反阿克曼函數]]。

== 示例 ==

{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
! 图例 !! 说明
|-
|[[Image:Kruskal Algorithm 1.svg|200px]]
|'''AD'''和'''CE'''是最短的两条边，长度为5，其中'''AD'''被任意选出，以高亮表示。
|-
|[[Image:Kruskal Algorithm 2.svg|200px]]
|现在'''CE'''是不属于环的最短边，长度为5，因此第二个以高亮表示。
|-
|[[Image:Kruskal Algorithm 3.svg|200px]]
|下一条边是长度为6的'''DF'''，同样地以高亮表示。
|-
|[[Image:Kruskal Algorithm 4.svg|200px]]
|接下来的最短边是'''AB'''和'''BE'''，长度均为7。'''AB'''被任意选中，并以高亮表示。边'''BD'''用红色高亮表示，因为'''B'''和'''D'''之间已经存在一条（标为绿色的）路径，如果选择它将会构成一个环（'''ABD'''）。
|-
|[[Image:Kruskal Algorithm 5.svg|200px]]
|以高亮表示下一条最短边'''BE'''，长度为7。这时更多的边用红色高亮标出：会构成环'''BCE'''的'''BC'''、会构成环'''DBEA'''的'''DE'''以及会构成环'''FEBAD'''的'''FE'''。
|-
|[[Image:Kruskal Algorithm 6.svg|200px]]
|最终，标记长度为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++ 实现 ===
以下代码基于路径压缩和按秩合并的并查集，时间复杂度 <math>\Omicron(|E| \alpha (|V|))</math>。
<syntaxhighlight lang="c++" line="1" start="1">
#include <bits/stdc++.h>

struct DSU {
    std::vector<int> fa, sz;
    DSU(int n = 0) : fa(n), sz(n, 1) {
        std::iota(fa.begin(), fa.end(), 0);
    }
    int Find(int x) { // 路径压缩
        while (x != fa[x])
            x = fa[x] = fa[fa[x]];
        return x;
    }
    bool Merge(int x, int y) { // 按秩合并
        x = Find(x), y = Find(y);
        if (x == y) return false; // 处于同一连通分量
        if (sz[x] > sz[y]) std::swap(x, y);
        fa[x] = y;
        sz[y] += sz[x];
        return true;
    }
}; // 并查集

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;
}
</syntaxhighlight>
== 参考文献 ==
{{reflist}}

{{算法}}
[[Category:图算法]]
[[Category:带有伪代码示例的条目]]