管道鋪設(shè)施工的最佳方案問(wèn)題-資料下載頁(yè)
2025-08-11 07:30本頁(yè)面
【正文】 / {if(vpposition[we[i].z1]==vpposition[we[i].y1]) /*兩頂點(diǎn)位置相同*/ continue。 /*舍去這條邊，否則會(huì)構(gòu)成回路*/ else{ abc=0。 bcd=0。 /*倘若兩頂點(diǎn)位置不同*/ for(j=0。jGn。j++) if(vpvvpp[vpposition[we[i].y1]1][j]!=0) abc++。 for(j=0。jGn。j++) if(vpvvpp[vpposition[we[i].z1]1][j]!=0) bcd++。 for(j=bcd,h=0。jGnamp。amp。habc。j++,h++) 將兩頂點(diǎn)放在同一個(gè)數(shù)組中*/ {vpvvpp[(vpposition[we[i].z1])1][j]=vpvvpp[(vpposition[we[i].y1])1][h]。 vpvvpp[vpposition[we[i].y1]1][h]=0。 /*將原數(shù)組置零*/ } for(h=bcd。habc+bcd。h++) vpposition[(vpvvpp[vpposition[we[i].z1]1][h])1]=vpposition[we[i].z1]。 [m].info=we[i].info。 /*將該邊存入T中*/ [m].z=we[i].z。 [m].y=we[i].y。 m++。 } } else if(t==1) /*兩頂點(diǎn)都未被訪問(wèn)的情況*/ { vpvisited[we[i].z1]=1。 vpvisited[we[i].y1]=1。 [k++]=wv[we[i].z1]。 [k++]=wv[we[i].y1]。 [m].info=we[i].info。 /*將該邊存入T中*/ [m].z=we[i].z。 [m].y=we[i].y。 m++。 vpposition[we[i].z1]=we[i].z。 /*將兩頂點(diǎn)的位置改為相同*/ vpposition[we[i].y1]=we[i].z。 vpvvpp[we[i].z1][1]=we[i].y。 /*將兩頂點(diǎn)存放到一個(gè)數(shù)組中*/ vpvvpp[we[i].y1][0]=0。 } else if(t==2) /*左頂點(diǎn)未被訪問(wèn)，右頂點(diǎn)已被訪問(wèn)的情況*/ {vpvisited[we[i].z1]=1。 vpposition[we[i].z1]=vpposition[we[i].y1]。 /*將左頂點(diǎn)的位置改為右頂點(diǎn)的位置*/ for(j=0。j(Gn)。j++) /*將兩頂點(diǎn)存放到一個(gè)數(shù)組中*/ if(vpvvpp[vpposition[we[i].y1]1][j]==0) {vpvvpp[vpposition[we[i].y1]1][j]=we[i].z。 break。 } vpvvpp[we[i].z1][0]=0。 [k++]=wv[we[i].z1]。 [m].info=we[i].info。 /*將該邊存放到T中*/ [m].z=we[i].z。 [m].y=we[i].y。 m++。 } else if(t==3) /*右頂點(diǎn)未被訪問(wèn)，左頂點(diǎn)已被訪問(wèn)的情況*/ {vpvisited[we[i].y1]=1。 vpposition[we[i].y1]=vpposition[we[i].z1]。 /*將右頂點(diǎn)的位置改為左頂點(diǎn)的位置*/ for(j=0。j(Gn)。j++) /*將兩頂點(diǎn)存放到一個(gè)數(shù)組中*/ if(vpvvpp[vpposition[we[i].z1]1][j]==0) {vpvvpp[vpposition[we[i].z1]1][j]=we[i].y。 break。 } vpvvpp[we[i].y1][0]=0。 [k++]=wv[we[i].y1]。 [m].info=we[i].info。 /*將該邊存放到T中*/ [m].z=we[i].z。 [m].y=we[i].y。 m++。 } }printf(Please output the information:\n)。for(i=0。i(Gn)1。i++) /*以頂點(diǎn)對(duì)的形式輸出最小生成樹(shù)*/printf((%c,%c)\n,[i].z+64,[i].y+64)。}void Create_WLGraph(ALGraph *G) /*將各邊的權(quán)值只存一次到w指向的結(jié)構(gòu)體中*/{int i,j,t,m,k=0。 EdgeNode *s,*p。 WGraph *W。 W=(WGraph *)malloc(sizeof(WGraph))。 Wv[0]=Gadjlist[0].vertex。 s=Gadjlist[0].firstedge。 /*將以頂點(diǎn)A為頂點(diǎn)的邊存放到w指向的結(jié)構(gòu)體中*/ while(s!=NULL) {We[k].z=1。 We[k].y=sadjvex。 We[k].info=sinfo。 k++。 s=snext。 } for(i=1。i(Gn)。i++) {Wv[i]=Gadjlist[i].vertex。 s=Gadjlist[i].firstedge。 while(s!=NULL) {m=Panduan_Vertex(k,i,W,s)。 /*調(diào)用該函數(shù)確定該邊權(quán)值是否是重復(fù)出現(xiàn)*/ if(m==1) /*若是，直接跳過(guò)*/ {s=snext。 continue。} else /*若不是，將該邊存放到w指向的結(jié)構(gòu)體中*/ { We[k].z=i+1。 We[k].y=sadjvex。 We[k].info=sinfo。 k++。 s=snext。 } } } select_info(W,G)。 /*調(diào)用該函數(shù)給權(quán)值排升序*/ Create_TLGraph(W,G)。 /*調(diào)用該函數(shù)確定最小生成樹(shù)*/}main(){ALGraph *G。 G=(ALGraph *)malloc(sizeof(ALGraph))。 Create_ALGraph(G)。 /*創(chuàng)建圖*/ Create_WLGraph(G)。}24
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1