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

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

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

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

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

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

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

7、/判隊空?/intv;if(q-front=q-rear)v=1;elsev=0;returnv;voidenlinkqueue(LINKQUEUEq,DATATYPE1x)/元素x入隊列/l80數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實訓(xùn)(q-rear)-next=malloc(sizeof(LINKQLIST);q-rear=(q-rear)-next;(q-rear)-data=x;(q-rear)-next=NULL;DATATYPE1dellinkqueue(LINKQUEUEq)/刪除隊頭元素/LINKQLISTp;DATATYPE1v;if(emptylinkqueue(q)printf(隊列空.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頂點出發(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);/遍歷到的未訪問過的結(jié)點編號入隊列/p=p-next;main()ADJGRAPHag;intj;printf(n連通圖的廣度遍歷n);ag=creat_adjgraph();/建立連通圖的鄰接鏈表結(jié)構(gòu)/printf(nn輸入廣度優(yōu)先遍歷起始頂點(1%d):,ag.vexnum);scanf(%d,&j);printf(nn廣度優(yōu)先遍歷結(jié)果序列:);bfs(ag,j);/連通圖的廣度遍歷算法/printf(nn);【習(xí)題2】連通圖上實現(xiàn)深度優(yōu)先遍歷題目要求:在以鄰接鏈表為存儲結(jié)構(gòu)的無向圖上,實現(xiàn)無向圖深度優(yōu)先遍歷算法。結(jié)構(gòu)說

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

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

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

13、度優(yōu)先遍歷算法:從v頂點出發(fā)/EDGENODEp;visitedv-1=1;/從編號為v的頂點出發(fā),visited數(shù)組對應(yīng)位置1/v-;printf(%d,adjg.adjlistv.vertex);/輸出v頂點/p=adjg.adjlistv.link;/取單鏈表的第一個結(jié)點/while(p!=NULL)/對應(yīng)單鏈表不空,進(jìn)行遍歷/f(visitedp-adjvex=0)/如果有未被訪問過的結(jié)點/dfs(adjg,(p-adjvex)+1);/遞歸調(diào)用深度優(yōu)先遍歷算法/p=p-next;/取單鏈表的下一個結(jié)點/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)先遍歷起始頂點(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ù)渑判蝾}目要求:在以鄰接鏈表為存儲結(jié)構(gòu)的有向圖上,實現(xiàn)有向圖的拓?fù)渑判颉＝Y(jié)構(gòu)說明:同上題。舉例說明:設(shè)有向圖如圖75所示,頂點值設(shè)定為V1=100,V2=200,V3=300,V4=

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

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

17、頂點和終止頂點/fflush(stdin);while(sadjg.vexnum|dadjg.vexnum)printf(輸入錯,重新輸入:);scanf(%d,%d,&s,&d);s-;d-;p=malloc(sizeof(EDGENODE);/每條弧對應(yīng)生成一個結(jié)點/p-adjvex=d;p-next=adjg.adjlists.link;/結(jié)點插入對應(yīng)的單鏈表上/adjg.adjlists.link=p;adjg.adjlistd.id+;/弧的終端頂點入度加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)的弧,即弧終點結(jié)點的入度減1/if(ag.adjlistk.id=0)/出現(xiàn)新的入度為0的頂點,將其入棧/g.adjlistk.id=top;top=k;p=p-next;if(mn)printf(nn有向圖中有環(huán)路!nn);/拓?fù)渑判蜻^程中輸出的頂點數(shù)小于有向圖的頂點數(shù)/main()DJGRAPHag;printf(n有向圖的拓?fù)渑判騨);ag=creat_adjgraph();/建立有向圖的鄰接鏈表結(jié)構(gòu)/topsort(ag);/進(jìn)行拓?fù)渑判?printf

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

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

21、num中/mg.arcnum=j;/存放邊點數(shù)在mg.arcnum中/fflush(stdin);for(i=0;img.vexnum;i+)printf(輸入頂點%d的值:,i+1);/輸入頂點的值/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條邊的起始頂點和終止頂點(用逗號隔開):,k);scanf(%d,%d,&i,&j);/輸入弧的起始頂點和終止頂點/fflus

22、h(stdin);while(img.vexnum|jmg.vexnum)printf(輸入錯,重新輸入:);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求有向圖單源點最短路徑n);mg=create_mgraph();/建立有向圖的鄰接矩陣結(jié)構(gòu)/printf(nn起始頂

23、點為:);/有向圖中頂點的編號從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+)/按最短路徑遞增算法計算/min=MAX;u=v0;for(j=0;jn;j+)if(sj=0&distjmin)min=distj;u=

24、j;su=1;/u頂點是求得最短路徑的頂點編號/for(j=0;jn;j+)if(sj=0&distu+costujdistj)/調(diào)整dist/distj=distu+costuj;pathj=u;/path記錄了路徑經(jīng)過的頂點/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í)題解析與實訓(xùn)elseprintf(%d-%dd=MAXn,i+1,v0+1);/無路徑/printf(nn);【習(xí)題5】圖的鄰接矩陣結(jié)構(gòu)轉(zhuǎn)

25、為鄰接鏈表結(jié)構(gòu)題目要求:將連通圖的鄰接矩陣結(jié)構(gòu)轉(zhuǎn)為鄰接鏈表結(jié)構(gòu)。結(jié)構(gòu)說明:圖的鄰接矩陣結(jié)構(gòu)同【習(xí)題4】;圖的鄰接鏈表結(jié)構(gòu)同【習(xí)題1】。舉例說明:以【習(xí)題1】中的圖71連通圖為例,輸出結(jié)果如圖710所示。圖7.10轉(zhuǎn)變的結(jié)果【解答】#includedatastru.h#include#includeMGRAPHcreate_mgraph()/建立圖的鄰接矩陣/inti,j,k;MGRAPHmg;mg.kind=2;printf(nn輸入頂點數(shù)和邊數(shù)(用逗號隔開):);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(輸入頂點%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條邊的起始頂點和終止頂點(用逗號隔開):,k);scanf(%d,%d,&i,&j);fflush(stdin);while(img.vexnum|jmg.vexnum)printf(輸入錯,重新輸入:);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;