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

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