继上一篇文章的Prim算法，今天学习使用的是Kruskal算法，Prim和Kruskal算法作用是相同的，都是为了求解加权图问题中的最小生成树，至于Kruskal算法的原理也是很好理解的，这里不多累赘简单概要一下Kruskal算法的的核心思想：
首先设置一个空的集合A，依次从原始图中寻找权重最小的边加入到A中，一个前提和原则是：不能形成回路，n个顶点，当A中存在n-1条边的时候算法终止
核心思想就是这么简洁，但是算法这东西，往往就是越简单越是容易被接受和使用，我本人对于Kruskal算法和Prim算法在本科的时候考试做题编程都是使用Kruskal算法居多，可能就是感觉这个做起来更方便了一点，简单实现了一下如下：
#!usr/bin/env python#encoding:utf-8'''__Author__:沂水寒城功能：使用Kruskal算法求加权连通图的最小生成树'''import randomimport timeimport numpydef random_matrix_genetor(vex_num=10):'''随机图顶点矩阵生成器输入：顶点个数，即矩阵维数'''data_matrix=[]for i in range(vex_num):one_list=[]for j in range(vex_num):one_list.append(random.randint(1, 100))data_matrix.append(one_list)return data_matrixdef Kruskal(data_matrix):'''Kruskal 算法输入：图矩阵输出：加权最小生成树总权重'''vex_num=len(data_matrix)kruskal=[]weights=[]start_set=[]end_set=[]for i in range(vex_num):kruskal.append([i])for j in range(i+1,vex_num):if data_matrix[i][j]!='N':start_set.append(i)end_set.append(j)weights.append(data_matrix[i][j])distance=0for i in range(vex_num):tmp=numpy.argsort(weights)[0]for j in range(vex_num):if start_set[tmp] in kruskal[j]:m=jif end_set[tmp] in kruskal[j]:n=jif m!=n:kruskal[m]=kruskal[m]+kruskal[n]kruskal[n]=[]distance+=weights[tmp]weights.pop(tmp)start_set.pop(tmp)end_set.pop(tmp)print '加权最小生成树总权重为：', distancereturn distancedef main_test_func(vex_num=10):'''主测试函数'''start_time=time.time()data_matrix=random_matrix_genetor(vex_num)distance=Kruskal(data_matrix)end_time=time.time()return end_time-start_timeif __name__=='__main__':data_matrix=[[0,3,1,'N'],[3,0,2,4],[1,2,0,5],['N',4,5,0]]print data_matrixKruskal(data_matrix) time_list=[]print '----------------------------10顶点测试-------------------------------------'time10=main_test_func(10)time_list.append(time10)print '----------------------------50顶点测试-------------------------------------'time50=main_test_func(50)time_list.append(time50)print '----------------------------100顶点测试-------------------------------------'time100=main_test_func(100)time_list.append(time100)print '----------------------------1000顶点测试-------------------------------------'time1000=main_test_func(1000)time_list.append(time1000)print '---------------------------------时间消耗对比--------------------------------'for one_time in time_list:print one_time
结果如下：
[[0, 3, 1, 'N'], [3, 0, 2, 4], [1, 2, 0, 5], ['N', 4, 5, 0]]加权最小生成树总权重为： 7----------------------------10顶点测试-------------------------------------加权最小生成树总权重为： 111----------------------------50顶点测试-------------------------------------加权最小生成树总权重为： 103----------------------------100顶点测试-------------------------------------加权最小生成树总权重为： 116----------------------------1000顶点测试-------------------------------------加权最小生成树总权重为： 834---------------------------------时间消耗对比--------------------------------0.00.0109999179840.067000150680557.513999939[Finished in 58.1s]
时间上的话可以看出来的确是跟Prim算法相差了一大截，尤其是当数据规模增大的时候，这个变得极其明显，我个人只是在做习题相关的时候更偏重于使用Kruskal算法的思想来求解得到加权图中的最小生成树，Prim算法在应对大数据规模的图矩阵的时候有着无可比拟的优势，这一点自然就被用于大规模的数据中了，当然，二者都是很优秀的算法，各有千秋
好了，简单的学习了一下，学习中也查阅了相关的网上资料，关于Kruskal算法就到这里了，如有兴趣欢迎讨论！
