圖的遍歷和生成樹(shù)求解實(shí)現(xiàn)的課程結(jié)構(gòu)設(shè)計(jì)-資料下載頁(yè)
2025-06-26 15:35本頁(yè)面
【正文】 值 //prevex[]存儲(chǔ)最短路徑的前一個(gè)結(jié)點(diǎn) int i,j,k,min。 for(i=2。i=n。i++) //n個(gè)頂點(diǎn)，n1條邊 { lowcost[i]=g[1][i]。 //初始化 prevex[i]=1。 //頂點(diǎn)未加入到最小生成樹(shù)中 } lowcost[1]=0。 //標(biāo)志頂點(diǎn)1加入U(xiǎn)集合 for(i=2。i=n。i++) //形成n1條邊的生成樹(shù) { min=inf。 k=0。 for(j=2。j=n。j++) //尋找滿(mǎn)足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊 if((lowcost[j]min)amp。amp。(lowcost[j]!=0)) { min=lowcost[j]。 k=j。 } cout(prevex[k]1,k1)min。 lowcost[k]=0。 //頂點(diǎn)k加入U(xiǎn) for(j=2。j=n。j++) //修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值 if(g[k][j]lowcost[j]) { lowcost[j]=g[k][j]。 prevex[j]=k。 } coutendl。 } return 0。}//最小生成樹(shù)的克魯斯卡爾算法int acrvisited[max]。//克魯斯卡爾弧標(biāo)記數(shù)組int find(int acrvisited[],int f){ while(acrvisited[f]0)f=acrvisited[f]。 return f。}typedef struct acr{ int pre。//弧的一結(jié)點(diǎn) int bak。//弧另一結(jié)點(diǎn) int weight。//弧的權(quán)}edg。void MiniSpanTREE_KRUSCAL(MGraph_L G,ALGraph gra){ edg edgs[max]。 int i,j,k=0。 for(i=0。i!=。++i) for(j=i。j!=。++j) { if([i][j].adj!=int_max) { edgs[k].pre=i。 edgs[k].bak=j。 edgs[k].weight=[i][j].adj。 ++k。 } } int x,y,m,n。 int buf,edf。 for(i=0。i!=。++i) acrvisited[i]=0。 for(j=0。j!=。++j) { m=int_max。 for(i=0。i!=。++i) { if(edgs[i].weightm) { m=edgs[i].weight。 x=edgs[i].pre。 y=edgs[i].bak。 n=i。 } } buf=find(acrvisited,x)。 edf=find(acrvisited,y)。 edgs[n].weight=int_max。 if(buf!=edf) { acrvisited[buf]=edf。 cout(x,y)m。 coutendl。 } }}int main(){ int s。 char y=39。y39。 cout||164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。菜單164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。||endl。 cout||【0、創(chuàng)建一個(gè)無(wú)向圖||endl。 cout||【顯示該圖的鄰接矩陣||endl。 cout||【顯示該圖的鄰接表||endl。 cout||【廣度優(yōu)先遍歷||endl。 cout||【深度優(yōu)先遍歷||endl。 cout||【連通分量||endl。 cout||【最小生成樹(shù)MiniSpanTree_PRIM算法||endl。 cout||【最小生成樹(shù)MiniSpanTree_KRUSCAL算法||endl。 cout||164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。164。||endl。 cout\t\t\t在求最小生成樹(shù)前請(qǐng)先求連通分量!endl。 while(y==39。y39。) { cout請(qǐng)選擇菜單：endl。 cins。 if(s==0) { ++o。 if(o==2) { n=0。 l=0。 o=0。 } } switch(s) { case 0:cout創(chuàng)建一個(gè)無(wú)向圖：endl。 MGraph_L G。 creatMGraph_L(G)。 ALGraph gra。 creatadj(gra,G)。 break。 case 1:cout鄰接矩陣顯示如下：endl。 ljjzprint(G)。 break。 case 2: cout鄰接表顯示如下：endl。 adjprint(gra,G)。 break。 case 3: cout廣度優(yōu)先遍歷：。 BFSTraverse(gra)。 coutendl。 break。 case 4: cout深度優(yōu)先遍歷：。 DFStra(gra)。 coutendl。 break。 case 5:cout連通分量:endl。 DFSTraverse_fen(gra)。 break。 case 6: if(n==0){cout無(wú)權(quán)圖沒(méi)有最小生成樹(shù)。break。} else if(l1){cout若該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)時(shí)，最小生成樹(shù)不存在endl。break。} else { int i,g[max][max]。 for(i=0。i!=。++i) for(int j=0。j!=。++j) g[i+1][j+1]=[i][j].adj。 cout普利姆算法:endl。 MiniSpanTree_PRIM(g,)。 break。 } case 7:if(n==0){cout無(wú)權(quán)圖沒(méi)有最小生成樹(shù)。break。} else if(l1){cout該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)，最小生成樹(shù)不存在endl。break。} else { cout克魯斯卡爾算法:endl。 MiniSpanTREE_KRUSCAL(G,gra)。 break。 } } coutendl是否繼續(xù)？y/n:。 ciny。 if(y==39。n39。) break。 } return 0。}33
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1