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

1、.一問題描述：1.實(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)的存儲(chǔ)采用鄰接表的結(jié)構(gòu)。3.測(cè)試數(shù)據(jù)：使用下圖給出的無線網(wǎng)數(shù)據(jù)作為程序的輸入， 求出最佳鋪設(shè)方案。 右側(cè)是給出的參考解。4. 簡(jiǎn)述每一部分的對(duì)象、目的和要求：I.

2、 主函數(shù)部分：對(duì)象：圖 G；目的：為圖 G分配空間，以作為后續(xù)調(diào)用函數(shù)的參數(shù)；'.值之和為最小。2.輸入輸出形式及輸入值范圍：程序運(yùn)行后，用戶可根據(jù)提示信息：.要求：無。II. Create_ALGraph( ) 函數(shù)部分：對(duì)象：頂點(diǎn)，邊及其權(quán)值；目的：將頂點(diǎn)，邊存放在一起，構(gòu)成圖；要求：構(gòu)造頂點(diǎn)表，各頂點(diǎn)的鄰接表以構(gòu)造圖。III. Create_WLGraph( ) 函數(shù)部分：對(duì)象：圖 G；目的：將圖中的權(quán)值只存放一次，存放到 w 指向的結(jié)構(gòu)體中；要求：權(quán)值只存放一次，再分別存放該邊的左右頂點(diǎn)。IV. select_info( )函數(shù)部分：對(duì)象： w指向的結(jié)構(gòu)體；目的：將該結(jié)構(gòu)體中的

3、各權(quán)值以升序排列；要求：采用簡(jiǎn)單選擇法進(jìn)行排序。V. Create_TLGraph( ) 函數(shù)部分：對(duì)象：排序后的w 指向的結(jié)構(gòu)體；目的：找到構(gòu)成最小生成樹的邊；要求：依權(quán)值升序排列，判斷各邊是否構(gòu)成回路來取舍各邊。二需求分析1.程序所能達(dá)到的基本可能：在 n 個(gè)小區(qū) m 條管道中，選取n-1 條管道，實(shí)現(xiàn)連通這n 個(gè)小區(qū)，同時(shí)權(quán)"Please input the vertices and theedges<n,e>:"輸入頂點(diǎn)數(shù)和邊數(shù)， 再根據(jù)提示信息： "Please input the information ofthe vertices<

4、v>:"輸入頂點(diǎn)信息，然后進(jìn)入循環(huán)，創(chuàng)建各個(gè)頂點(diǎn)的鄰接表，即根據(jù)提 示 信 息 "Please inputthe informationofedges<p,q>:"和 "Please inputtheinformation of weight:" 依次輸入各頂點(diǎn)與其他頂點(diǎn)本身以及兩者之間的權(quán)值，創(chuàng)建圖完畢。用戶輸入完畢后， 程序自動(dòng)輸出運(yùn)行結(jié)果。 輸入值必須為字母和浮點(diǎn)數(shù)，可以不必區(qū)分大小寫。3.測(cè)試數(shù)據(jù)要求：'.用戶輸入字母時(shí)，輸入大寫或小寫，都可以被該程序識(shí)別，正常運(yùn)行。但必須根據(jù)提示信息后面給出的參考形式，有針對(duì)

5、性地輸入逗號(hào)。三概要設(shè)計(jì)為了實(shí)現(xiàn)上述功能， 該程序以鄰接表來存儲(chǔ)圖， 因此需要圖這個(gè)抽象數(shù)據(jù)類型。1. 圖抽象數(shù)據(jù)類型定義：ADT ALGraph數(shù) 據(jù) 對(duì) 象 ： D=ai , bi ,ci | aiAdjList, biint, ciint，i=1,2,3.,n,n0 數(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)對(duì)（i, j ）的

6、形式輸出ADT ALGraph2.本程序保護(hù)模塊：主函數(shù)模塊圖模塊調(diào)用關(guān)系：主函數(shù)模塊圖模塊3.主要算法流程圖：'.Create_ALGraph( )算法流程圖：.Create_WLGraph()算法流程圖：開始讀入頂點(diǎn)數(shù)和邊數(shù)i=0i<nFT讀入頂點(diǎn)信息i=i+1K=0K<2eT讀入邊 <Vi,Vj>的對(duì)應(yīng)頂點(diǎn)及權(quán)值F開始i=0i<nTFs！ =NULLFT該權(quán)值還未存入 W中FT讀入該權(quán)值及左右頂點(diǎn)編號(hào)s=s->nexti=i+1將新邊表結(jié)點(diǎn)插入到頂點(diǎn) Vi的邊表頭部k=k+1結(jié)束結(jié)束'.Create_TLGraph( )算法流程圖：開始

