4.2 primMst算法及时间复杂度分析
void primMst(int **AdjMatrix,EDGENODE *edgeSet,int n,int start) { int iter,minPos,to; EDGENODE edge; initEdgeSet(AdjMatrix,edgeSet,n,start); //初始化边集合 for(iter=0;iter<n-1;iter++) { minPos=chooseEdge(edgeSet,n,iter); //从边集中选择取值最小边 edge=edgeSet[minPos]; //将选择的最小边edgeSet[iter] edgeSet[minPos]=edgeSet[iter]; edgeSet[iter]=edge; to=edgeSet[iter].to; //将选择的边结点加入U集合 modfiyEdgeSet(AdjMatrix,edgeSet,n,iter,to); //调整候选边结点 } }时间复杂度分析：该普利姆算法程序实现的时间复杂度主要由primMst函数、initEdgeSet边集初始化函数、chooseEdge边选择函数、modfiyEdgeSet候选边集调整函数构成，因此基本程序执行语句的执行次数如下： 4.3 Kruskal算法及主要的功能函数模块说明 （1）creatMatrix函数模块 函数原型：void creatMatrix(int **AdjMatrix,EDGENODE *edgeSet,int n,int e)； 函数功能：以文件读入或者键盘输入的方式构造邻接矩阵，AdjMatrix表示邻接矩阵，edgeSet表示边集，n和e分别表示图的顶点数和边数。 （2）printMatrix函数模块 函数原型：void printMatrix(int **AdjMatrix,int n)； 函数功能：输出邻接矩阵，AdjMatrix表示邻接矩阵，n表示图的顶点数。 （3）printEdgeSet函数模块 函数原型：void printEdgeSet(EDGENODE *edgeSet,int e)； 函数功能：输出边集合中的所有边数据，其中edgeSet表示边集合，e表示边的数量。 （4）findRootEdge函数模块 函数原型：int findRootEdge(int nodeNumber)； 函数功能：查找顶点的所在并查集的根，其中nodeNumber表示顶点编号。 （5）mergeEdge函数模块 函数原型：int mergeEdge(int nodeFrom,int nodeTo)； 函数功能：判断顶点from和to是否属于同一连通分量，同时对连通分量进行合并。其中nodeFrom和nodeTo分别为所选边的两个顶点。 （6）kruskalMst最小生成树函数模块 函数原型：void kruskalMst(EDGENODE *edgeSet,int n,int e)； 函数功能：依次从候选边集中选取权值最小边构造最小生成树，其中edgeSet为边集，n和e分别为图中的顶点数和边数。 4.4 kruskal算法及时间复杂度分析
void kruskalMst(EDGENODE *edgeSet,int n,int e) { int index=0; int countEdge=0; int minCost=0; cout<<"------------------------------------"<<endl; printEdgeSet(edgeSet,e); sort(edgeSet,edgeSet+e); //对边集进行快速排序 cout<<"------------------------------------"<<endl; printEdgeSet(edgeSet,e); cout<<"------------------------------------"<<endl; while(index<e) { int from=edgeSet[index].from; int to=edgeSet[index].to; int cost=edgeSet[index].cost; if(mergeEdge(from,to)==0) //利用并查集判断环路,同时对查找路径进行压缩合并 { countEdge++; minCost+=cost; cout<<"("<<from<<","<<to<<") "<<cost<<endl; index++; } else index++; if(countEdge==n-1) break; } if(index<e) cout<<"minCost: "<<minCost<<endl; else cout<<"The Graph is disconnected!"<<endl; //index>=e则不能构造最小生成树 }时间复杂度分析：该克鲁斯卡尔算法的时间复杂度主要由sort快速排序函数、kruskalMst函数、mergeEdge函数、findRootEdge函数构成，各部分时间复杂度如下： 5 程序测试 为了方便测试，将图1中边结点信息存入文本文件，程序在运行时自动读入数据，数据格式如下，其中第一行为图中结点个数与边总数，第二行到最后一行为边的顶点编号和边的权值。 4.1 Prim算法程序运行测试 4.2 Kruskal算法程序运行测试 5 总结 参考文献： [1-2] 孙凌宇, 冷明, 谭云兰等. 赋权有向图的最小生成树算法[J]. 计算机工程, 2010, 36(2): 61-66. [3] 徐建军, 沙力妮, 张艳等. 一种新的最小生成树算法[J]. 电力系统保护与控制, 2011, 39(14): 107-112. [4] 徐凤生. 数据结构与算法C语言版[M]. 北京: 机械工业出版社, 100-124. [5] Anany Levitin. 算法设计与分析基础(第3版)[M] 潘彦译. 北京: 清华大学出版社, 2015, 250-259. [6] 江波, 张黎. 基于Prim算法的最小生成树优化研究[J]. 计算机工程与设计, 2009, 30(13): 3244-3247. [7] 宋国明, 王厚军, 姜书艳等. 最小生成树SVM的模拟电路故障诊断方法[J]. 电子科技大学学报, 2012, 41(3): 412-417. [8] 谭浩强. C程序设计第三版[M]. 北京: 清华大学出版社, 2009, 20-33. [9] 吴艳, 赵端阳, 曹平等. 数据结构(用C++语言描述)[M]. 北京: 北京邮电大学出版社, 2016, 10-15.
