资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：,刘斌,克鲁斯卡尔算法,常州信息职业技术学院,02,教,学,目标,1,2,克鲁斯卡尔算法的具体实现,03,克鲁斯卡尔算法的分析,三、链表的插入,04,克鲁斯卡尔算法,1.5,克鲁斯卡尔算法,实现,具体算法,void,SortEdge(MGraph *G),/,对,Edge,中各元素按权值从小到大排序,int,i,j,temp;,char,ch;,for,(i=0;ie;i+),for,(j=i+1;je;j+),if,(Edgei.weightEdgej.weight),temp=Edgei.weight;,Edgei.weight=Edgej.weight;,Edgej.weight=temp;,ch=Edgei.ch1;,Edgei.ch1=Edgej.ch1;,Edgej.ch1=ch;,ch=Edgei.ch2;,Edgei.ch2=Edgej.ch2;,Edgej.ch2=ch;,05,克鲁斯卡尔算法,1.5,具体算法,int,LocateVex(MGraph *G,VertexType ch),/,确定顶点,ch,在图,G-vexs,中的位置,int,i,k;,for,(i=0;in;i+),if,(G-vexsi=ch),k=i;,return,k;,06,克鲁斯卡尔算法,1.5,具体算法,void,KruskalMST(MGraph *G),/,克鲁斯卡尔算法求最小生成树,int,p1,p2,i,j;,int,CCNumVertexNum;,/,标记连通分量号,for,(i=0;in;i+),CCNumi=i;,/,初始时共有,n,个连通分量，分量号分别为,0,1,2,.,n-1,SortEdge(G);,/,将边数组元素按权值从小到大排序,for,(i=0;ie;i+),p1=CCNumLocateVex(G,Edgei.ch1);,/p1,表示,ch1,所在连通分量号,p2=CCNumLocateVex(G,Edgei.ch2);,/p2,表示,ch2,所在连通分量号,if,(p1!=p2),/,顶点,ch1,与顶点,ch2,只要不在同一个连通分量，将该边加入,TE,printf(%c,%c)-%dn,Edgei.ch1,Edgei.ch2,Edgei.weight);,for,(j=0;jn;j+),/,将两个连通分量合并为一个连通分量,p1,if,(CCNumj=p2),CCNumj=p1;,07,克鲁斯卡尔算法,1.5,示例：,对图,G,的,Edge,数组进行按权值排序，下图的排序结果如下：,V0,V3,V1,V5,V4,V2,5,6,2,6,3,6,4,7,5,1,Edge0=(v0,v2,1),，,Edge1=(v3,v5,2),，,Edge2=(v1,v4,3),，,Edge3=(v2,v5,4),，,Edge4=(v0,v3,5),，,Edge5=(v1,v2,5),，,Edge6=(v0,v1,6),，,Edge7=(v2,v4,6),，,Edge8=(v4,v5,6),，,Edge9=(v2,v3,7),。,08,克鲁斯卡尔算法,1.5,V0,V3,V1,V5,V4,V2,5,6,2,6,3,6,4,7,5,1,然后选取不在同一个连通分量的顶点，并将新的边加入到,TE,中。,并将两个连通分量合并成同一个连通分量。,重复以上操作，直到只有一个连通分量时位置。此时,TE,便是连通网,G,最小生成树的边集。结束算法。,09,克鲁斯卡尔算法,1.5,算法分析,克鲁斯卡尔算法的时间复杂度为,O(elge),，即克鲁斯卡尔算法的时间复杂度取决于边数,e,，所以克鲁斯卡尔算法适合于对边数较少的稀疏图求最小生成树。,THANKS,2016.9.18,
展开阅读全文