數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn) 第七章

1、第7章 圖圖是另一種重要的非線性結(jié)構(gòu),它比樹(shù)的結(jié)構(gòu)更復(fù)雜,更靈活。習(xí)題中涉及到圖的兩種常用的存儲(chǔ)結(jié)構(gòu)即圖的鄰接矩陣和鄰接鏈表。這些習(xí)題的目的主要讓讀者掌握?qǐng)D的深度遍歷和廣度遍歷的算法,同時(shí)加深對(duì)圖的幾個(gè)應(yīng)用問(wèn)題的算法的理解。7.1習(xí)題解析【習(xí)題1】連通圖上實(shí)現(xiàn)廣度優(yōu)先遍歷題目要求:在以鄰接鏈表為存儲(chǔ)結(jié)構(gòu)的無(wú)向圖上,實(shí)現(xiàn)無(wú)向圖的廣度優(yōu)先遍歷算法。【習(xí)題1】和【習(xí)題2】是在連通圖上實(shí)現(xiàn)圖的廣度優(yōu)先遍歷算法和深度優(yōu)先遍歷算法。這兩個(gè)算法同樣適用于對(duì)非連通圖的遍歷,稍加分析和設(shè)計(jì),就可計(jì)算出非連通圖上有幾個(gè)連通分量并給出對(duì)每個(gè)連通分量的遍歷結(jié)果。程序的實(shí)現(xiàn)留給讀者自己完成。結(jié)構(gòu)說(shuō)明:#defineVE

2、XTYPEint#defineMAXLEN40typedefstructnode3/表結(jié)點(diǎn)結(jié)構(gòu)/intadjvex;/存放與表頭結(jié)點(diǎn)相鄰接的頂點(diǎn)在數(shù)組中的序號(hào)/structnode3next;/指向與表頭結(jié)點(diǎn)相鄰接的下一個(gè)頂點(diǎn)的表結(jié)點(diǎn)/EDGENODE;typrdefstructEXTYPEvertex;/存放圖中頂點(diǎn)的信息/EDGENODElink;/指針指向?qū)?yīng)的單鏈表中的表結(jié)點(diǎn)/VEXNODE;typedefstruct 第7章圖l77EXNODEadjlistMAXLEN;/鄰接鏈表表頭向量/intvexnum,arcnum;/頂點(diǎn)數(shù)和邊數(shù)/intkind;/圖的類型/ADJGRAPH

3、;舉例說(shuō)明:設(shè)有連通圖如圖71所示,頂點(diǎn)值設(shè)定為V1=100,V2=200,V3=300,V4=400,V5=500,V6=600,V7=700,V8=800,8個(gè)頂點(diǎn)和9條邊的編號(hào)如圖71所示。圖7.1連通圖數(shù)據(jù)輸入過(guò)程如圖72所示。圖7.2數(shù)據(jù)輸入輸出結(jié)果如圖73所示。l78數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)圖7.3輸出結(jié)果注意:此連通圖鄰接鏈表結(jié)構(gòu)的建立過(guò)程是依賴于圖7.1中8個(gè)頂點(diǎn)和9條邊的編號(hào)。頂點(diǎn)和邊的編號(hào)可以預(yù)先規(guī)定,編法不同,則數(shù)據(jù)輸入的過(guò)程和輸出的結(jié)果也會(huì)不同,但廣度優(yōu)先遍歷算法的結(jié)果都是正確的?！窘獯稹?includedatastru.h#include#includeADJGRAPH

