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

1、WORD整理版優(yōu)質(zhì)參考資料優(yōu)質(zhì)參考資料問題描述：實(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ǎng)的最小生成樹。2基本要求：在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個(gè)小區(qū)，又能使總投資最小。每條管道的費(fèi)用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲采用鄰接表的結(jié)構(gòu)。3測試數(shù)據(jù)：使用下圖給出的無線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。右側(cè)是給出的參考解。4簡述每一部分的對象、目的和要求：主函數(shù)部分：對象

2、：圖G；目的：為圖G分配空間，以作為后續(xù)調(diào)用函數(shù)的參數(shù)；要求：無。Create_ALGraph()函數(shù)部分：對象：頂點(diǎn)，邊及其權(quán)值；目的：將頂點(diǎn)，邊存放在一起，構(gòu)成圖；要求：構(gòu)造頂點(diǎn)表，各頂點(diǎn)的鄰接表以構(gòu)造圖。Create_WLGraph()函數(shù)部分：對象：圖G；目的：將圖中的權(quán)值只存放一次，存放到w指向的結(jié)構(gòu)體中;要求：權(quán)值只存放一次，再分別存放該邊的左右頂點(diǎn)。selectnfo()函數(shù)部分：對象：w指向的結(jié)構(gòu)體；目的：將該結(jié)構(gòu)體中的各權(quán)值以升序排列；要求：采用簡單選擇法進(jìn)行排序。Create_TLGraph()函數(shù)部分：對象：排序后的w指向的結(jié)構(gòu)體；目的：找到構(gòu)成最小生成樹的邊；要求：依權(quán)

3、值升序排列，判斷各邊是否構(gòu)成回路來取舍各邊。需求分析1程序所能達(dá)到的基本可能：在n個(gè)小區(qū)m條管道中，選取n-1條管道，實(shí)現(xiàn)連通這n個(gè)小區(qū)，同時(shí)權(quán)值之和為最小。輸入輸出形式及輸入值范圍：程序運(yùn)行后，用戶可根據(jù)提示信息：Pleaseinputtheverticesandtheedges:輸入頂點(diǎn)數(shù)和邊數(shù)，再根據(jù)提示信息：Pleaseinputtheinformationofthevertices:輸入頂點(diǎn)信息，然后進(jìn)入循環(huán)，創(chuàng)建各個(gè)頂點(diǎn)的鄰接表，即根據(jù)提示信息Pleaseinputtheinformationofedges:和Pleaseinputtheinformationofweight:依次

4、輸入各頂點(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)上述功能，該程序以鄰接表來存儲圖，因此需要圖這個(gè)抽象數(shù)據(jù)類型。1.圖抽象數(shù)據(jù)類型定義：ADTALGraph數(shù)據(jù)對象：D=ai,bi,Ci|aAdjList,int,qint，i=1,2,3.,n,n_0數(shù)據(jù)關(guān)系：R=;基本操作：Create_ALGraph(G);/創(chuàng)建圖Create_WLGraph(G);/