7、初始化存儲(chǔ)各頂點(diǎn)被訪問情況及位置信息的結(jié)構(gòu)體指針 vpi=1i<e調(diào)用judge_vertex() 函數(shù)若兩頂點(diǎn)都已被訪問過若兩頂點(diǎn)位置不同將該權(quán)值加入T中，并把位置改相同若左頂點(diǎn)未被訪問，右頂點(diǎn)已被訪問若左頂點(diǎn)已被訪問，右頂點(diǎn)未被訪問若兩頂點(diǎn)都未被訪問將該權(quán)值加入 T將該權(quán)值加入 T將該權(quán)值加入 T中，并把左頂點(diǎn)中，并把右頂點(diǎn)中，并把兩頂點(diǎn)的位置改為和右的位置改為和左的位置改為相同頂點(diǎn)相同頂點(diǎn)相同i=i+1輸出最小生成樹的各邊結(jié)束'.四詳細(xì)設(shè)計(jì)1.相關(guān)頭文件的調(diào)用說明：#include<stdio.h>#include<stdlib.h>#define

8、MaxVerNum 1002.元素類型、結(jié)點(diǎn)類型和結(jié)點(diǎn)指針類型：static void forcefloat(float *p)float f = *p;forcefloat(&f);typedef struct node int adjvex; float info;struct node *next;EdgeNode;typedef struct vnode char vertex; EdgeNode *firstedge;VertexNode;typedef VertexNode AdjListMaxVerNum;struct bianint z,y;float info;typ

9、edef structchar vMaxVerNum;struct bian eMaxVerNum;WGraph;struct visit'.visitedMaxVerNum;positionMaxVerNum;vvppMaxVerNumMaxVerNum;3.鄰接表類型：typedef structAdjList adjlist;int n,e;ALGraph;/部分基本操作的偽碼實(shí)現(xiàn)Create_ALGraph(ALGraph *G)int i,j;char p,q;int k; /* int x=0; */EdgeNode *s;char a,b;printf("Ple

10、ase input the vertices and the edges<n,e>:n"); scanf("%d,%d",&(G->n),&(G->e);printf("Please input the information of the vertices<v>:n");getchar();for(i=0;i<(G->n);i+)scanf("%c",&(G->adjlisti.vertex);G->adjlisti.firstedge=N

11、ULL;/*if(G->adjlisti.vertex!=' '&&G->adjlisti.vertex!='n'&&G->adjlisti.vertex!=' ')x+;*/for(k=0;k<2*(G->e);k+)printf("Please input the information of edges<p,q>:n"); getchar();scanf("%c,%c",&p,&q);'.s=(EdgeN

12、ode *)malloc(sizeof(EdgeNode);s->adjvex=q-64;i=p-64;getchar();printf("Please input the information of weight:n");scanf("%f",&(s->info);s->next=G->adjlisti-1.firstedge;G->adjlisti-1.firstedge=s;/*printf("Please output the information:n");printf("%

13、d,%dn",G->n,G->e);printf("x=%dn",x);for(i=0;i<G->n;i+)printf("%cn",G->adjlisti.vertex);s=G->adjlisti.firstedge;while(s!=NULL)printf("the linbian is %d,the info is %.1fn",s->adjvex,s->info); s=s->next;*/int Panduan_Vertex(int k,int i,WGrap

14、h *w,EdgeNode *s)int t;for(t=0;t<k;t+)if(w->et).y=i+1&&(w->et).z=s->adjvex)return 1;return 0;void select_info(WGraph *W,ALGraph *G)int i,j,p,k;'.float t;for(i=0;i<(G->e);i+)p=i;for(j=i+1;j<(G->e);j+)if(W-><W->)p=j;if(p!=i)t=W->;W-&

15、gt;=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;i<(G->e);i+)printf("%.1f ",W->);printf("n");*/int judge_vertex(WGraph *w,int i,struct visit *vp)if(vp->visitedw-&

16、gt;ei.z-1=-1&&vp->visitedw->ei.y-1=-1)return 1;else if(vp->visitedw->ei.z-1=-1&&vp->visitedw->ei.y-1=1)return 2;else if(vp->visitedw->ei.y-1=-1&&vp->visitedw->ei.z-1=1)return 3;else if(vp->visitedw->ei.z-1=1&&vp->visitedw->ei.

17、y-1=1)'.return 4;void Create_TLGraph(WGraph *w,ALGraph *G)WGraph T;int i,j,t,h,k=2;int m=1;int abc,bcd;struct visit *vp;vp=(struct visit *)malloc(sizeof(struct visit);for(i=0;i<(G->n);i+)vp->visitedi=-1;vp->positioni=-1;vp->vvppi0=i+1;for(j=1;j<G->n;j+)vp->vvppij=0;T.v0=w