4、creat_adjgraph()EDGENODEp;inti,s,d;ADJGRAPHadjg;adjg.kind=2;printf(nn輸入頂點(diǎn)數(shù)和邊數(shù)(用逗號(hào)隔開(kāi)):);scanf(%d,%d,&s,&d);fflush(stdin);adjg.vexnum=s;/存放頂點(diǎn)數(shù)在adjg.vexnum中/adjg.arcnum=d;/存放邊點(diǎn)數(shù)在adjg.arcnum中/printf(nn);for(i=0;iadjg.vexnum;i+)第7章圖l79printf(輸入頂點(diǎn)%d的值:,i+1);scanf(%d,&adjg.adjlisti.vertex);/輸入頂點(diǎn)的值/fflush(s

5、tdin);adjg.adjlisti.link=NULL;printf(nn);for(i=0;iadjg.arcnum;i+)printf(輸入第%d條邊的起始頂點(diǎn)和終止頂點(diǎn)(用逗號(hào)隔開(kāi)):,i+1);scanf(%d,%d,&s,&d);/輸入邊的起始頂點(diǎn)和終止頂點(diǎn)/fflush(stdin);while(sadjg.vexnum|dadjg.vexnum)printf(輸入錯(cuò),重新輸入:);scanf(%d,%d,&s,&d);s-;d-;p=malloc(sizeof(EDGENODE);/建立一個(gè)和邊相關(guān)的結(jié)點(diǎn)/p-adjvex=d;p-next=adjg.adjlists.lin

6、k;/掛到對(duì)應(yīng)的單鏈表上/adjg.adjlists.link=p;p=malloc(sizeof(EDGENODE);/建立另一個(gè)和邊相關(guān)的結(jié)點(diǎn)/p-adjvex=s;p-next=adjg.adjlistd.link;/掛到對(duì)應(yīng)的單鏈表上/adjg.adjlistd.link=p;returnadjg;voidinitlinkqueue(LINKQUEUEq)/初始化廣度優(yōu)先遍歷算法中用到的鏈隊(duì)列/q-front=malloc(sizeof(LINKQLIST);(q-front)-next=NULL;q-rear=q-front;intemptylinkqueue(LINKQUEUEq)

7、/判隊(duì)空?/intv;if(q-front=q-rear)v=1;elsev=0;returnv;voidenlinkqueue(LINKQUEUEq,DATATYPE1x)/元素x入隊(duì)列/l80數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)(q-rear)-next=malloc(sizeof(LINKQLIST);q-rear=(q-rear)-next;(q-rear)-data=x;(q-rear)-next=NULL;DATATYPE1dellinkqueue(LINKQUEUEq)/刪除隊(duì)頭元素/LINKQLISTp;DATATYPE1v;if(emptylinkqueue(q)printf(隊(duì)列空.n)

8、;v=0;elsep=(q-front)-next;(q-front)-next=p-next;if(p-next=NULL)q-rear=q-front;v=p-data;free(p);returnv;voidbfs(ADJGRAPHadjg,intvi)/連通圖的廣度優(yōu)先遍歷算法:從vi頂點(diǎn)出發(fā)/intvisitedMAXLEN;inti,v;EDGENODEp;LINKQUEUEque,q;q=&que;initlinkqueue(q);for(i=0;iadjvex=0)visitedp-adjvex=1;printf(%d,adjg.adjlistp-adjvex.vertex);

9、第7章圖l81enlinkqueue(q,(p-adjvex)+1);/遍歷到的未訪問(wèn)過(guò)的結(jié)點(diǎn)編號(hào)入隊(duì)列/p=p-next;main()ADJGRAPHag;intj;printf(n連通圖的廣度遍歷n);ag=creat_adjgraph();/建立連通圖的鄰接鏈表結(jié)構(gòu)/printf(nn輸入廣度優(yōu)先遍歷起始頂點(diǎn)(1%d):,ag.vexnum);scanf(%d,&j);printf(nn廣度優(yōu)先遍歷結(jié)果序列:);bfs(ag,j);/連通圖的廣度遍歷算法/printf(nn);【習(xí)題2】連通圖上實(shí)現(xiàn)深度優(yōu)先遍歷題目要求:在以鄰接鏈表為存儲(chǔ)結(jié)構(gòu)的無(wú)向圖上,實(shí)現(xiàn)無(wú)向圖深度優(yōu)先遍歷算法。結(jié)構(gòu)說(shuō)

10、明:同上題。舉例說(shuō)明:數(shù)據(jù)輸入過(guò)程及輸出結(jié)果如圖74所示。圖7.4輸入及輸出l82數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)【解答】#include#includedatastru.h#includeintvisitedMAXLEN;ADJGRAPHcreat_adjgraph()EDGENODEp;inti,s,d;ADJGRAPHadjg;adjg.kind=2;printf(nn輸入頂點(diǎn)數(shù)和邊數(shù)(用逗號(hào)隔開(kāi)):);scanf(%d,%d,&s,&d);fflush(stdin);adjg.vexnum=s;/存放頂點(diǎn)數(shù)在adjg.vexnum中/adjg.arcnum=d;/存放邊點(diǎn)數(shù)在adjg.arcnu

11、m中/printf(nn);for(i=0;iadjg.vexnum;i+)/輸入頂點(diǎn)的值/printf(輸入頂點(diǎn)%d的值:,i+1);scanf(%d,&adjg.adjlisti.vertex);fflush(stdin);adjg.adjlisti.link=NULL;printf(n);for(i=0;iadjg.arcnum;i+)printf(輸入第%d條邊的起始頂點(diǎn)和終止頂點(diǎn)(用逗號(hào)隔開(kāi)):,i+1);scanf(%d,%d,&s,&d);/輸入邊的起始頂點(diǎn)和終止頂點(diǎn)/fflush(stdin);while(sadjg.vexnum|dadjg.vexnum)printf(輸入錯(cuò)

12、,重新輸入:);scanf(%d,%d,&s,&d);s-;d-;p=malloc(sizeof(EDGENODE);/建立一個(gè)和邊相關(guān)的結(jié)點(diǎn)/p-adjvex=d;p-next=adjg.adjlists.link;/掛到對(duì)應(yīng)的單鏈表上/adjg.adjlists.link=p;p=malloc(sizeof(EDGENODE);/建立另一個(gè)和邊相關(guān)的結(jié)點(diǎn)/p-adjvex=s;p-next=adjg.adjlistd.link;/掛到對(duì)應(yīng)的單鏈表上/adjg.adjlistd.link=p;第7章圖l83returnadjg;voiddfs(ADJGRAPHadjg,intv)/連通圖的深

13、度優(yōu)先遍歷算法:從v頂點(diǎn)出發(fā)/EDGENODEp;visitedv-1=1;/從編號(hào)為v的頂點(diǎn)出發(fā),visited數(shù)組對(duì)應(yīng)位置1/v-;printf(%d,adjg.adjlistv.vertex);/輸出v頂點(diǎn)/p=adjg.adjlistv.link;/取單鏈表的第一個(gè)結(jié)點(diǎn)/while(p!=NULL)/對(duì)應(yīng)單鏈表不空,進(jìn)行遍歷/f(visitedp-adjvex=0)/如果有未被訪問(wèn)過(guò)的結(jié)點(diǎn)/dfs(adjg,(p-adjvex)+1);/遞歸調(diào)用深度優(yōu)先遍歷算法/p=p-next;/取單鏈表的下一個(gè)結(jié)點(diǎn)/main()ADJGRAPHag;inti;printf(n連通圖的深度遍歷n);

14、ag=creat_adjgraph();/建立連通圖的鄰接鏈表結(jié)構(gòu)/for(i=0;iag.vexnum;i+)/visited數(shù)組初始化,均置0/visitedi=0;printf(nn輸入深度優(yōu)先遍歷起始頂點(diǎn)(1-%d):,ag.vexnum);scanf(%d,&i);printf(nn深度優(yōu)先遍歷結(jié)果序列:);dfs(ag,i);/連通圖的深度優(yōu)先遍歷算法/printf(nn);圖7.5有向圖1【習(xí)題3】拓?fù)渑判蝾}目要求:在以鄰接鏈表為存儲(chǔ)結(jié)構(gòu)的有向圖上,實(shí)現(xiàn)有向圖的拓?fù)渑判?。結(jié)構(gòu)說(shuō)明:同上題。舉例說(shuō)明:設(shè)有向圖如圖75所示,頂點(diǎn)值設(shè)定為V1=100,V2=200,V3=300,V4=

15、400,V5=500,V6=600,6個(gè)頂點(diǎn)和8條邊的編號(hào)如圖75所示。數(shù)據(jù)輸入過(guò)程及輸出結(jié)果如圖76所示。l84數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)圖7.6對(duì)應(yīng)輸入的結(jié)果【解答】#include#include#includedatastru.hADJGRAPHcreat_adjgraph()/建立有向圖的鄰接鏈表結(jié)構(gòu)/EDGENODEp;inti,s,d;ADJGRAPHadjg;adjg.kind=1;printf(nn輸入頂點(diǎn)數(shù)和邊數(shù)(用逗號(hào)隔開(kāi)):);scanf(%d,%d,&s,&d);fflush(stdin);adjg.vexnum=s;/存放頂點(diǎn)數(shù)在adjg.vexnum中/adjg.ar

16、cnum=d;/存放邊點(diǎn)數(shù)在adjg.arcnum中/printf(nn);for(i=0;iadjg.vexnum;i+)/鄰接鏈表頂點(diǎn)初始化/printf(輸入頂點(diǎn)%d的值:,i+1);scanf(%d,&adjg.adjlisti.vertex);/輸入頂點(diǎn)的值/第7章圖l85fflush(stdin);adjg.adjlisti.link=NULL;adjg.adjlisti.id=0;printf(nn);for(i=0;iadjg.arcnum;i+)printf(輸入第%d條有向弧的起始頂點(diǎn)和終止頂點(diǎn)(用逗號(hào)隔開(kāi)):,i+1);scanf(%d,%d,&s,&d);/輸入弧的起始

17、頂點(diǎn)和終止頂點(diǎn)/fflush(stdin);while(sadjg.vexnum|dadjg.vexnum)printf(輸入錯(cuò),重新輸入:);scanf(%d,%d,&s,&d);s-;d-;p=malloc(sizeof(EDGENODE);/每條弧對(duì)應(yīng)生成一個(gè)結(jié)點(diǎn)/p-adjvex=d;p-next=adjg.adjlists.link;/結(jié)點(diǎn)插入對(duì)應(yīng)的單鏈表上/adjg.adjlists.link=p;adjg.adjlistd.id+;/弧的終端頂點(diǎn)入度加1/returnadjg;voidtopsort(ADJGRAPHag)inti,j,k,m,n,top;EDGENODEp;n=

18、ag.vexnum;top=-1;/拓?fù)渑判蛑杏玫降臈３跏蓟?for(i=0;iadjvex;ag.adjlistk.id-;/刪除相關(guān)的弧,即弧終點(diǎn)結(jié)點(diǎn)的入度減1/if(ag.adjlistk.id=0)/出現(xiàn)新的入度為0的頂點(diǎn),將其入棧/g.adjlistk.id=top;top=k;p=p-next;if(mn)printf(nn有向圖中有環(huán)路!nn);/拓?fù)渑判蜻^(guò)程中輸出的頂點(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù)/main()DJGRAPHag;printf(n有向圖的拓?fù)渑判騨);ag=creat_adjgraph();/建立有向圖的鄰接鏈表結(jié)構(gòu)/topsort(ag);/進(jìn)行拓?fù)渑判?printf

