Kruskal算法
解最小生成树的另一种常见的算法是Kruskal算法，它比Prim算法更直观。
Kruskal算法的做法是：每次都从剩余边中选取权值最小的，当然，这条边不能使已有的边产生回路。手动求解会发现Kruskal算法异常简单，下面是一个例子
先对边的权值排个序：
1(V0,V4)、2(V2,V6)、4(V1,V3)、6(V1,V2)、8(V3,V6)、10(V5,V6)、12(V3,V5)、15(V4,V5)、20(V0,V1)
首选边1(V0,V4)、2(V2,V6)、4(V1,V3)、6(V1,V2)，此时的图是这样
显然，若选取边8(V3,V6)则会出现环，则必须抛弃8(V3,V6)，选择下一条10(V5,V6)没有问题，此时图变成这样
显然，12(V3,V5)同样不可取，选取15(V4,V5)，边数已达到要求，算法结束。最终的图是这样的
算法逻辑很容易理解，但用代码判断当前边是否会引起环的出现则很棘手。
这里简单提一提连通分量
在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中较大的连通子图称为连通分量。
在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。
【算法说明】
为了判断环的出现，我们换个角度来理解Kruskal算法的做法：初始时，把图中的n个顶点看成是独立的n个连通分量，从树的角度看，也是n个根节点。我们选边的标准是这样的：若边上的两个顶点从属于两个不同的连通分量，则此边可取，否则考察下一条权值最小的边。
于是问题又来了，如何判断两个顶点是否属于同一个连通分量呢？这个可以参照并查集的做法解决。它的思路是：如果两个顶点的根节点是一样的，则显然是属于同一个连通分量。这也同样暗示着：在加入新边时，要更新父节点。
憋说话，看代码
点击文末的“阅读原文”字样可以直接复制黏贴获取源代码哦
最后再多说两句
看完了这个
是不是感觉自己又在装逼路上
再次晋级？
古语云：持之以恒，有朝一日，必可成仙。
祝贺大家早日成仙。
