Kruskal算法

是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。

其实就是贪心的应用。

和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

步骤

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

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

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

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

时间复杂度

平均时间复杂度为O(|E|log|E|)，其中E和V分别是图的边集和点集

---

好吧，关于这个算法我知道的不多，这个帖子也是我发的第一个关于算法的帖子，大佬们要是有补充就发在评论区吧。

神犇勿喷！