管道鋪設(shè)施工的最佳方案問(wèn)題

管道鋪設(shè)施工的最佳方案問(wèn)題管道鋪設(shè)施工的最佳方案問(wèn)題管道鋪設(shè)施工的最佳方案問(wèn)題資料僅供參考文件編號(hào)：2022年4月管道鋪設(shè)施工的最佳方案問(wèn)題版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：?jiǎn)栴}描述：實(shí)驗(yàn)題目：需要在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n-1條管道即可。假設(shè)任意兩個(gè)小區(qū)之間都可以鋪設(shè)管道，但由于地理環(huán)境不同，所需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，這個(gè)問(wèn)題即為求無(wú)向網(wǎng)的最小生成樹(shù)?；疽螅涸诳赡芗僭O(shè)的m條管道中，選取n-1條管道，使得既能連通n個(gè)小區(qū)，又能使總投資最小。每條管道的費(fèi)用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲(chǔ)采用鄰接表的結(jié)構(gòu)。測(cè)試數(shù)據(jù)：使用下圖給出的無(wú)線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。右側(cè)是給出的參考解。簡(jiǎn)述每一部分的對(duì)象、目的和要求：=1\*ROMANI.主函數(shù)部分：對(duì)象：圖G；目的：為圖G分配空間，以作為后續(xù)調(diào)用函數(shù)的參數(shù)；要求：無(wú)。=2\*ROMANII.Create_ALGraph()函數(shù)部分：對(duì)象：頂點(diǎn)，邊及其權(quán)值；目的：將頂點(diǎn)，邊存放在一起，構(gòu)成圖；要求：構(gòu)造頂點(diǎn)表，各頂點(diǎn)的鄰接表以構(gòu)造圖。=3\*ROMANIII.Create_WLGraph()函數(shù)部分：對(duì)象：圖G；目的：將圖中的權(quán)值只存放一次，存放到w指向的結(jié)構(gòu)體中；要求：權(quán)值只存放一次，再分別存放該邊的左右頂點(diǎn)。=4\*ROMANIV.select_info()函數(shù)部分：對(duì)象：w指向的結(jié)構(gòu)體；目的：將該結(jié)構(gòu)體中的各權(quán)值以升序排列；要求：采用簡(jiǎn)單選擇法進(jìn)行排序。=5\*ROMANV.Create_TLGraph()函數(shù)部分：對(duì)象：排序后的w指向的結(jié)構(gòu)體；目的：找到構(gòu)成最小生成樹(shù)的邊；要求：依權(quán)值升序排列，判斷各邊是否構(gòu)成回路來(lái)取舍各邊。需求分析程序所能達(dá)到的基本可能：在n個(gè)小區(qū)m條管道中，選取n-1條管道，實(shí)現(xiàn)連通這n個(gè)小區(qū)，同時(shí)權(quán)值之和為最小。輸入輸出形式及輸入值范圍：程序運(yùn)行后，用戶可根據(jù)提示信息："Pleaseinputtheverticesandtheedges<n,e>:"輸入頂點(diǎn)數(shù)和邊數(shù)，再根據(jù)提示信息："Pleaseinputtheinformationofthevertices<v>:"輸入頂點(diǎn)信息，然后進(jìn)入循環(huán)，創(chuàng)建各個(gè)頂點(diǎn)的鄰接表，即根據(jù)提示信息"Pleaseinputtheinformationofedges<p,q>:"和"Pleaseinputtheinformationofweight:"依次輸入各頂點(diǎn)與其他頂點(diǎn)本身以及兩者之間的權(quán)值，創(chuàng)建圖完畢。用戶輸入完畢后，程序自動(dòng)輸出運(yùn)行結(jié)果。輸入值必須為字母和浮點(diǎn)數(shù)，可以不必區(qū)分大小寫。測(cè)試數(shù)據(jù)要求：用戶輸入字母時(shí)，輸入大寫或小寫，都可以被該程序識(shí)別，正常運(yùn)行。但必須根據(jù)提示信息后面給出的參考形式，有針對(duì)性地輸入逗號(hào)。概要設(shè)計(jì)為了實(shí)現(xiàn)上述功能，該程序以鄰接表來(lái)存儲(chǔ)圖，因此需要圖這個(gè)抽象數(shù)據(jù)類型。圖抽象數(shù)據(jù)類型定義：ADTALGraph{數(shù)據(jù)對(duì)象：D={，i=1,2,3....,n,n}數(shù)據(jù)關(guān)系：R=;基本操作：Create_ALGraph(G)；程序保護(hù)模塊：主函數(shù)模塊圖模塊調(diào)用關(guān)系：3.主要算法流程圖：Create_ALGraph()算法流程圖：Create_WLGraph()算法流程圖：Create_TLGraph()算法流程圖：詳細(xì)設(shè)計(jì)相關(guān)頭文件的調(diào)用說(shuō)明：#include<>#include<>#defineMaxVerNum1002.元素類型、結(jié)點(diǎn)類型和結(jié)點(diǎn)指針類型：staticvoidforcefloat(float*p){floatf=*p;forcefloat(&f);}typedefstructnode{intadjvex;floatinfo;structnode*next;}EdgeNode;typedefstructvnode{charvertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[MaxVerNum];structbian{intz,y;floatinfo;};typedefstruct{charv[MaxVerNum];structbiane[MaxVerNum];}WGraph;structvisit{visited[MaxVerNum];position[MaxVerNum];vvpp[MaxVerNum][MaxVerNum];}3.鄰接表類型：typedefstruct {AdjListadjlist; intn,e; }ALGraph;ertex));G->adjlist[i].firstedge=NULL;/*if(G->adjlist[i].vertex!=''&&G->adjlist[i].vertex!='\n'&&G->adjlist[i].vertex!=' ')x++;*/}for(k=0;k<2*(G->e);k++){printf("Pleaseinputtheinformationofedges<p,q>:\n");getchar();scanf("%c,%c",&p,&q);s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=q-64;i=p-64;getchar();printf("Pleaseinputtheinformationofweight:\n");scanf("%f",&(s->info));s->next=G->adjlist[i-1].firstedge;G->adjlist[i-1].firstedge=s;}/*printf("Pleaseoutputtheinformation:\n");printf("%d,%d\n",G->n,G->e);printf("x=%d\n",x);for(i=0;i<G->n;i++){printf("%c\n",G->adjlist[i].vertex);s=G->adjlist[i].firstedge;while(s!=NULL){printf("thelinbianis%d,theinfois%.1f\n",s->adjvex,s->info);s=s->next;}}*/}intPanduan_Vertex(intk,inti,WGraph*w,EdgeNode*s){intt;for(t=0;t<k;t++)if((w->e[t]).y==i+1&&(w->e[t]).z==s->adjvex)return1;return0;}voidselect_info(WGraph*W,ALGraph*G){inti,j,p,k;floatt;for(i=0;i<(G->e);i++){p=i;for(j=i+1;j<(G->e);j++)if(W->e[j].info<W->e[p].info)p=j;if(p!=i){t=W->e[p].info;W->e[p].info=W->e[i].info;W->e[i].info=t;k=W->e[p].z;W->e[p].z=W->e[i].z;W->e[i].z=k;k=W->e[p].y;W->e[p].y=W->e[i].y;W->e[i].y=k;}}/*for(i=0;i<(G->e);i++)printf("%.1f",W->e[i].info);printf("\n");*/}intjudge_vertex(WGraph*w,inti,structvisit*vp){if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1)return1;elseif(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1)return2;elseif(vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1)return3;elseif(vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].y-1]==1)return4;}voidCreate_TLGraph(WGraph*w,ALGraph*G){WGraphT;inti,j,t,h,k=2;intm=1;intabc,bcd;structvisit*vp;vp=(structvisit*)malloc(sizeof(structvisit));for(i=0;i<(G->n);i++){vp->visited[i]=-1;vp->position[i]=-1;vp->vvpp[i][0]=i+1;for(j=1;j<G->n;j++)vp->vvpp[i][j]=0;}[0]=w->v[w->e[0].z-1];[1]=w->v[w->e[0].y-1];vp->visited[w->e[0].z-1]=1;vp->position[w->e[0].z-1]=w->e[0].z;for(j=0;j<(G->n);j++)if(vp->vvpp[w->e[0].z-1][j]==0){vp->vvpp[w->e[0].z-1][j]=w->e[0].y;break;}vp->visited[w->e[0].y-1]=1;vp->position[w->e[0].y-1]=w->e[0].z;[0].info=w->e[0].info;[0].z=w->e[0].z;[0].y=w->e[0].y;for(i=1;i<(G->e);i++){t=judge_vertex(w,i,vp);if(t==4){if(vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1])continue; else{abc=0;bcd=0; for(j=0;j<G->n;j++) if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0) abc++; for(j=0;j<G->n;j++) if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0) bcd++; for(j=bcd,h=0;j<G->n&&h<abc;j++,h++) {vp->vvpp[(vp->position[w->e[i].z-1])-1][j]=vp->vvpp[(vp->position[w->e[i].y-1])-1][h];vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0; } for(h=bcd;h<abc+bcd;h++) vp->position[(vp->vvpp[vp->position[w->e[i].z-1]-1][h])-1]=vp->position[w->e[i].z-1]; [m].info=w->e[i].info;[m].z=w->e[i].z;[m].y=w->e[i].y;m++; }}elseif(t==1) {vp->visited[w->e[i].z-1]=1; vp->visited[w->e[i].y-1]=1; [k++]=w->v[w->e[i].z-1]; [k++]=w->v[w->e[i].y-1];[m].info=w->e[i].info;[m].z=w->e[i].z;[m].y=w->e[i].y;m++; vp->position[w->e[i].z-1]=w->e[i].z;vp->position[w->e[i].y-1]=w->e[i].z; vp->vvpp[w->e[i].z-1][1]=w->e[i].y; vp->vvpp[w->e[i].y-1][0]=0;}elseif(t==2){vp->visited[w->e[i].z-1]=1;vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1];for(j=0;j<(G->n);j++) if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0) {vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z; break; } vp->vvpp[w->e[i].z-1][0]=0; [k++]=w->v[w->e[i].z-1]; [m].info=w->e[i].info;[m].z=w->e[i].z;[m].y=w->e[i].y;m++;}elseif(t==3){vp->visited[w->e[i].y-1]=1;vp->position[w->e[i].y-1]=vp->position[w->e[i].z-1];for(j=0;j<(G->n);j++) if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]==0) {vp->vvpp[vp->position[w->e[i].z-1]-1][j]=w->e[i].y; break; } vp->vvpp[w->e[i].y-1][0]=0; [k++]=w->v[w->e[i].y-1]; [m].info=w->e[i].info;[m].z=w->e[i].z;[m].y=w->e[i].y;m++; }}printf("Pleaseoutputtheinformation:\n");for(i=0;i<(G->n)-1;i++)printf("(%c,%c)\n",[i].z+64,[i].y+64);}voidCreate_WLGraph(ALGraph*G){inti,j,t,m,k=0;EdgeNode*s,*p;WGraph*W;W=(WGraph*)malloc(sizeof(WGraph));W->v[0]=G->adjlist[0].vertex;s=G->adjlist[0].firstedge;while(s!=NULL){W->e[k].z=1;W->e[k].y=s->adjvex;W->e[k].info=s->info;k++;s=s->next;}for(i=1;i<(G->n);i++){W->v[i]=G->adjlist[i].vertex;s=G->adjlist[i].firstedge;while(s!=NULL){m=Panduan_Vertex(k,i,W,s);if(m==1){s=s->next;continue;}else{W->e[k].z=i+1;W->e[k].y=s->adjvex;W->e[k].info=s->info;k++;s=s->next;}}}/*printf("Pleaseoutputtheinformation:\n");for(i=0;i<G->n;i++)printf("%c\n",W->v[i]);for(i=0;i<G->e;i++)printf("%d,%d,%.1f\n",W->e[i].z,W->e[i].y,W->e[i].info);*/select_info(W,G);Create_TLGraph(W,G);}主函數(shù)的偽碼：main(){ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));Create_ALGraph(G);Create_WLGraph(G);}5.函數(shù)調(diào)用關(guān)系：五．調(diào)試分析1.出現(xiàn)問(wèn)題及解決方法：在剛開(kāi)始寫程序時(shí)，由于考慮不全面，在去除連通圖閉合回路的算法中遇到很大困難，后來(lái)采用以下方法解決了這個(gè)問(wèn)題：將每個(gè)頂點(diǎn)分別放在一個(gè)結(jié)構(gòu)體中，結(jié)構(gòu)體中的數(shù)組visited[i]記錄頂點(diǎn)Vi是否被訪問(wèn)過(guò)的情況，position[i]記錄頂點(diǎn)Vi的具體位置，二維數(shù)組vvpp[i][j]記錄已經(jīng)將以該頂點(diǎn)為左頂點(diǎn)或右頂點(diǎn)的權(quán)值存入T中后，該權(quán)值的右頂點(diǎn)或左頂點(diǎn)的編號(hào)。其具體思想是：只要將一個(gè)權(quán)值存入T中，就將相應(yīng)的左右頂點(diǎn)放到同一個(gè)二維數(shù)組中，之后每欲將一個(gè)權(quán)值加入T中，先檢驗(yàn)該權(quán)值的兩頂點(diǎn)是否在同一個(gè)二維數(shù)組中。若不在，則將該權(quán)值存入T中；若在，將該權(quán)值舍去（因?yàn)樵賹⒃摍?quán)值加入T中，就會(huì)出現(xiàn)回路）。方法優(yōu)缺點(diǎn)分析：優(yōu)點(diǎn)：=1\*GB3①思想比較簡(jiǎn)單，容易令人理解；=2\*GB3②在寫核心算法時(shí)，先將字母頂點(diǎn)用相應(yīng)的數(shù)字代替，所以在將數(shù)字轉(zhuǎn)化成字母回去時(shí)，利用數(shù)字與ASCII碼值的固定差值，可以保證用戶在輸入時(shí)的大小寫字母都可以被該程序識(shí)別。缺點(diǎn)：由于采用數(shù)字來(lái)代替字母，中間的轉(zhuǎn)換關(guān)系比較復(fù)雜，尤其是將對(duì)應(yīng)關(guān)系理清需要足夠的耐心和細(xì)心。3．主要算法的時(shí)間和空間復(fù)雜度分析：（1）由于Create_ALGraph()算法中將讀入頂點(diǎn)的操作執(zhí)行了n次，讀入邊的操作執(zhí)行了2m次，故其時(shí)間復(fù)雜度為O（n+2m）；（2）由于Create_WLGraph()算法將讀入權(quán)值及其左右頂點(diǎn)的操作執(zhí)行了n次，故其時(shí)間復(fù)雜度為O（n）；（3）由于Create_TLGraph()算法中根據(jù)判斷是否構(gòu)成回路來(lái)取舍邊，因?yàn)橛衝條邊，故要執(zhí)行n次，所以時(shí)間復(fù)雜度是O（n）；（4）由于select_info()函數(shù)采用簡(jiǎn)單選擇法排序，時(shí)間復(fù)雜度是O（）；（5）所有算法的空間復(fù)雜度都是O（1）。六．使用說(shuō)明程序運(yùn)行后，用戶根據(jù)提示輸入頂點(diǎn)數(shù)，邊數(shù)，頂點(diǎn)信息，邊的信息，權(quán)值，輸入完畢后程序會(huì)自動(dòng)以頂點(diǎn)對(duì)（i,j）的形式輸出最小生成樹(shù)的邊。七．調(diào)試結(jié)果輸入數(shù)據(jù)：“9”，“15”，“ABCDEFGHI”，“A,B”，“”，“A,C”，“”，“A,H”，“”，“A,I”，“”，“B,A”，“”，“B,C”，“”，“C,A”，“”，“C,B”，“”，“C,D”，“”，“C,E”，“”，“C,G”，“”，“D,C”，“”，“D,E”，“”，“D,F”，“”，“E,C”，“”，“E,D”，“”，“E,F”，“”，“E,G”，“”，“F,D”，“”，“F,E”，“”，“F,I”，“”，“G,C”，“”，“G,E”，“”，“G,H”，“”，“H,A”，“”，“H,G”，“”，“H,I”，“”，“I,A”，“”，“I,F”，“”，“I,H”，“”。(雙引號(hào)不需輸入)輸出數(shù)據(jù)：(B,C),(H,I),(E,G),(A,H),(C,D),(A,B),(C,E),(F,I)運(yùn)行結(jié)果截屏：八．附錄源程序清單：#include<>/*調(diào)用的頭文件庫(kù)說(shuō)明*/#include<>#defineMaxVerNum100staticvoidforcefloat(float*p){floatf=*p;/*由于我的TC中不支持浮點(diǎn)數(shù)，故添加了這個(gè)程序段*/forcefloat(&f);}typedefstructnode/*構(gòu)造鄰接表的結(jié)構(gòu)體*/{intadjvex;floatinfo;/*存放權(quán)值*/structnode*next;/*指向下一個(gè)鄰接點(diǎn)的指針域*/}EdgeNode;typedefstructvnode/*構(gòu)造頂點(diǎn)表的結(jié)構(gòu)體*/{charvertex;/*頂點(diǎn)域*/EdgeNode*firstedge;/*邊表頭指針*/}VertexNode;typedefVertexNodeAdjList[MaxVerNum];typedefstruct/*構(gòu)造圖的結(jié)構(gòu)體*/ {AdjListadjlist;/*鄰接表*/ intn,e;/*頂點(diǎn)數(shù)和邊數(shù)*/ }ALGraph;structbian/*存放權(quán)值及其左右頂點(diǎn)的結(jié)構(gòu)體*/{intz,y;floatinfo;};typedefstruct/*用該結(jié)構(gòu)體來(lái)只存放一次權(quán)值及其相應(yīng)的頂點(diǎn)*/{charv[MaxVerNum];structbiane[MaxVerNum];}WGraph;structvisit/*用該結(jié)構(gòu)體來(lái)存放各結(jié)點(diǎn)被訪問(wèn)的情況，{visited[MaxVerNum];位置，和其他結(jié)點(diǎn)的關(guān)系*/position[MaxVerNum];vvpp[MaxVerNum][MaxVerNum];}Create_ALGraph(ALGraph*G)/*創(chuàng)建圖*/{inti,j;charp,q;intk;EdgeNode*s;chara,b;printf("Pleaseinputtheverticesandtheedges<n,e>:\n");/*輸入頂點(diǎn)數(shù)和邊數(shù)*/scanf("%d,%d",&(G->n),&(G->e));printf("Pleaseinputtheinformationofthevertices<v>:\n");getchar();for(i=0;i<(G->n);i++)/*建立有n各頂點(diǎn)的頂點(diǎn)表*/{scanf("%c",&(G->adjlist[i].vertex));/*讀入頂點(diǎn)信息*/G->adjlist[i].firstedge=NULL;}for(k=0;k<2*(G->e);k++)/*建立邊表*/{printf("Pleaseinputtheinformationofedges<p,q>:\n");getchar();scanf("%c,%c",&p,&q);/*讀入邊的頂點(diǎn)*/s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=q-64;/*鄰接點(diǎn)的序號(hào)為q-64*/i=p-64;getchar();printf("Pleaseinputtheinformationofweight:\n");/*讀入權(quán)值*/scanf("%f",&(s->info));s->next=G->adjlist[i-1].firstedge;/*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部*/G->adjlist[i-1].firstedge=s;}}intPanduan_Vertex(intk,inti,WGraph*w,EdgeNode*s)/*判斷該邊是不是已經(jīng)讀入到w指{intt;向的結(jié)構(gòu)體中*/for(t=0;t<k;t++)if((w->e[t]).y==i+1&&(w->e[t]).z==s->adjvex)return1;return0;}voidselect_info(WGraph*W,ALGraph*G)/*將w指向的結(jié)構(gòu)體中各權(quán)值按升序{inti,j,p,k;排列*/floatt;for(i=0;i<(G->e);i++)/*簡(jiǎn)單選擇排序*/{p=i;for(j=i+1;j<(G->e);j++)if(W->e[j].info<W->e[p].info)p=j;if(p!=i){t=W->e[p].info;/*將兩條邊的權(quán)值左右頂點(diǎn)都進(jìn)行交換*/W->e[p].info=W->e[i].info;W->e[i].info=t;k=W->e[p].z;W->e[p].z=W->e[i].z;W->e[i].z=k;k=W->e[p].y;W->e[p].y=W->e[i].y;W->e[i].y=k;}}/*for(i=0;i<(G->e);i++)printf("%.1f",W->e[i].info);printf("\n");*/}intjudge_vertex(WGraph*w,inti,structvisit*vp)/*判斷頂點(diǎn)的訪問(wèn)情況*/{if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1)return1;elseif(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1)return2;elseif(vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1)return3;elseif(vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].y-1]==1)return4;}voidCreate_TLGraph(WGraph*w,ALGraph*G)/*生成最小生成樹(shù)*/{WGraphT;inti,j,t,h,k=2;intm=1;intabc,bcd;structvisit*vp;vp=(structvisit*)malloc(sizeof(structvisit));for(i=0;i<(G->n);i++)/*將各頂點(diǎn)的被訪問(wèn)情況，位置，與其他頂點(diǎn){vp->visited[i]=-1;的相互關(guān)系進(jìn)行初始化*/vp->position[i]=-1;vp->vvpp[i][0]=i+1;for(j=1;j<G->n;j++)vp->vvpp[i][j]=0;}[0]=w->v[w->e[0].z-1];[1]=w->v[w->e[0].y-1];vp->visited[w->e[0].z-1]=1;vp->position[w->e[0].z-1]=w->e[0].z;for(j=0;j<(G->n);j++)if(vp->vvpp[w->e[0].z-1][j]==0){vp->vvpp[w->e[0].z-1][j]=w->e[0].y;break;}vp->visited[w->e[0].y-1]=1;vp->position[w->e[0].y-1]=w->e[0].z;[0].info=w->e[0].info;[0].z=w->e[0].z;[0].y=w->e[0].y;for(i=1;i<(G->e);i++){t=judge_vertex(w,i,vp);/*根據(jù)不同的頂點(diǎn)訪問(wèn)情況選取相應(yīng)操作*/if(t==4)/*兩頂點(diǎn)均已被訪問(wèn)過(guò)的情況*/{if(vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1])/*兩頂點(diǎn)位置相同*/continue;/*舍去這條邊，否則會(huì)構(gòu)成回路*/ else{abc=0;bcd=0;/*倘若兩頂點(diǎn)位置不同*/ for(j=0;j<G->n;j++) if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0) abc++; for(j=0;j<G->n;j++) if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0) bcd++; for(j=bcd,h=0;j<G->n&&h<abc;j++,h++)將兩頂點(diǎn)放在同一個(gè)數(shù)組中*/ {vp->vvpp[(vp->position[w->e[i].z-1])-1][j]=vp->vvpp[(vp->position[w->e[i].y-1])-1][h];vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0;/*將原數(shù)組置零*/ } for(h=bcd;h<abc+bcd;h++) vp->position[(vp->vvpp[vp->position[w->e[i].z-1]-1][h])-1]=vp->position[w->e[i].z-1]; [m].info=w->e[i].info;/*將該邊存入T中*/[m].z=w->e[i].z;[m].y=w->e[i].y;m++; }}elseif(t==1)/*兩頂點(diǎn)都未被訪問(wèn)的情況*/ {vp->visited[w->e[i].z-1]=1; vp->visited[w->e[i].y-1]=1; [k++]=w->v[w->e[i].z-1]; [k++]=w->v[w->e[i].y-1];[m].info=w->e[i].info;/*將該邊存入T中*/[m].z=w->e[i].z;[m].y=w->e[i].y;m++; vp->position[w->e[i].z-1]=w->e[i].z;/*將兩頂點(diǎn)的位置改為相同*/vp->position[w->e[i].y-1]=w->e[i].z; vp->vvpp[w->e[i].z-1][1]=w->e[i].y;/*將兩頂點(diǎn)存放到一個(gè)數(shù)組中*/ vp->vvpp[w->e[i].y-1][0]=0;}elseif(t==2)/*左頂點(diǎn)未被訪問(wèn)，右頂點(diǎn)已被訪問(wèn)的情況*/{vp->visited[w->e[i].z-1]=1;vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1];/*將左頂點(diǎn)的位置改為右頂點(diǎn)的位置*/for(j=0;j<(G->n);j++)/*將兩頂點(diǎn)存放到一個(gè)數(shù)組中*/ if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0) {vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z; break; } vp->vvpp[w->e[i].z-1][0]=0; [k++]=w->v[w->e[i].z-1]; [m].info=w->e[i].info;