18、->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;j<(G->n);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.=w->e0.inf

19、o;T.e0.z=w->e0.z;T.e0.y=w->e0.y;for(i=1;i<(G->e);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;for(j=0;j<G->n;j+)if(vp->vvppvp->positionw->ei.y-1-1j!=0)abc+;for(j=0;j<G->n;j+)if(vp->vvpp

20、vp->positionw->ei.z-1-1j!=0)bcd+;for(j=bcd,h=0;j<G->n&&h<abc;j+,h+)vp->vvpp(vp->positionw->ei.z-1)-1j=vp->vvpp(vp->positionw->ei.y-1)-1h;vp->vvppvp->positionw->ei.y-1-1h=0;for(h=bcd;h<abc+bcd;h+)vp->position(vp->vvppvp->positionw->ei.z

21、-1-1h)-1=vp->positionw->ei .z-1;T.=w->;T.em.z=w->ei.z;T.em.y=w->ei.y;m+;else if(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.=w->;T.em.z=w->ei.z;T.em.y=w->ei.y;m+;vp-&g

22、t;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;else if(t=2)vp->visitedw->ei.z-1=1;vp->positionw->ei.z-1=vp->positionw->ei.y-1;for(j=0;j<(G->n);j+)if(vp->vvppvp->positionw->ei.y-1

23、-1j=0)vp->vvppvp->positionw->ei.y-1-1j=w->ei.z;break;vp->vvppw->ei.z-10=0;T.vk+=w->vw->ei.z-1;T.=w->;T.em.z=w->ei.z;T.em.y=w->ei.y;m+;else if(t=3)vp->visitedw->ei.y-1=1;vp->positionw->ei.y-1=vp->positionw->ei.z-1;for(j=0;j<(G->n)

24、;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.=w->;T.em.z=w->ei.z;T.em.y=w->ei.y;m+;printf("Please output the information:n");for(i=0;i<(G-

25、>n)-1;i+)printf("(%c,%c)n",T.ei.z+64,T.ei.y+64);void Create_WLGraph(ALGraph *G)int i,j,t,m,k=0;EdgeNode *s,*p;WGraph *W;W=(WGraph *)malloc(sizeof(WGraph);W->v0=G->adjlist0.vertex;s=G->adjlist0.firstedge;while(s!=NULL)W->ek.z=1;W->ek.y=s->adjvex;W->=s->info

26、;k+;s=s->next;for(i=1;i<(G->n);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;else W->ek.z=i+1;W->ek.y=s->adjvex;W->=s->info;k+;s=s->next;/*printf("Please output the inform

27、ation:n");for(i=0;i<G->n;i+)printf("%cn",W->vi);for(i=0;i<G->e;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)

28、;'.5.函數(shù)調(diào)用關(guān)系：調(diào)用調(diào)用Create_ALGrapPanduan_Verh()函數(shù)tex()函數(shù)main（）調(diào)用調(diào)用調(diào)用Create_WLGrCreate_TLGrjudge_verte函數(shù)aph()函數(shù)aph()函數(shù)x()函數(shù)調(diào)用select_info()函數(shù)五調(diào)試分析1.出現(xiàn)問題及解決方法：在剛開始寫程序時(shí)， 由于考慮不全面， 在去除連通圖閉合回路的算法中遇到很大困難，后來采用以下方法解決了這個(gè)問題：將每個(gè)頂點(diǎn)分別放在一個(gè)結(jié)構(gòu)體中，結(jié)構(gòu)體中的數(shù)組visitedi 記錄頂點(diǎn) Vi是否被訪問過的情況， positioni 記錄頂點(diǎn) Vi 的具體位置，二維數(shù)組vvppij 記錄已

29、經(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)回路） 。2.方法優(yōu)缺點(diǎn)分析：優(yōu)點(diǎn)：思想比較簡(jiǎn)單，容易令人理解；'.在寫核心算法時(shí)， 先將字母頂點(diǎn)用相應(yīng)的數(shù)字代替， 所以在將數(shù)字轉(zhuǎn)化成字母回去時(shí)，利用數(shù)字與 ASCII 碼值的固定差值，可以保證用戶在輸入時(shí)的大小寫字母都可以被該程序識(shí)別。缺點(diǎn)：由于采用數(shù)字來代替字母，中間的

30、轉(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)成回路來取舍邊，因?yàn)橛?n 條邊，故要執(zhí)行 n 次，所以時(shí)間復(fù)雜度是 O（n）；（ 4）由于 select_info( )函數(shù)采用簡(jiǎn)單選擇法排序，時(shí)間復(fù)雜度是O（

31、n2 ）；（ 5）所有算法的空間復(fù)雜度都是O（1）。六使用說明程序運(yùn)行后， 用戶根據(jù)提示輸入頂點(diǎn)數(shù)， 邊數(shù)，頂點(diǎn)信息，邊的信息，權(quán)值，輸入完畢后程序會(huì)自動(dòng)以頂點(diǎn)對(duì)（ 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

32、”，“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”。(雙引號(hào)不需輸入 )輸出數(shù)據(jù)： (B,C),(H,I),(E,G),(A,H),

33、(C,D),(A,B),(C,E),(F,I)運(yùn)行結(jié)果截屏：'.八附錄源程序清單：#include<stdio.h>/* 調(diào)用的頭文件庫(kù)說明*/#include<stdlib.h>#define MaxVerNum 100static void forcefloat(float *p)float f = *p;/* 由于我的 TC 中不支持浮點(diǎn)數(shù)，故添加了這個(gè)程序段*/forcefloat(&f);typedef struct node/* 構(gòu)造鄰接表的結(jié)構(gòu)體*/ int adjvex;float info;/* 存放權(quán)值 */struct node *

34、next;/* 指向下一個(gè)鄰接點(diǎn)的指針域*/EdgeNode;typedef struct vnode/* 構(gòu)造頂點(diǎn)表的結(jié)構(gòu)體*/'. char vertex;/* 頂點(diǎn)域 */EdgeNode *firstedge;/* 邊表頭指針 */VertexNode;typedef VertexNode AdjListMaxVerNum;typedef struct/* 構(gòu)造圖的結(jié)構(gòu)體*/AdjList adjlist;/* 鄰接表 */int n,e;/* 頂點(diǎn)數(shù)和邊數(shù)*/ALGraph;struct bian/* 存放權(quán)值及其左右頂點(diǎn)的結(jié)構(gòu)體*/int z,y;float info;ty

35、pedef struct/* 用該結(jié)構(gòu)體來只存放一次權(quán)值及其相應(yīng)的頂點(diǎn)*/char vMaxVerNum;struct bian eMaxVerNum;WGraph;struct visit/* 用該結(jié)構(gòu)體來存放各結(jié)點(diǎn)被訪問的情況，visitedMaxVerNum;位置，和其他結(jié)點(diǎn)的關(guān)系*/positionMaxVerNum;vvppMaxVerNumMaxVerNum;Create_ALGraph(ALGraph *G)/* 創(chuàng)建圖 */int i,j;char p,q;int k;EdgeNode *s;char a,b;printf("Please input the vert

36、ices and the edges<n,e>:n");/* 輸入頂點(diǎn)數(shù)和邊數(shù)*/scanf("%d,%d",&(G->n),&(G->e);printf("Please input the information of the vertices<v>:n");getchar();for(i=0;i<(G->n);i+)/* 建立有 n 各頂點(diǎn)的頂點(diǎn)表*/scanf("%c",&(G->adjlisti.vertex);/* 讀入頂點(diǎn)信息*/G-&

37、gt;adjlisti.firstedge=NULL;for(k=0;k<2*(G->e);k+)/* 建立邊表 */printf("Please input the information of edges<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("Ple

38、ase input the information of weight:n");/* 讀入權(quán)值 */scanf("%f",&(s->info);'.s->next=G->adjlisti-1.firstedge;/* 將新邊表結(jié)點(diǎn)s 插入到頂點(diǎn)Vi 的邊表頭部 */G->adjlisti-1.firstedge=s;int Panduan_Vertex(int k,int i,WGraph *w,EdgeNode *s)/* 判斷該邊是不是已經(jīng)讀入到w 指int t;向的結(jié)構(gòu)體中 */for(t=0;t<k;t+)if

39、(w->et).y=i+1&&(w->et).z=s->adjvex)return 1;return 0;void select_info(WGraph *W,ALGraph *G)/* 將 w 指向的結(jié)構(gòu)體中各權(quán)值按升序int i,j,p,k;排列 */float t;for(i=0;i<(G->e);i+)/* 簡(jiǎn)單選擇排序*/p=i;for(j=i+1;j<(G->e);j+)if(W-><W->)p=j;if(p!=i)t=W->;/* 將兩條邊的權(quán)值左右頂點(diǎn)都進(jìn)

40、行交換*/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;i<(G->e);i+)printf("%.1f ",W->);printf("n");*/int judge_vertex(WGraph *w,int i,struct visit *vp)/* 判斷頂點(diǎn)的訪問情況

41、*/if(vp->visitedw->ei.z-1=-1&&vp->visitedw->ei.y-1=-1)return 1;else if(vp->visitedw->ei.z-1=-1&&vp->visitedw->ei.y-1=1)return 2;else if(vp->visitedw->ei.y-1=-1&&vp->visitedw->ei.z-1=1)return 3;else if(vp->visitedw->ei.z-1=1&&v

42、p->visitedw->ei.y-1=1)return 4;'.void Create_TLGraph(WGraph *w,ALGraph *G)/* 生成最小生成樹*/WGraph T;int i,j,t,h,k=2;int m=1;int abc,bcd;struct visit *vp;vp=(struct visit *)malloc(sizeof(struct visit);for(i=0;i<(G->n);i+)/* 將各頂點(diǎn)的被訪問情況，位置，與其他頂點(diǎn)vp->visitedi=-1;的相互關(guān)系進(jìn)行初始化*/vp->positioni

43、=-1;vp->vvppi0=i+1;for(j=1;j<G->n;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;j<(G->n);j+)if(vp->vvppw->e0.z-1j=0)vp->vvppw->e0.z-1j=w->e0.y;break;vp->visitedw->e0

44、.y-1=1;vp->positionw->e0.y-1=w->e0.z;T.=w->;T.e0.z=w->e0.z;T.e0.y=w->e0.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->positionw->ei.z-1=vp->positionw->ei.y-1)/* 兩頂點(diǎn)位置相同*/continue;/* 舍去這條邊，否則會(huì)構(gòu)成回路*/e

45、lseabc=0; bcd=0;/* 倘若兩頂點(diǎn)位置不同*/for(j=0;j<G->n;j+)if(vp->vvppvp->positionw->ei.y-1-1j!=0)abc+;for(j=0;j<G->n;j+)if(vp->vvppvp->positionw->ei.z-1-1j!=0)bcd+;for(j=bcd,h=0;j<G->n&&h<abc;j+,h+)將兩頂點(diǎn)放在同一個(gè)數(shù)組中*/vp->vvpp(vp->positionw->ei.z-1)-1j=vp->

46、vvpp(vp->positionw->ei.y-1)-1h;vp->vvppvp->positionw->ei.y-1-1h=0; /*將原數(shù)組置零*/'.for(h=bcd;h<abc+bcd;h+)vp->position(vp->vvppvp->positionw->ei.z-1-1h)-1=vp->positionw->ei.z-1;T.=w->; /* 將該邊存入 T 中 */ T.em.z=w->ei.z;T.em.y=w->ei.y;m+;else if

47、(t=1)/* 兩頂點(diǎn)都未被訪問的情況*/ 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.=w->;/* 將該邊存入T 中 */T.em.z=w->ei.z;T.em.y=w->ei.y;m+;vp->positionw->ei.z-1=w->ei.z;/* 將兩頂點(diǎn)的位置改為相同*/vp->positionw->ei.y-1=w->ei.z;vp->vvppw->ei.z-11=w->ei.y;/* 將兩頂點(diǎn)存放到一個(gè)數(shù)組中*/vp->vvppw->ei.y-10=0;else if(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;j<(G->n);j+)/* 將兩頂點(diǎn)存放到一個(gè)數(shù)組中*/if(