1、kruskal算法（克鲁斯卡尔）思想
该算法是基于贪心的思想得到的，假设有n个顶点的连通网G = {V,E} 中，最初每个顶点都是孤立点，没有边的非连通图G’= {V, E},图中每个顶点自成一个连通分量。把每条边按照权值从小到大排列，按照顺序选取每条边，若该边的两个顶点落在不同的连通分量上，则将此边加入到G’中；否则将此边舍去，重新选择下一条边。如此重复下去，直到所有顶点在同一个连通分量上为止。
2、算法流程
输入：图G(V,E) 输出：G的最小生成树
下面给出一个无向图B,我们使用Kruskal来找无向图B的最小生成树。
① 首先，根据每条边的权重把它们从小到大排序，选取权值最小的一条边（A,D），因为A,D不在同一个树，所以合并顶点A,D 所在的树。
②接着在剩下的边中找权值最小的边，找到了（C,E）, C,E不在同一个树，合并顶点C,E所在的树。
③ 不断重复上面的步骤，直到所有的顶点在同一个连通分量上为止。
至此，我们找到了无向图B的最小生成树。
3、python实现
下面用python实现找到上面无向图B的最小生成树。
#coding:utf-8 from pylab import * inf=float('inf') #邻接矩阵表示 vexs = array([[0,7,inf,5,inf,inf,inf],#A [7,0,8,9,7,inf,inf],#B [inf,8,0,inf,5,inf,inf],#C [5,9,inf,0,15,6,inf],#D [inf,7,5,15,0,8,9],#E [inf,inf,inf,6,8,0,11],#F [inf,inf,inf,inf,9,11,0]])#G lengthVex = len(vexs) #邻接矩阵大小 beginEdge = [] endEdge = [] weight = [] group = [] for i in arange(lengthVex): #生成边集数组 group.append([i]) for j in arange(i+1,lengthVex): if(vexs[i, j]>0 and vexs[i, j]<INFINITY): beginEdge.append(i) #每条边的起点 endEdge.append(j) #每条边的终点 weight.append(vexs[i, j]) #每条边的权值 lengthEdge = len(weight) #边的条数 sum = 0 for i in arange(lengthEdge): #遍历每条边 I = (argsort(weight))[0] for j in arange(lengthVex): if(beginEdge[I]) in group[j]: m = j if(endEdge[I]) in group[j]: n = j if m != n: #判断当前这条边是否属于不同的连通分量，如果是，将其合并 group[m] = group[m] + group[n] group[n] = [] sum = sum + weight[I] print(weight[I]) del weight[I] #删除遍历过的边以及顶点 del beginEdge[I] del endEdge[I] print("The length of the minimum cost spanning tree is: ",sum)运行结果：
5,5,6,7,7,9表示组成最小生成树的边的权值，权值之和为39.
