《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）（第2版）》教學(xué)課件5-15克魯斯卡爾算法

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：劉斌克魯斯卡爾算法常州信息職業(yè)技術(shù)學(xué)院02教學(xué)目標(biāo)12克魯斯卡爾算法的具體實(shí)現(xiàn)03克魯斯卡爾算法的分析三、鏈表的插入04克魯斯卡爾算法1.5克魯斯卡爾算法實(shí)現(xiàn)具體算法void SortEdge(MGraph *G)/對(duì)Edge中各元素按權(quán)值從小到大排序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

2、.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)/確定頂點(diǎn)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)/克魯斯卡爾算法求最小生成樹(shù)int p1,p2,i,j;int CCNumVertexNum;/標(biāo)記連通

3、分量號(hào)for(i=0;in;i+)CCNumi=i;/初始時(shí)共有n個(gè)連通分量，分量號(hào)分別為0,1,2,.,n-1SortEdge(G);/將邊數(shù)組元素按權(quán)值從小到大排序for(i=0;ie;i+)p1=CCNumLocateVex(G,Edgei.ch1);/p1表示ch1所在連通分量號(hào)p2=CCNumLocateVex(G,Edgei.ch2);/p2表示ch2所在連通分量號(hào)if(p1!=p2)/頂點(diǎn)ch1與頂點(diǎn)ch2只要不在同一個(gè)連通分量，將該邊加入TEprintf(%c,%c)-%dn,Edgei.ch1,Edgei.ch2,Edgei.weight);for(j=0;jn;j+)/將兩

4、個(gè)連通分量合并為一個(gè)連通分量p1if(CCNumj=p2)CCNumj=p1;07克魯斯卡爾算法1.5示例：對(duì)圖G的Edge數(shù)組進(jìn)行按權(quán)值排序，下圖的排序結(jié)果如下：V0V3V1V5V4V25626364751Edge0=(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.5V0V3V1V5V4V25626364751然后選取不在同一個(gè)連通分量的頂點(diǎn)，并將新的邊加入到TE中。并將兩個(gè)連通分量合并成同一個(gè)連通分量。重復(fù)以上操作，直到只有一個(gè)連通分量時(shí)位置。此時(shí)TE便是連通網(wǎng)G最小生成樹(shù)的邊集。結(jié)束算法。 09克魯斯卡爾算法1.5算法分析克魯斯卡爾算法的時(shí)間復(fù)雜度為O(e