5、將圖G中各頂點(diǎn)以及權(quán)值存放到新圖中，權(quán)值只存放一次selectnfo(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()算法流程圖:開始J讀入頂點(diǎn)數(shù)和邊數(shù)i=0i=01FFT讀入頂點(diǎn)信息i=i+1K=0讀入邊的對應(yīng)頂點(diǎn)及權(quán)值T讀入該權(quán)值及左右頂點(diǎn)編號s=s-nexti=i+1將新邊表結(jié)點(diǎn)插入到頂點(diǎn)Vi的邊表頭部結(jié)束結(jié)束Create_TLGraph()算法流程圖:詳細(xì)設(shè)

6、計(jì)1相關(guān)頭文件的調(diào)用說明：#include#include#defineMaxVerNum1002元素類型、結(jié)點(diǎn)類型和結(jié)點(diǎn)指針類型：staticvoidforcefloat(float*p)floatf=*p;forcefloat(&f);typedefstructnodeintadjvex;floatinfo;structnode*next;EdgeNode;typedefstructvnodecharvertex;EdgeNode*firstedge;VertexNode;typedefVertexNodeAdjListMaxVerNum;structbianint乙y;floatinfo

7、;；typedefstructcharvMaxVerNum;structbianeMaxVerNum;WGraph;structvisitvisitedMaxVerNum;positionMaxVerNum;vvppMaxVerNumMaxVerNum;3鄰接表類型：typedefstructAdjListadjlist;intn,e;ALGraph;/部分基本操作的偽碼實(shí)現(xiàn)Create_ALGraph(ALGraph*G)inti,j;charp,q;intk;/*intx=0;*/EdgeNode*s;chara,b;printf(Pleaseinputtheverticesandthee

8、dges:n);seanf(%d,%d,&(G-n),&(G-e);printf(Pleaseinputtheinformationofthevertiees:n);getehar();for(i=0;in);i+)seanf(%e，&(G-adjlisti.vertex);G-adjlisti.firstedge=NULL;/*if(G-adjlisti.vertex!=&G-adjlisti.vertex!=n&G-adjlisti.vertex!=)x+;*/for(k=0;ke);k+)printf(Pleaseinputtheinformationofedges:n);getehar

9、();scanf(%e,%e,&p,&q);s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=q-64;i=p-64;getehar();printf(Pleaseinputtheinformationofweight:n);scanf(%f,&(s-info);WORD整理版WORD整理版優(yōu)質(zhì)參考資料優(yōu)質(zhì)參考資料s-next=G-adjlisti-1.firstedge;G-adjlisti-1.firstedge=s;/*printf(Pleaseoutputtheinformation:n);printf(%d,%dn,G-n,G-e);prin

10、tf(x=%dn,x);for(i=0;in;i+)printf(%cn,G-adjlisti.vertex);s=G-adjlisti.firstedge;while(s!=NULL)printf(thelinbianis%d,theinfois%.1fn,s-adjvex,s-info);s=s-next;*/intPanduan_Vertex(intk,inti,WGraph*w,EdgeNode*s)intt;for(t=0;tet).y=i+1&(w-et).z=s-adjvex)return1;return0;AJCUr)七ds4u=a)eML:L.&=)七d(+(八0)乂0上)0

11、hnsa.snsa.shnsa.sNSA.SiTr04u=a)eMO4U=a)eMH04u二darAMOJU二darAMHD(llid)七-Ird(04U二da)eMV04u一sAM)七(+r(O)VL+HDO4._Hd)(+(八6)乂0上)04reo匸MdTg(0*lldeo-lWORD整理版WORD整理版優(yōu)質(zhì)參考資料優(yōu)質(zhì)參考資料intjudge_vertex(WGraph*w,inti,structvisit*vp)if(vp_visitedw_ei.z_1=_1&vp_visitedw_ei.y_1=_1)return1;elseif(vp-visitedw-ei.z-1=-1&vp-v

12、isitedw-ei.y-1=1)return2;elseif(vp-visitedw-ei.y-1=-1&vp-visitedw-ei.z-1=1)return3;elseif(vp-visitedw-ei.z-1=1&vp-visitedw-ei.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;in);i+)vp-visi

13、tedi=-1;vp-positioni=-1;vp-vvppi0=i+1;for(j=1;jn;j+)vp-vvppij=O;T.v0=w-vw-e0.z-1;T.v1=w-vw-e0.y-1;vp-visitedw-e0.z-1=1;vp-positionw-e0.z-1=w-e0.z;for(j=0;jn);j+)if(vp-vvppw-e0.z-1j=0)vp-vvppw-e0.z-1j=w-e0.y;break;vp-visitedw-e0.y-1=1;vp-positionw-e0.y-1=w-e0.z;T.=;T.e0.z=w-e0.z;T.e0.

14、y=w-e0.y;for(i=1;ie);i+)t=judge_vertex(w,i,vp);if(t=4)if(vp-positionw-ei.z-1=vp-positionw-ei.y-1)continue;elseabc=0;bcd=0;WORD整理版WORD整理版WORD整理版優(yōu)質(zhì)參考資料優(yōu)質(zhì)參考資料優(yōu)質(zhì)參考資料for(j=0;jn;j+)if(vp-vvppvp-positionw-ei.y-1-1j!=0)abc+;for(j=0;jn;j+)if(vp-vvppvp-positionw-ei.z-1-1j!=0)bcd+;for(j=bcd,h=0;jn&hvvpp(vp-pos

15、itionw-ei.z-1)-1j=vp-vvpp(vp-positionw-ei.y-1)-1h;vp-vvppvp-positionw-ei.y-1-1h=0;for(h=bcd;hposition(vp-vvppvp-positionw-ei.z-1-1h)-1=vp-positionw-ei.z-1;T.=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;elseif(t=1)vp-visitedw-ei.z-1=1;vp-visitedw-ei.y-1=1;T.vk+=w_vw_ei.z_1;T.vk+=w_vw_ei.y_1;T.em.

16、info=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;vp-positionw-ei.z-1=w-ei.z;vp-positionw-ei.y-1=w-ei.z;vp-vvppw-ei.z-11=w-ei.y;vp-vvppw-ei.y-10=0;elseif(t=2)vp-visitedw-ei.z-1=1;vp-positionw-ei.z-1=vp-positionw-ei.y-1;for(j=0;jn);j+)if(vp-vvppvp-positionw-ei.y-1-1j=0)vp-vvppvp-positionw-ei.y-1-1j=w-ei.

17、z;break;vp-vvppw-ei.z-10=0;T.vk+=w_vw_ei.z_1;T.=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;elseif(t=3)vp-visitedw-ei.y-1=1;vp-positionw-ei.y-1=vp-positionw-ei.z-1;for(j=0;jn);j+)if(vp-vvppvp-positionw-ei.z-1-1j=0)vp-vvppvp-positionw-ei.z-1-1j=w-ei.y;break;vp-vvppw-ei.y-10=0;T.vk+=w-vw-ei.y-1;T.

