克鲁斯克尔演算法
外观
克鲁斯克尔演算法 | |
---|---|
概况 | |
类别 | 最小生成树 |
资料结构 | 并查集 |
复杂度 | |
平均时间复杂度 | 或 |
空间复杂度 | |
相关变量的定义 | |
点集 | |
边集 |
图与树 搜索算法 |
---|
分类 |
相关主题 |
克鲁斯克尔演算法(英语:Kruskal's algorithm)是一种用来寻找最小生成树的演算法[1],由美国数学家约瑟夫·克鲁斯克尔在1956年发表[2]。用来解决同样问题的还有普林演算法和布卢瓦卡演算法等。三种演算法都是贪心算法的应用。和布卢瓦卡演算法不同的地方是,克鲁斯克尔演算法在图中存在相同权值的边时也有效。
步骤
[编辑]- 新建图,中拥有原图中相同的节点,但没有边
- 将原图中所有的边按权值从小到大排序
- 从权值最小的边开始,如果这条边连接的两个节点于图中不在同一个连通分量中,则添加这条边到图中
- 重复3,直至图中所有的节点都在同一个连通分量中
证明
[编辑]- 这样的步骤保证了选取的每条边都是桥,因此图构成一个树。
- 为什么这一定是最小生成树呢?关键还是步骤3中对边的选取。演算法中总共选取了条边,每条边在选取的当时,都是连接两个不同的连通分量的权值最小的边
- 要证明这条边一定属于最小生成树,可以用反证法:如果这条边不在最小生成树中,它连接的两个连通分量最终还是要连起来的,通过其他的连法,那么另一种连法与这条边一定构成了环,而环中一定有一条权值大于这条边的边,用这条边将其替换掉,图仍旧保持连通,但总权值减小了。也就是说,如果不选取这条边,最后构成的生成树的总权值一定不会是最小的。
时间复杂度
[编辑]通过使用路径压缩的并查集,平均时间复杂度为,其中和分别是图的边集和点集。
此外,如果同时使用路径压缩和按秩合并,时间复杂度可以优化到 ,其中表示反阿克曼函数。
示例
[编辑]伪代码
[编辑]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;
}
参考文献
[编辑]- ^ Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein. Introduction To Algorithms Third. MIT Press. 2009: 631. ISBN 978-0262258104.
- ^ 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.
|