19、(nn);【習(xí)題4】求最短路徑題目要求:在以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的有向圖上,求單源點(diǎn)到其他頂點(diǎn)的最短路徑。結(jié)構(gòu)說(shuō)明:#defineVEXTYPEint#defineADJTYPEint#defineMAXLEN40typedefstructotherdata;/圖中邊的信息,在下面的分析和討論中忽略不考慮/VEXTYPEvexsMAXLEN;/圖中頂點(diǎn)的信息/ADJTYPEarcsMAXLENMAXLEN;/鄰接矩陣/intvexnum,arcnum;/頂點(diǎn)數(shù)和邊數(shù)/intkind;/圖的類型/MGRAPH;舉例說(shuō)明:設(shè)有向圖如圖77所示,頂點(diǎn)值設(shè)定為V1=100,V2=200,V3=300,V

20、4=400,V5=500,V6=600,V7=700,7個(gè)頂點(diǎn)和11條邊的編號(hào)如圖77所示。數(shù)據(jù)輸入過(guò)程如圖78所示,輸出結(jié)果如圖79所示。第7章圖l87圖7.7有向圖2圖7.8輸入圖7.9結(jié)果l88數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)【解答】#includedatastru.h#include#include#defineMAX10000MGRAPHcreate_mgraph()/建立有向圖的鄰接矩陣結(jié)構(gòu)/inti,j,k,h;MGRAPHmg;mg.kind=3;printf(nn輸入頂點(diǎn)數(shù)和邊數(shù)(用逗號(hào)隔開(kāi)):);scanf(%d,%d,&i,&j);mg.vexnum=i;/存放頂點(diǎn)數(shù)在mg.vex