18、=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;WORD整理版WORD整理版優(yōu)質(zhì)參考資料優(yōu)質(zhì)參考資料printf(Pleaseoutputtheinformation:n);for(i=0;in)-1;i+)printf(%c,%c)n,T.ei.z+64,T.ei.y+64);voidCreate_WLGraph(ALGraph*G)inti,j,t,m,k=0;EdgeNode*s,*p;WGraph*W;W=(WGraph*)malloc(sizeof(WGraph);W-v0=G-adjlist0.vertex;s=G-adjlist0

19、.firstedge;while(s!=NULL)W-ek.z=1;W-ek.y=s-adjvex;W-=s-info;k+;s=s-next;for(i=1;in);i+)W-vi=G-adjlisti.vertex;s=G-adjlisti.firstedge;while(s!=NULL)m=Panduan_Vertex(k,i,W,s);if(m=1)s=s-next;continue;elseW-ek.z=i+1;W-ek.y=s-adjvex;W-=s-info;k+;s=s-next;/*printf(Pleaseoutputtheinformation

20、:n);for(i=0;in;i+)printf(%cn,W-vi);for(i=0;ie;i+)printf(%d,%d,%.1fn,W-ei.z,W-ei.y,W-);*/select_info(W,G);Create_TLGraph(W,G);4.主函數(shù)的偽碼:main()ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph);Create_ALGraph(G);Create_WLGraph(G);5.函數(shù)調(diào)用關(guān)系：調(diào)用select_info()函數(shù)調(diào)試分析1出現(xiàn)問題及解決方法：在剛開始寫程序時(shí)，由于考慮不全面，在去除連通圖閉合回路的算法中

21、遇到WORD整理版WORD整理版優(yōu)質(zhì)參考資料優(yōu)質(zhì)參考資料很大困難，后來采用以下方法解決了這個(gè)問題：將每個(gè)頂點(diǎn)分別放在一個(gè)結(jié)構(gòu)體中，結(jié)構(gòu)體中的數(shù)組visitedi記錄頂點(diǎn)Vi是否被訪問過的情況，positioni記錄頂點(diǎn)Vi的具體位置，二維數(shù)組vvppij記錄已經(jīng)將以該頂點(diǎn)為左頂點(diǎn)或右頂點(diǎn)的權(quán)值存入T中后，該權(quán)值的右頂點(diǎn)或左頂點(diǎn)的編號。其具體思想是：只要將一個(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中，就會出現(xiàn)回路)。2方法優(yōu)缺點(diǎn)分析：優(yōu)點(diǎn)：思

22、想比較簡單，容易令人理解；在寫核心算法時(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ù)雜度分析：由于Create_ALGraph()算法中將讀入頂點(diǎn)的操作執(zhí)行了n次，讀入邊的操作執(zhí)行了2m次，故其時(shí)間復(fù)雜度為O(n+2m);由于Create_WLGraph()算法將讀入權(quán)值及其左右頂點(diǎn)的操作執(zhí)行了n次，故其時(shí)間復(fù)雜度為O(n);由于Create_TLGraph()算法中根據(jù)

