金华做网站建设公司/免费代理上网网站

Kruskal 算法用于求解无向图中的最小生成树问题。

问题描述：一个无向图 $G=(V,E)$ 的最小生成树就是由该图中连接所有顶点的边构成的树，且总的权值最低。此时，最小生成树的边数为 $|V|-1$。

最小生成树存在当且仅当 $G$ 是连通的。

形式上，Kruskal 算法是在处理一个森林（树的集合）。开始时，存在 $|V|$ 棵单节点的树。Kruskal 算法不断地处理 $G$ 中的每条边 $(u,v)$，以决定是否连接节点 $u,v$，也就是将两棵树合并为一棵树。当算法终止时，就只剩下一棵树了，即最小生成树。

（1）构造 $|V|$ 棵单节点的树，每个树包含的是 $G$ 中的一个顶点；
（2）构造一个大小为 $|E|$ 的最小二叉堆，其中保存的是 $G$ 中的所有连边；
（3）如果堆为空，则返回；否则，弹出堆顶元素 $(u,v)$，如果 $u,v$ 不在同一棵树上（可以使用不相交集合中的 $find$ 算法），则连接节点 $u,v$（使用 $union$ 算法合并两个不相交集合）；否则，舍弃该连边；
（4）继续步骤（3）。