最小生成树-克鲁斯卡尔算法-Kruskal算法

克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），图中每 顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点构成一个连通分量为止

1.概览

  Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

2.算法简单描述

  1).记Graph中有v个顶点，e个边

  2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边

  3).将原图Graph中所有e个边按权值从小到大排序

  4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中

if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中

   添加这条边到图Graphnew中

Kruskal算法样例：

Kruskal算法-1

    首先第一步，我们有一张图Graph，有若干点和边

    将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择，排序完成后，我们率先选择了边AD。

Kruskal算法-2

在剩下的变中寻找。我们找到了CE。这里边的权重也是5

Kruskal算法-3

   依次类推我们找到了6,7,7，即DF，AB，BE。

Kruskal算法-4

     下面继续选择， BC或者EF尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。

     最后就剩下EG和FG了。当然我们选择了EG。最后成功。

鲁斯卡尔算法的时间复杂度主要由排序方法决定，而克鲁斯卡尔算法的排序方法只与网中边的条数有关，而与网中顶点的个数无关，当使用时间复杂度为O（elog2e）的排序方法时，克鲁斯卡尔算法的时间复杂度即为O（log2e），因此当网的顶点个数较多、而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果较好