23、判斷是否構(gòu)成回路來取舍邊，因?yàn)橛衝條邊，故要執(zhí)行n次，所以時(shí)間復(fù)雜度是O(n);由于selectnfo()函數(shù)采用簡單選擇法排序，時(shí)間復(fù)雜度是O(n2)；所有算法的空間復(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,l”，“18.2”，“B,A”，“32.8”，“B,C”，“5.9”，“C,A”，“44.6”，“C,B”，“5.9”，“c,D

24、”，“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”,“79.2”，“G,C”，“56.4”,“H,G”，“52.5”，“H,l”，(雙引號不需輸入)“E,G”，“10.5”，“F,D”,“98.7”，“F,E”，“85.6”，“F,l”,“G,E”，“10.5”，“G,H”，“52.5”，“H,A”，“12.1”,“8.7”,“I,A”,“18.2”,“l(fā),F”,“79.2”,“l(fā),H”,“8.7”輸出數(shù)據(jù)：(B,C),(H

25、,I),(E,G),(A,H),(C,D),(A,B),(C,E),(F,I)運(yùn)行結(jié)果截屏:swwswsswsswswwswssws=錄aA2A5AasAABAaAA2AA2aaACIGHDBEI附ale-ece5E0-eHe-eAe二Ga-ele?eAe二Fe-67ezz-:L*191i.&l1.0Li.21izllii(l&L!-iiBHEACACF卩卩戸7卩侖丘戸心戸九卩匚戸卩3:卩萱卩”卩5:戸：1:卩卩1戸丄戸1丘7戸1卩00卩|A源程序清單:#include#include/*調(diào)用的頭文件庫說明*/#defineMaxVerNum100staticvoidforcefloat(fl

26、oat*p)floatf=*p;forcefloat(&f);typedefstructnodeintadjvex;floatinfo;structnode*next;EdgeNode;/*由于我的TC中不支持浮點(diǎn)數(shù)，故添加了這個(gè)程序段*/*構(gòu)造鄰接表的結(jié)構(gòu)體*/*存放權(quán)值*/*指向下一個(gè)鄰接點(diǎn)的指針域*/*構(gòu)造頂點(diǎn)表的結(jié)構(gòu)體*/*頂點(diǎn)域*/*邊表頭指針*/typedefstructvnodecharvertex;EdgeNode*firstedge;VertexNode;typedefVertexNodeAdjListMaxVerNum;/*構(gòu)造圖的結(jié)構(gòu)體*/*鄰接表*/*頂點(diǎn)數(shù)和邊數(shù)*/t

27、ypedefstructAdjListadjlist;intn,e;ALGraph;structbianint乙y;floatinfo;typedefstructcharvMaxVerNum;structbianeMaxVerNum;WGraph;structvisit/*存放權(quán)值及其左右頂點(diǎn)的結(jié)構(gòu)體*/*用該結(jié)構(gòu)體來只存放一次權(quán)值及其相應(yīng)的頂點(diǎn)*/visitedMaxVerNum;positionMaxVerNum;vvppMaxVerNumMaxVerNum;Create_ALGraph(ALGraph*G)inti,j;charp,q;intk;/*用該結(jié)構(gòu)體來存放各結(jié)點(diǎn)被訪問的情況,位

28、置，和其他結(jié)點(diǎn)的關(guān)系*/*創(chuàng)建圖*/EdgeNode*s;chara,b;printf(Pleaseinputtheverticesandtheedges:n);/*輸入頂點(diǎn)數(shù)和邊數(shù)*/scanf(%d,%d,&(G-n),&(G-e);printf(Pleaseinputtheinformationofthevertices:n);getchar();for(i=0;in);i+)scanf(%c,&(G-adjlisti.vertex);G-adjlisti.firstedge=NULL;for(k=0;ke);k+)/*建立有n各頂點(diǎn)的頂點(diǎn)表*/*讀入頂點(diǎn)信息*/*建立邊表*/print

29、f(Pleaseinputtheinformationofedges:n);getchar();scanf(%c,%c,&p,&q);/*讀入邊的頂點(diǎn)*/s=(EdgeNode*)malloc(sizeof(EdgeNode);s_adjvex=q_64;i=p-64;/*鄰接點(diǎn)的序號為q-64*/getchar();printf(Pleaseinputtheinformationofweight:n);/*讀入權(quán)值*/*判斷該邊是不是已經(jīng)讀向的結(jié)構(gòu)體中*/*將w指向的結(jié)構(gòu)體中各權(quán)值排列*/*簡單選擇排序*/*將兩條邊的權(quán)值左右頂點(diǎn)都進(jìn)行交換*/scanf(%f,&(s_info);s-nex

30、t=G-adjlisti-1.firstedge;/*將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部*/G-adjlisti-1.firstedge=s;intPanduan_Vertex(intk,inti,WGraph*w,EdgeNode*s)入到w指intt;for(t=0;tet).y=i+1&(w_et).z=s_adjvex)return1;return0;voidselect_info(WGraph*W,ALGraph*G)按升序inti,j,p,k;floatt;for(i=0;ie);i+)p=i;for(j=i+1;je);j+)if(W-)p=j;i

