资源描述：
《最小生成树论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、最小生成树最小生成树问题摘要：本文通过对最小生成树两种算法(Kruskal算法和Prim算法)的分析，用C语言写出了Kruskal算法的C语言源程序，通过计算机实现求一个连通图的最小生成树问题。关键词：最小生成树Kruskal算法Prim算法C语言源程序引言现实屮一些实际应用问题可通过利川连通图、生成树的模型來建立求解，找出最优的方法，而在任意一个连通图中存在许多条生成树，如何从这些生成树屮找出一条权最小的生成树对解决现实生活中实际应用问题具冇匝大意义，所以经过数学家的研究，口前最小生成树的算法主耍有Kruskal算法和Prim
2、算法，那么对这两种方法在计算机上的实现也关系着效率的提高，两种算法的C语言程序也应运而出。正文一.对最小纶成树问题中的认识：①G(V,E)是一个树，若p(G)M2,则G中至少冇两个悬挂点。②树G(V,E)屮不相邻的两个点间添上一条边，则得到只含一个圈的图G'；若在图G'中从该圈中再去掉任意一条边得到图G〃，则图G〃乂成为树。二.最小生成树的算法：①Kruskal算法(避圈法):I令匸1,E()二①(空集)；II选一条eiWEEi_],使ei是所有不在Ei-】中且打E-i不构成圈的边屮权最小的边，如果这样的边不存在，算法终止，此
3、时IEi-z
4、二m-l,则T二(V,Em)是最小树；若IEi-i
5、5-1,则说明原图G二(V,E)不是连通的。III令Ei二Ei-iU{ei},iT+1,转步II。定理：G=(V,E)是连通图，则上述Kruskal算法一定有限终止，且终止时得到的子图T一定是图G的最小生成树。①Prim算法：I从任意一个节点i开始,找到离节点i最近的节点jo令Vi={i,j},Ei={(i,j)},称也的节点为连通节点集合，网络屮其余的节点V/二VVi称作非联通节点集。E>={(i,j)}将在最小生成树中。令k二1.II若Vk'S,算法终止,已
6、找到最小生成树，Vk为相应的节点集,Ek为相应的边集;否则从呼中选择一个离Vk最近的成员节点p(如果M中有两个或两个以上的节点离％最近，则从屮选一个；如果柿‘中所有节点均不能与柿连通，则说明图g不是连通的)。设q是表示Vk屮离p最近的节点，则边(p,q)将在最小生成树屮。更新Vk和Vk',令VkH-VkU{p},Vk+i'-Vk'{p},Ew-EkU{(p,q)}。III令k二k+1,转步II。一.C语言源程序：^include^include#defineMAX100#defineMAX
7、COST0x7fffffffintgraph[MAX][MAX];intPrim(intgraph[][MAX],intn)/*lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树*/intlowcost[MAX];/*mst[i]记录对应lowcost[i]的起点,当mst[i]=0时表示起点i加入生成树*/intmst[MAX];inti,j,min,minid,sum=0;/*默认选择1号节点加入生成树，从2号节点开始初始化*/for(i=2;i<=n;i++){/*最短距离初
8、始化为具他节点到1号节点的距离*/lowcost[i]=graph[l][i];/*标记所侑节点的起点皆为默认的1号节点*/mst[i]=1;}/*标记1号节点加入生成树*/mst[1]=0;/*n个节点至少需要n-1条边构成最小生成树*/for(i二2;i<=n;i++){min=MAXCOST;minid=0;/*找满足条件的最小权值边的节点minid*/for(j=2;j<二n;j++){/*边权值较小且不在生成树中*/if(lowcost[j]9、id=j;}}/*输出生成树边的信息:起点，终点，权值*/printf(，z%c-%c:%d",mst[minid]+'A'-1,minid+'A'-1,min);/*累加权值*/sum+=min;/*标记节点minid加入生成树*/lowcost[minid]=0;/*更新当前节点minid到其他节点的权值*/for(j=2;j<=n;j++){/*发现更小的权值*/if(graph[minid][j]10、点*/mst[j]=minid;}}}/*返回最小权值和*/returnsum;intmdin()inti,j,k,m,n;intx,y,cost;charchx,chy;/*读取节点和边的数目*/printff输入连通图的节点和边的数目：〃);scanf(