21、num中/mg.arcnum=j;/存放邊點(diǎn)數(shù)在mg.arcnum中/fflush(stdin);for(i=0;img.vexnum;i+)printf(輸入頂點(diǎn)%d的值:,i+1);/輸入頂點(diǎn)的值/scanf(%d,&mg.vexsi);fflush(stdin);for(i=0;img.vexnum;i+)/鄰接矩陣初始化/for(j=0;jmg.vexnum;j+)mg.arcsij=MAX;for(k=1;k=mg.arcnum;k+)printf(輸入第%d條邊的起始頂點(diǎn)和終止頂點(diǎn)(用逗號(hào)隔開(kāi)):,k);scanf(%d,%d,&i,&j);/輸入弧的起始頂點(diǎn)和終止頂點(diǎn)/fflus

22、h(stdin);while(img.vexnum|jmg.vexnum)printf(輸入錯(cuò),重新輸入:);scanf(%d,%d,&i,&j);printf(輸入此邊權(quán)值:);/輸入弧上之權(quán)值/scanf(%d,&h);mg.arcsi-1j-1=h;returnmg;main()MGRAPHmg;intcostMAXLENMAXLEN;第7章圖l89intpathMAXLEN,sMAXLEN;intdistMAXLEN;inti,j,n,v0,min,u;printf(n求有向圖單源點(diǎn)最短路徑n);mg=create_mgraph();/建立有向圖的鄰接矩陣結(jié)構(gòu)/printf(nn起始頂

23、點(diǎn)為:);/有向圖中頂點(diǎn)的編號(hào)從1編起/scanf(%d,&v0);v0-;n=mg.vexnum;for(i=0;in;i+)/cost矩陣初始化/for(j=0;jn;j+)costij=mg.arcsij;costii=0;for(i=0;in;i+)disti=costv0i;/dist數(shù)組初始化/if(disti0)/path數(shù)組初始化/pathi=v0;for(i=0;in;i+)/s數(shù)組初始化/si=0;sv0=1;for(i=0;in;i+)/按最短路徑遞增算法計(jì)算/min=MAX;u=v0;for(j=0;jn;j+)if(sj=0&distjmin)min=distj;u=

