跳转到内容

克鲁斯克尔演算法

本页使用了标题或全文手工转换
维基百科,自由的百科全书
(重定向自Kruskal算法
克鲁斯克尔演算法
克鲁斯克尔算法的图解
概况
類別最小生成树
資料結構并查集
复杂度
平均時間複雜度
空間複雜度
相关变量的定义
点集
边集

克魯斯克爾演算法(英語:Kruskal's algorithm)是一種用來尋找最小生成樹的演算法[1],由美國數學家約瑟夫·克魯斯克爾在1956年發表[2]。用來解決同樣問題的還有普林演算法布盧瓦卡演算法英语Borůvka's algorithm等。三種演算法都是贪心算法的應用。和布盧瓦卡演算法不同的地方是,克魯斯克爾演算法在圖中存在相同權值的邊時也有效。

步骤

  1. 新建图中拥有原图中相同的节点,但没有边
  2. 将原图中所有的边按权值从小到大排序
  3. 从权值最小的边开始,如果这条边连接的两个节点于图中不在同一个连通分量中,则添加这条边到图
  4. 重複3,直至图中所有的节点都在同一个连通分量中

证明

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

時間複雜度

通过使用路径压缩的并查集,平均时间复杂度为,其中分别是图的边集和点集。

此外,如果同时使用路径压缩和按秩合并,时间复杂度可以优化到 ,其中表示反阿克曼函數

示例

图例 说明
ADCE是最短的两条边,长度为5,其中AD被任意选出,以高亮表示。
现在CE是不属于环的最短边,长度为5,因此第二个以高亮表示。
下一条边是长度为6的DF,同样地以高亮表示。
接下来的最短边是ABBE,长度均为7。AB被任意选中,并以高亮表示。边BD用红色高亮表示,因为BD之间已经存在一条(标为绿色的)路径,如果选择它将会构成一个环(ABD)。
以高亮表示下一条最短边BE,长度为7。这时更多的边用红色高亮标出:会构成环BCEBC、会构成环DBEADE以及会构成环FEBADFE
最终,标记长度为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++ 实现

以下代码基于路径压缩和按秩合并的并查集,时间复杂度

#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;
}

参考文献

  1. ^ Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein. Introduction To Algorithms Third. MIT Press. 2009: 631. ISBN 978-0262258104. 
  2. ^ Kruskal, J. B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society. 1956, 7 (1): 48–50. JSTOR 2033241. doi:10.1090/S0002-9939-1956-0078686-7.