克魯斯克爾演算法（）是一種用來尋找最小生成樹的演算法，由美國數學家約瑟夫·克魯斯克爾在1956年發表。用來解決同樣問題的還有普林演算法和等。三種演算法都是贪心算法的應用。和布盧瓦卡演算法不同的地方是，克魯斯克爾演算法在圖中存在相同權值的邊時也有效。

步骤

新建图G，G中拥有原图中相同的节点，但没有边

将原图中所有的边按权值从小到大排序

从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中

重複3，直至图G中所有的节点都在同一个连通分量中

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

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

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

示例
伪代码
-{}-
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++ 实现
以下代码基于路径压缩和按秩合并的并查集，时间复杂度 \Omicron(|E| \alpha (|V|))。

#include

struct DSU {
std::vector 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> 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
参考文献