24、j;su=1;/u頂點(diǎn)是求得最短路徑的頂點(diǎn)編號(hào)/for(j=0;jn;j+)if(sj=0&distu+costujdistj)/調(diào)整dist/distj=distu+costuj;pathj=u;/path記錄了路徑經(jīng)過(guò)的頂點(diǎn)/for(i=0;in;i+)/打印結(jié)果/if(si=1)u=i;while(u!=v0)printf(%d-,u+1);u=pathu;printf(%d,u+1);printf(d=%dn,disti);/有路徑/l90數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)elseprintf(%d-%dd=MAXn,i+1,v0+1);/無(wú)路徑/printf(nn);【習(xí)題5】圖的鄰接矩陣結(jié)構(gòu)轉(zhuǎn)

25、為鄰接鏈表結(jié)構(gòu)題目要求:將連通圖的鄰接矩陣結(jié)構(gòu)轉(zhuǎn)為鄰接鏈表結(jié)構(gòu)。結(jié)構(gòu)說(shuō)明:圖的鄰接矩陣結(jié)構(gòu)同【習(xí)題4】;圖的鄰接鏈表結(jié)構(gòu)同【習(xí)題1】。舉例說(shuō)明:以【習(xí)題1】中的圖71連通圖為例,輸出結(jié)果如圖710所示。圖7.10轉(zhuǎn)變的結(jié)果【解答】#includedatastru.h#include#includeMGRAPHcreate_mgraph()/建立圖的鄰接矩陣/inti,j,k;MGRAPHmg;mg.kind=2;printf(nn輸入頂點(diǎn)數(shù)和邊數(shù)(用逗號(hào)隔開(kāi)):);scanf(%d,%d,&i,&j);fflush(stdin);mg.vexnum=i;第7章圖l91mg.arcnum=j;p

26、rintf(nn);for(i=0;img.vexnum;i+)printf(輸入頂點(diǎn)%d的值:,i+1);scanf(%d,&mg.vexsi);fflush(stdin);for(i=0;img.vexnum;i+)for(j=0;jmg.vexnum;j+)mg.arcsij=0;for(k=1;k=mg.arcnum;k+)printf(輸入第%d條邊的起始頂點(diǎn)和終止頂點(diǎn)(用逗號(hào)隔開(kāi)):,k);scanf(%d,%d,&i,&j);fflush(stdin);while(img.vexnum|jmg.vexnum)printf(輸入錯(cuò),重新輸入:);scanf(%d,%d,&i,&j);mg.arcsi-1j-1=1;mg.arcsj-1i-1=1;returnmg;ADJGRAPHmg_to_adjg(MGRAPHmg)nti,j,n;ADJGRAPHadjg;EDGENODEp;n=mg.vexnum;adjg.vexnum=mg.vexnum;