31、f(p!=i)t=W-;W-=W-;W-=t;k=W-ep.z;W-ep.z=W-ei.z;W-ei.z=k;k=W-ep.y;W-ep.y=W-ei.y;W-ei.y=k;/*for(i=0;ie);i+)printf(%.1f,W-);printf(n);*/intjudge_vertex(WGraph*w,inti,structvisit*vp)/*判斷頂點(diǎn)的訪問情況*/if(vp-visitedw-ei.z-1=-1&vp-visitedw-ei.y-1=-1)return1;elseif(vp-visitedw-e

32、i.z-1=-1&vp-visitedw-ei.y-1=1)return2;elseif(vp-visitedw-ei.y-1=-1&vp-visitedw-ei.z-1=1)return3;elseif(vp-visitedw-ei.z-1=1&vp-visitedw-ei.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

33、);for(i=0;in);i+)/*將各頂點(diǎn)的被訪問情況，位置，與其他頂點(diǎn)vp-visitedi=-1;的相互關(guān)系進(jìn)行初始化*/vp-positioni=-1;vp-vvppi0=i+1;for(j=1;jn;j+)vp-vvppij=0;T.v0=w-vw-e0.z-1;T.v1=w-vw-e0.y-1;vp-visitedw-e0.z-1=1;vp-positionw-e0.z-1=w-e0.z;for(j=0;jn);j+)if(vp-vvppw-e0.z-1j=0)vp-vvppw-e0.z-1j=w-e0.y;break;vp-visitedw-e0.y-1=1;vp-positi

34、onw_e0.y_1=w_e0.z;T.=;T.e0.z=w-e0.z;T.e0.y=w-e0.y;for(i=1;ie);i+)TOC o 1-5 h zt=judge_vertex(w,i,vp);/*根據(jù)不同的頂點(diǎn)訪問情況選取相應(yīng)操作*/if(t=4)/*兩頂點(diǎn)均已被訪問過的情況*/if(vp-positionw-ei.z-1=vp-positionw-ei.y-1)/*兩頂點(diǎn)位置相同*/continue;/*舍去這條邊，否則會構(gòu)成回路*/elseabc=0;bcd=0;/*倘若兩頂點(diǎn)位置不同*/for(j=0;jn;j+)if(vp-vvppvp-pos

35、itionw_ei.y_1_1j!=0)abc+;for(j=0;jn;j+)if(vp-vvppvp-positionw-ei.z-1-1j!=0)bcd+;將兩頂點(diǎn)放在同一個(gè)數(shù)組for(j=bcd,h=0;jn&hvvpp(vp-positionw-ei.z-1)-1j=vp-vvpp(vp-positionw_ei.y_1)-1h；vp-vvppvp-positionw-ei.y-1-1h=0;/*將原數(shù)組置零*/for(h=bcd;hposition(vp_vvppvp_positionw-ei.z-1-1h)-1=vp-positionw-ei.z-1;T.=w-ei.

36、info;/*將該邊存入T中*/T.em.z=w-ei.z;T.em.y=w_ei.y;m+;elseif(t=1)/*兩頂點(diǎn)都未被訪問的情況*/vp_visitedw_ei.z_1=1;vp_visitedw_ei.y_1=1;T.vk+=w_vw_ei.z_1;/*將該邊存入T中*/*將兩頂點(diǎn)的位置改為相同*/*將兩頂點(diǎn)存放到一個(gè)數(shù)組中*/T.vk+=w_vw_ei.y_1;T.=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;vp-positionw-ei.z-1=w-ei.z;vp-positionw_ei.y_1=w_ei.z;vp_vvppw_ei.z_11=w_ei.y;vp-vvppw-ei.y-10=0;elseif(t=2)/*左頂點(diǎn)未被訪問，右頂點(diǎn)已被訪問的情況*/vp_visitedw_ei.z_1=1;vp-positionw-ei.z-1=vp-positionw-ei.y-1;/*將左頂點(diǎn)的位置改為右頂點(diǎn)的位置*/for(j=0;jn);j+)/*將兩頂點(diǎn)存放到一個(gè)數(shù)組中*/if(vp-vvppvp-positionw-ei.y-1-1j=0)vp-vvppvp-posi