算法與數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機(jī)械工業(yè)出版社課后答案 第7章 圖

《算法與數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機(jī)械工業(yè)出版社課后答案 第7章 圖》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法與數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機(jī)械工業(yè)出版社課后答案 第7章 圖（19頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 第 7 章 圖 一、基礎(chǔ)知識(shí)題 7.1設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有多少條邊？ 【解答】n(n-1)/2 ? 7.2一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為多少？ 【解答】n-1 ? 7.3要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要多少條弧? 【解答】n ? 7.4 n個(gè)頂點(diǎn)的完全有向圖含有弧的數(shù)目是多少? 【解答】n(n-1) ? 7.5一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖，最少有多少個(gè)連通分量，最多有多少個(gè)連通分量。 【解答】1, n ? 7.6圖的BFS生成樹(shù)的樹(shù)高要小于等于同圖DFS生成樹(shù)的樹(shù)高，對(duì)嗎？ 【解答】對(duì) ? 7.7無(wú)向圖G=(V,

2、E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，寫(xiě)出對(duì)該圖從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可能得到的全部頂點(diǎn)序列。 【解答】abedfc, acfdeb, aebdfc, aedfcb ? 7.8 在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的 Prim 算法的時(shí)間復(fù)雜度是多少？ 【解答】O(n+e) ? 7.9若一個(gè)具有n個(gè)頂點(diǎn)，e條邊的無(wú)向圖是一個(gè)森林，則該森林中必有多少棵樹(shù)？ 【解答】n-e ? 7.10 n個(gè)頂點(diǎn)的無(wú)向圖的鄰接矩陣至少有多少非零元素？ 【解答】0 ? 7.11證明:具有n個(gè)

3、頂點(diǎn)和多于n-1條邊的無(wú)向連通圖G一定不是樹(shù)。 【證明】具有n個(gè)頂點(diǎn)n-1條邊的無(wú)向連通圖是自由樹(shù)，即沒(méi)有確定根結(jié)點(diǎn)的樹(shù)，每個(gè)結(jié)點(diǎn)均可當(dāng)根。若邊數(shù)多于n-1條，因一條邊要連接兩個(gè)結(jié)點(diǎn)，則必因加上這一條邊而使兩個(gè)結(jié)點(diǎn)多了一條通路，即形成回路。形成回路的連通圖不再是樹(shù)。 ? 7.12證明對(duì)有向圖頂點(diǎn)適當(dāng)編號(hào)，使其鄰接矩陣為下三角形且主對(duì)角線為全零的充要條件是該圖是無(wú)環(huán)圖。 【證明】該有向圖頂點(diǎn)編號(hào)的規(guī)律是讓弧尾頂點(diǎn)的編號(hào)大于弧頭頂點(diǎn)的編號(hào)。由于不允許從某頂點(diǎn)發(fā)出并回到自身頂點(diǎn)的弧，所以鄰接矩陣主對(duì)角元素均為0。先證明該命題的充分條件。由于弧尾頂點(diǎn)的編號(hào)均大于弧頭頂點(diǎn)的編號(hào)，在鄰接矩陣中，非

4、零元素（A[i][j]=1）自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現(xiàn)弧頭頂點(diǎn)編號(hào)大于弧尾頂點(diǎn)編號(hào)的弧，否則，就必然存在環(huán)路。（對(duì)該類(lèi)有向無(wú)環(huán)圖頂點(diǎn)編號(hào)，應(yīng)按頂點(diǎn)出度的大小進(jìn)行順序編號(hào)。） ? 7.13設(shè)G=(V，E)以鄰接表存儲(chǔ)，如圖所示，試畫(huà)出從頂點(diǎn)1出發(fā)所得到的深度優(yōu)先和廣度優(yōu)先生成樹(shù)。 ? ? ? ? ? ? ? 習(xí)題7.13 的圖 【解答】深度優(yōu)先生成樹(shù) 1 2 3 4 5 ? ? ? 　　　　　寬度優(yōu)先生成樹(shù)： 1 2 3 4 5 ?

5、 ? ? ? ? ? ? 7.14 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為： V={0，1，2，3，4，5，6，7}； E={<0，2>，<1，3>，<1，4>，<2，4>，<2，5>，<3，6>，<3，7>，<4，7>，<4，8>，<5，7>，<6，7>，<7，8>}； 若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照頂點(diǎn)序號(hào)從小到大的次序鏈接的，則按教材中介紹的進(jìn)行拓?fù)渑判虻乃惴ǎ瑢?xiě)出得到的拓?fù)湫蛄小? 【解答】1-3-6-0-2-5-4-7-8 ? 7.15一帶權(quán)無(wú)向圖的鄰接矩陣如下圖 ，試畫(huà)出它的一棵最小生成樹(shù)。

6、 習(xí)題7.15 的圖 習(xí)題7.16 的圖 【解答】設(shè)頂點(diǎn)集合為{1，2，3，4，5，6}， 由下邊的邏輯圖可以看出，在{1，2，3}和{4，5，6}回路中， 各任選兩條邊，加上（2，4），則可構(gòu)成9棵不同的最小生成樹(shù)。 ? 1 2 1 1 1 1 1 3 1 2 3 4 5 6 ? ? ? ? ? ? ?

7、7.16如圖所示是一帶權(quán)有向圖的鄰接表法存儲(chǔ)表示。其中出邊表中的每個(gè)結(jié)點(diǎn)均含有三個(gè)字段，依次為邊的另一個(gè)頂點(diǎn)在頂點(diǎn)表中的序號(hào)、邊上的權(quán)值和指向下一個(gè)邊結(jié)點(diǎn)的指針。試求： （1）．該帶權(quán)有向圖的圖形； （2）．從頂點(diǎn)V1為起點(diǎn)的廣度優(yōu)先遍歷的頂點(diǎn)序列及對(duì)應(yīng)的生成樹(shù)； （3）．以頂點(diǎn)V1為起點(diǎn)的深度優(yōu)先遍歷生成樹(shù)； （4）．由頂點(diǎn)V1到頂點(diǎn)V3的最短路徑。 33 36 25 18 10 29 38 30 42 1 4 3 2 6 5 【解答】(1) ? ? ? ? ?

8、 (2)V1,V2,V4,V6,V3,V5 1 2 4 6 3 5 ? ? ? ? ? ? ? (3)? 頂點(diǎn)集合V(G)={V1,V2,V3,V4,V5,V6} 邊的集合 E(G)={,,,,} (4)? V1到V3最短路徑為67: (V1—V4—V3) 迭代 集合 S ? 選擇 頂點(diǎn) D[ ] D[2] D[3] D[4] D[5] D[6] 初值 {

9、 v1} ? 33 ∞ 29 ∞ 25 1 {v1, v6} v6 33 ∞ 29 ∞ 25 2 { v1, v6, v4} v4 33 67 29 71 3 { v1, v6, v4, v2} v2 33 67 71 4 {v1,v6, v4, v2,v3} v3 67 71 5 {v1,v6,v4, v2,v3,v5} v 71 ? ? ? ? ? ?

10、 ? ? ? ? 7.17已知一有向網(wǎng)的鄰接矩陣如下，如需在其中一個(gè)頂點(diǎn)建立娛樂(lè)中心，要求該頂點(diǎn)距其它各頂點(diǎn)的最長(zhǎng)往返路程最短，相同條件下總的往返路程越短越好，問(wèn)娛樂(lè)中心應(yīng)選址何處？給出解題過(guò)程。 習(xí)題7.18的圖 習(xí)題7.17 的圖 【解答】下面用FLOYD算法求出任意兩頂點(diǎn)的最短路徑（如圖A（6）所示）。題目要求娛樂(lè)中心“距其它各結(jié)點(diǎn)的最長(zhǎng)往返路程最短”，結(jié)點(diǎn)V1，V3，V5和V6最長(zhǎng)往返路徑最短都是9。按著“相同條件下總的往返路徑越短越好”，選頂點(diǎn)V5，總的往返路徑是34。 A(0)= A(1)= A(2)= A(3)= A

11、(4)= A(5)= A(6)= 7.18求出圖中頂點(diǎn)1到其余各頂點(diǎn)的最短路徑。 【解答】本表中DIST中各列最下方的數(shù)字是頂點(diǎn)1到頂點(diǎn)的最短通路。 所選頂點(diǎn) S（已確定最短路徑 的頂點(diǎn)集合） T(尚未確定最短 路徑的頂點(diǎn)集合) DIST [2] [3] [4] [5] [6] [7] [8] 初態(tài) {1} {2,3,4,5,6,7,8} 30 ￥ 60 10 ￥ ￥ ￥ 5 {1,5} {2,3,4,6,7,8} 25 ￥ 60 10 17 ￥ ￥ 6 {1,5,6} {2,3,4

12、,7,8 } 20 33 60 ? 17 25 ￥ 2 {1,5,6,2} {3,4,7,8} 20 33 60 ? ? 25 ￥ 7 {1,5,6,2,7} {3,4,8} ? 31 28 ? ? 25 35 4 {1,5,6,2,7,4} {3,8} ? 31 28 ? ? ? 35 3 {1,5,6,2,7,4,3} {5,8} ? 31 ? ? ? ? 35 8 {1,5,6,2,7,4,3,8} {8} ? ? ? ? ? ? 35 頂點(diǎn)1到其它頂點(diǎn)的最短路徑依次是20

13、，31，28，10，17，25，35。按Dijkstra算法所選頂點(diǎn)依次是5，6，2，7，4，3，8。 ? 7.19對(duì)圖示的AOE網(wǎng)絡(luò)，計(jì)算各活動(dòng)弧的e(ai)和l(ai)的函數(shù)值，各事件（頂點(diǎn)）的ve（vi）和vl (vi)的函數(shù)值，列出各條關(guān)鍵路徑。 【解答】 頂點(diǎn) α A B C D E F G H W Ve(i) 0 1 6 3 4 24 13 39 22 52 Vl(i) 0 29 24 3 7 31 13 39 22 52 ? 活動(dòng) a1 a2 a3 a4 a5 a6 a7 a8 a9

14、 a10 a11 a12 a13 a14 a15 a16 a17 e(i) 0 0 0 0 1 6 6 3 3 4 24 13 13 13 39 22 22 l(i) 28 18 0 3 29 24 31 34 3 7 31 20 36 13 39 22 40 a C F H G W ，長(zhǎng)52。 關(guān)鍵路徑是： ? 活動(dòng)與頂點(diǎn)的對(duì)照表：a1<α,A> a2<α,B> a3<α,C> a4<α,D> a5 a6 a7 a8<

15、C,G> a9 a10 a11 a12 a13 a14 a15 a16 a17 ? 7.20??????????? 利用弗洛伊德算法，寫(xiě)出如圖所示相應(yīng)的帶權(quán)鄰接矩陣的變化。 3 2 1 4 5 9 6 8 2 3 1 10 ? ? ? ? ? ? ? ? ? ? ? 【解答】A0= A1= A2= A3= A4= ? 二、算法設(shè)計(jì)題 7.21 設(shè)無(wú)向圖G有n個(gè)頂點(diǎn)，m條邊。試編寫(xiě)用鄰接表存儲(chǔ)該

16、圖的算法。 void CreatGraph (AdjList g)∥建立有n個(gè)頂點(diǎn)和m 條邊的無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu) {int n,m; scanf("%d%d",&n,&m); for(i=0,i

17、*)malloc(sizeof(ArcNode));∥申請(qǐng)邊結(jié)點(diǎn) p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p; ∥將邊結(jié)點(diǎn)鏈入 p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=i; p->next=g[j].firstarc; g[j].frstarc=p; }∥for }∥算法CreatGraph結(jié)束 ? 7.22 已知有向圖有n個(gè)頂點(diǎn)，請(qǐng)編寫(xiě)算法，根據(jù)用戶輸入的偶對(duì)建立該有向圖的鄰接表。 void CreatAdjList(AdjList g)∥建立有向圖

18、的鄰接表存儲(chǔ)結(jié)構(gòu) {int n; scanf("%d",&n); for(i=0;iadjvex=j; p->next=g[i].firstarc; g[i].firstarc=

19、p; scanf(&v1,&v2); }∥while } ? 7.23 給出以十字鏈表作存儲(chǔ)結(jié)構(gòu)，建立圖的算法，輸入(i，j，v)其中i，j為頂點(diǎn)號(hào)，v為權(quán)值。 void CreatOrthList(OrthList g)∥建立有向圖的十字鏈表存儲(chǔ)結(jié)構(gòu) {int i,j,v; ∥假定權(quán)值為整型 scanf("%d",&n); for(i=0,i

20、); while(i && j && v) ∥當(dāng)輸入i,j,v之一為0時(shí),結(jié)束算法運(yùn)行 {p=(OrArcNode *)malloc(sizeof(OrArcNode)); ∥申請(qǐng)結(jié)點(diǎn) p->headvex=j; p->tailvex=i; p->weight=v;∥弧結(jié)點(diǎn)中權(quán)值域 p->headlink=g[j].firstin; g[j].firstin=p; p->tailink=g[i].firstout; g[i].firstout=p; scanf("%d%d%d",&i,&j,&v); }∥while }∥算法結(jié)

21、束 [算法討論] 本題已假定輸入的i和j是頂點(diǎn)號(hào),否則,頂點(diǎn)的信息要輸入,且用頂點(diǎn)定位函數(shù)求出頂點(diǎn)在頂點(diǎn)向量中的下標(biāo)。圖建立時(shí)，若已知邊數(shù)（如上面1和2題），可以用for循環(huán)；若不知邊數(shù)，可用while循環(huán)（如本題），規(guī)定輸入特殊數(shù)（如本題的零值）時(shí)結(jié)束運(yùn)行。本題中數(shù)值設(shè)為整型，否則應(yīng)以和數(shù)值類(lèi)型相容的方式輸入。 ? 7.24 設(shè)有向圖G有n個(gè)點(diǎn)(用1，2，…，n表示)，e條邊，寫(xiě)一算法根據(jù)G的鄰接表生成G的反向鄰接表，要求算法時(shí)間復(fù)雜性為O(n+e)。 void InvertAdjList(AdjList gin,gout)∥將有向圖的出度鄰接表改為按入度建立的逆鄰接表

22、{for(i=0;iadjvex; s=(ArcNode *)malloc(sizeof(ArcNode));∥申請(qǐng)結(jié)點(diǎn)空間 s

23、->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s; p=p->next;∥下一個(gè)鄰接點(diǎn)。 }∥while }∥for } ? 7.25 寫(xiě)出從圖的鄰接表表示轉(zhuǎn)換成鄰接矩陣表示的算法。 void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm) ∥將圖的鄰接表表示轉(zhuǎn)換為鄰接矩陣表示 {for(i=0;i

24、 for(i=0;iadjvex]=1;p=p->next; } }∥for }∥算法結(jié)束 ? 7.26 試寫(xiě)出把圖的鄰接矩陣表示轉(zhuǎn)換為鄰接表表示的算法。 void AdjMatrixToAdjList(AdjMatrix gm, AdjList gl) ∥將圖的鄰接矩陣表示轉(zhuǎn)換為鄰接表表示 {for(i=0;i

25、 {scanf(&gl[i].vertex); gl[i].firstarc=null;} for(i=0;iadjvex=j;∥頂點(diǎn)I的鄰接點(diǎn)是j p->next=gl[i].firstarc; gl[i].firstarc=p; ∥鏈入頂點(diǎn)i的鄰接點(diǎn)鏈表中 }∥if }∥end ? 7.27 試編寫(xiě)

26、建立有n個(gè)頂點(diǎn)，m條邊且以鄰接多重表為存儲(chǔ)結(jié)構(gòu)表示的無(wú)向圖的算法。 void CreatMGraph(AdjMulist g) ∥建立有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接多重表的存儲(chǔ)結(jié)構(gòu) {int n,e; scanf("%d%d",&n,&e); for(i=0,i

27、ateVertex(g,v2); p=(ENode *)malloc(sizeof(ENode)); p->ivex=i; p->jvex=j; p->ilink=g[i].firstedge; p->jlink=g[j].firstedge; g[i].firstedge=p; g[j].firstedge=p; }∥for }∥算法結(jié)束 ? 7.28 已知某有向圖（n個(gè)結(jié)點(diǎn)）的鄰接表，求該圖各結(jié)點(diǎn)的入度數(shù)。 【題目分析】在有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)中求頂點(diǎn)的入度，需要遍歷整個(gè)鄰接表。 void Indegree(AdjList g)∥求以鄰接表為存儲(chǔ)結(jié)構(gòu)的n個(gè)頂點(diǎn)有向圖

28、的各頂點(diǎn)入度 {for(i=0;iadjvex==i) num++; p=p->next; } } printf(“頂點(diǎn)%d的入度為：%d\n”,g[i].vexdata,num); ∥設(shè)頂點(diǎn)數(shù)據(jù)為整型 } } ? 7.29 已知無(wú)向圖G=(V，E)，給出求圖G的連通分量

29、個(gè)數(shù)的算法。 【題目分析】使用圖的遍歷可以求出圖的連通分量。進(jìn)入dfs或bfs一次，就可以訪問(wèn)到圖的一個(gè)連通分量的所有頂點(diǎn)。 void dfs (v) {visited[v]=1; printf (“%3d”,v); ∥輸出連通分量的頂點(diǎn)。 p=g[v].firstarc; while(p!=null) {if（visited[p->adjvex==0]） dfs(p->adjvex); p=p->next; }∥while }∥ dfs void Count() ∥求圖中連通分量的個(gè)數(shù) {int k=0 ; static AdjLi

30、st g ; ∥設(shè)無(wú)向圖g有n個(gè)結(jié)點(diǎn) for(i=0;i

31、式存儲(chǔ)的無(wú)向圖g中，刪除邊(i,j) {p=g[i].firstarc; pre=null; ∥刪頂點(diǎn)i 的邊結(jié)點(diǎn)(i,j),pre是前驅(qū)指針 while(p) if(p->adjvex==j) {if(pre==null)g[i].firstarc=p->next; else pre->next=p->next; free(p); }∥釋放空間 else {pre=p; p=p->next;} ∥沿鏈表繼續(xù)查找 p=g[j].firstarc; pre=null; ∥刪頂點(diǎn)j 的邊結(jié)點(diǎn)(j,i) while(p) if(p->adj

32、vex==i) {if(pre==null)g[j].firstarc=p->next; else pre->next=p->next; free(p); }∥釋放空間 else {pre=p; p=p->next;} ∥沿鏈表繼續(xù)查找 }∥ DeletEdge 【算法討論】 算法中假定給的i，j 均存在，否則應(yīng)檢查其合法性。若未給頂點(diǎn)編號(hào)，而給出頂點(diǎn)信息，則先用頂點(diǎn)定位函數(shù)求出其在鄰接表頂點(diǎn)向量中的下標(biāo)i和j。 ? 7.31 假設(shè)有向圖以鄰接表存儲(chǔ)，試編寫(xiě)算法刪除弧的算法。 void DeleteArc（AdjList g,ver

33、type vi,vj） ∥刪除以鄰接表存儲(chǔ)的有向圖g的一條弧，假定頂點(diǎn)vi和vj存在 {i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); ∥頂點(diǎn)定位 p=g[i].firstarc; pre=null; while(p) if(p->adjvex==j) {if(pre==null) g[i].firstarc=p->next; else pre->next=p->next;free(p); }∥釋放結(jié)點(diǎn)空間 else {pre=p; p=p->

34、next;} }∥結(jié)束 ? 7.32? 設(shè)計(jì)一個(gè)算法利用遍歷圖的方法判別一個(gè)有向圖G中是否存在從頂點(diǎn)Vi到Vj的長(zhǎng)度為k的簡(jiǎn)單路徑，假設(shè)有向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)。 【題目分析】本題利用深度優(yōu)先遞歸的搜索方法判斷有向圖G的頂點(diǎn)i到j(luò)是否存在長(zhǎng)度為k的簡(jiǎn)單路徑，先找到i的第一個(gè)鄰接點(diǎn)m，再?gòu)膍出發(fā)遞歸的求是否存在m到j(luò)的長(zhǎng)度為k-1的簡(jiǎn)單路徑。 int existpathlen(AlGraph G,int i,int j,int k) {//判斷鄰接表方式存儲(chǔ)的有向圖G的頂點(diǎn)i到j(luò)是否存在長(zhǎng)度為k的簡(jiǎn)單路徑 if(i==j&&k==0) return 1; //找

35、到了一條路徑,且長(zhǎng)度符合要求 else if(k>0) {visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->next) {m=p->adjvex; if(!visited[m]) if(existpathlen(G,m,j,k-1)) return 1; //剩余路徑長(zhǎng)度減一 } visited[i]=0; //本題允許曾經(jīng)被訪問(wèn)過(guò)的結(jié)點(diǎn)出

36、現(xiàn)在另一條路徑中 } return 0; //沒(méi)找到 } ? 7.33? 設(shè)有向圖G采用鄰接矩陣存儲(chǔ)，編寫(xiě)算法求出G中頂點(diǎn)i到頂點(diǎn)j的不含回路的、長(zhǎng)度為k的路徑數(shù)。 int GetPathNum(AdjMatrix GA,int i,int j,int k,int n) {//求鄰接矩陣方式存儲(chǔ)的有向圖G的頂點(diǎn)i到j(luò)之間長(zhǎng)度為k的簡(jiǎn)單路徑條數(shù) //n為頂點(diǎn)個(gè)數(shù) if(i==j&&k==0) return 1; //找到了一條路徑,且長(zhǎng)度符合要求 else if(k>0) {su

37、m=0; //sum表示通過(guò)本結(jié)點(diǎn)的路徑數(shù) visited[i]=1; for(k=0;k

38、 } return sum; } ? 7.34? 設(shè)計(jì)算法求出以鄰接表存儲(chǔ)的有向圖G中由頂點(diǎn)u到v的所有的簡(jiǎn)單路徑。 　 void AllSPdfs(AdjList g,vertype u,vertype v) ∥求有向圖g中頂點(diǎn)u到頂點(diǎn)v的所有簡(jiǎn)單路徑 { int top=0,s[]; s[++top]=u; visited[u]=1; while(top>0 || p) {p=g[s[top]].firstarc; ∥第一個(gè)鄰接點(diǎn) while(

39、p!=null && visited[p->adjvex]==1) p=p->next; ∥下一個(gè)訪問(wèn)鄰接點(diǎn)表 if(p==null) top--; ∥退棧 else {i=p->adjvex; ∥取鄰接點(diǎn)（編號(hào)） if(i==v) ∥找到從u到v的一條簡(jiǎn)單路徑，輸出 {for(k=1;k<=top;k++) printf( "%3d",s[k]); printf( "%3d\n",v); }∥if

40、 else { visited[i]=1; s[++top]=i; } ∥else深度優(yōu)先遍歷 }∥else }∥while }∥ AllSPdfs ? 7.35 以鄰接表作存儲(chǔ)結(jié)構(gòu)，編寫(xiě)拓?fù)渑判虻乃惴ā? 7.36 試寫(xiě)一算法，判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑（i<>j）。 【題目分析】從Vi深度優(yōu)先遍歷,若在未退出深度優(yōu)先遍歷時(shí)遍歷到Vj，說(shuō)明Vi間Vj存在路徑 int visited[n]; ∥設(shè)有向圖有n個(gè)頂點(diǎn) int Pathitoj(AdjList g,int

41、 Vi,int Vj) ∥ 判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑 {if(Vi==Vj) return 1; ∥Vi到頂點(diǎn)Vj存在路徑 else{visited[Vi]=1; for(p=g[Vi].firstarc;p;p=p->next) {k=p->adjvex; if(!visited[k] && Pathitoj(g,k, Vj)) return 1; }∥for return 0; ∥∥Vi到頂點(diǎn)Vj不存在路徑 }∥else }∥結(jié)束 【算

42、法討論】若頂點(diǎn)vi和vj 不是編號(hào)，必須先用頂點(diǎn)定位函數(shù),查出其在鄰接表頂點(diǎn)向量中的下標(biāo)。下面再對(duì)本題用非遞歸算法求解如下。 int Connectij (AdjList g , vertype Vi , Vj ) ∥判斷n個(gè)頂點(diǎn)以鄰接表表示的有向圖g中，頂點(diǎn) Vi 各Vj 是否有路徑，有則返回1，否則返回0 {for(i=1;i

43、stack[],top=0;stack[++top]=i; while(top>0) {k=stack[top--]; p=g[k].firstarc; while(p && visited[p->adjvex]==1) p=p->next;∥查第k個(gè)鏈表中第一個(gè)未訪問(wèn)的弧結(jié)點(diǎn) if(p==null) top--; else {i=p->adjvex; if(i==j) return(1); ∥頂點(diǎn)Vi和Vj 間有路徑 else {visited[i]=1; stack[++top]=i;} }∥else }while return(0); ∥頂點(diǎn)Vi和V

44、j間無(wú)通路 } ? 7.37假設(shè)有向圖G以十字鏈表形式存儲(chǔ)，試寫(xiě)一個(gè)判斷該有向圖中是否有環(huán)路（回路）的算法。 【題目分析】有幾種方法判斷有向圖是否存在環(huán)路，這里使用拓?fù)渑判蚍?。?duì)有向圖的頂點(diǎn)進(jìn)行拓?fù)渑判?，若拓?fù)渑判虺晒?，則無(wú)環(huán)路；否則，存在環(huán)路。題目已假定有向圖用十字鏈表存儲(chǔ)，為方便運(yùn)算，在頂點(diǎn)結(jié)點(diǎn)中，再增加一個(gè)入度域indegree，存放頂點(diǎn)的入度。入度為零的頂點(diǎn)先輸出。為節(jié)省空間，入度域還起棧的作用。值得注意的是，在鄰接表中，頂點(diǎn)的鄰接點(diǎn)非常清楚，頂點(diǎn)的單鏈表中的鄰接點(diǎn)域都是頂點(diǎn)的鄰接點(diǎn)。由于十字鏈表邊（?。┙Y(jié)點(diǎn)個(gè)數(shù)與邊（弧）個(gè)數(shù)相同（不象無(wú)向圖邊結(jié)點(diǎn)個(gè)數(shù)是邊的二倍），因此，對(duì)某

45、頂點(diǎn)v, 要判斷其鄰接點(diǎn)是headvex還是tailvex。 int Topsor(OrthList g) ∥判斷十字鏈表為存儲(chǔ)結(jié)構(gòu)的有向圖g是否有環(huán)，如是返回1，否則返回0 {int top=-1; ∥用作棧頂指針 for(i=0;iheadvex==i) p=p->headlink; else p=p

46、->taillink; ∥找頂點(diǎn)i的鄰接點(diǎn) }∥while(p) }∥for for(i=1;i<=n;i++) if(g[i].indegree==0){g[i].indegree=top;top=i;}∥建入度為0頂點(diǎn)的棧 m=0; ∥m為計(jì)數(shù)器，記輸出頂點(diǎn)個(gè)數(shù) while(top<>-1) {i=top; top=g[top].indegree; m++; ∥top指向下一入度為0的頂點(diǎn) p=g[i].firstout; while(p) ∥處理頂點(diǎn)i的各鄰接點(diǎn)的入度 {if(p->tailvex==i) k=p->headv

47、ex; else k=p->tailvex; ∥找頂點(diǎn)i的鄰接點(diǎn) g[k].indegree--; ∥鄰接點(diǎn)入度減1 if(g[k].indegree==0) {g[k].indegree=top; top=k; } ∥入度為0的頂點(diǎn)再入棧 if(p->headvex==i) p=p->headlink; else p=p->taillink;∥找頂點(diǎn)i的下一鄰接點(diǎn) }∥while(p) }∥ while(top<>0) if(m

48、無(wú)環(huán)路 }∥算法結(jié)束 ? 7.38已知n個(gè)頂點(diǎn)的有向圖，用鄰接矩陣表示，編寫(xiě)函數(shù)，計(jì)算每對(duì)頂點(diǎn)之間的最短路徑。 本題用FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) ∥求具有n個(gè)頂點(diǎn)的有向圖每對(duì)頂點(diǎn)間的最短路徑 {AdjMatrix length; ∥length[i][j]存放頂點(diǎn)vi到vj的最短路徑長(zhǎng)度。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) length[i][j]=g[i][j]; ∥初始化。 for(k=

49、1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(length[i][k]+length[k][j]

50、短路徑長(zhǎng)度為K的頂點(diǎn)均在第K+1層?？捎藐?duì)列存放頂點(diǎn)，將遍歷訪問(wèn)頂點(diǎn)的操作改為入隊(duì)操作。隊(duì)列中設(shè)頭尾指針f和r，用level表示層數(shù)。 void bfs_K(graph g,int v0,K) ∥輸出無(wú)向連通圖g中距頂點(diǎn)v0最短路徑長(zhǎng)度為K的頂點(diǎn) {int Q[]; ∥Q為頂點(diǎn)隊(duì)列，容量足夠大 int f=0,r=0,t=0; ∥f和r分別為隊(duì)頭和隊(duì)尾指針，t指向當(dāng)前層最后頂點(diǎn) int level=0,flag=0;∥層數(shù)和訪問(wèn)成功標(biāo)記 visited[v0]=1; ∥設(shè)v0為根 Q[++r]=v0; t=r;

51、 level=1; ∥v0入隊(duì) while(f

52、 }∥if w=GraphNextAdj(g ,v ,w); }∥while(w!=0) if(f==t) {level++；t=r; } ∥當(dāng)前層處理完，修改層數(shù)，t指向下一層最后一個(gè)頂點(diǎn) }∥while(f

53、列，其入隊(duì)和出隊(duì)操作同步，其核心語(yǔ)句段如下： 　　QueueInit(Q1) ; QueueInit(Q2); ∥Q1和Q2是頂點(diǎn)和頂點(diǎn)所在層次數(shù)的隊(duì)列 visited[v0]=1; ∥訪問(wèn)數(shù)組初始化，置v0被訪問(wèn)標(biāo)記 level=1; flag=0; ∥是否有層次為K的頂點(diǎn)的標(biāo)志 QueueIn(Q1,v0); QueueIn(Q2,level); ∥頂點(diǎn)和層數(shù)入隊(duì)列 while(!empty(Q1) && level<=K+1) {v=QueueOut(Q1); level=QueueOut(Q2);∥頂點(diǎn)和層數(shù)出隊(duì)

54、 w=GraphFirstAdj(g,v0); while(w!=0) ∥鄰接點(diǎn)存在 {if(visited[w]==0) if(level==K+1) {printf("距離頂點(diǎn)v0最短路徑長(zhǎng)度為K的頂點(diǎn)是%d\n",w); visited[w]=1; flag=1; QueueIn(Q1 ,w); QueueIn(Q2,level+1); } w=GraphNextAdj(g ,v ,w); }∥while(w!=0)

55、 }∥while(!empty(Q1) && level0)個(gè)頂點(diǎn)的無(wú)向連通圖G， 可以鄰接矩陣Anxn存儲(chǔ)，由于鄰接矩陣的對(duì)稱(chēng)性，只將其下三角順序存儲(chǔ)在數(shù)組S中。請(qǐng)編寫(xiě)對(duì)以數(shù)組S存儲(chǔ)的圖G進(jìn)行寬度優(yōu)先遍歷的算法。 【題目分析】 由寬度優(yōu)先遍歷的定義，首先訪問(wèn)任一頂點(diǎn)，然后訪問(wèn)該頂點(diǎn)的未曾訪問(wèn)的鄰接點(diǎn)，如此下去，直至全部頂點(diǎn)訪問(wèn)完成。在鄰接矩陣中，第i行非零元素都是第i個(gè)頂點(diǎn)的鄰接點(diǎn)，而在壓縮存儲(chǔ)下，找某頂點(diǎn)的鄰接點(diǎn)要遍歷整個(gè)數(shù)組。矩陣元

56、素的下標(biāo)i和j和其在一維數(shù)組S中的序號(hào)k的關(guān)系： 由 得 和j=k-i(i+1)/2 在一維數(shù)組中，只有非零元素才是頂點(diǎn)。為簡(jiǎn)單計(jì)，當(dāng)訪問(wèn)完一個(gè)頂點(diǎn)后，就將其在一維數(shù)組中的位序置零；由于是圖的遍歷，當(dāng)全部頂點(diǎn)訪問(wèn)完后就直接結(jié)束算法。 #define n 用戶圖的頂點(diǎn)數(shù) #define m n(n+1)/2 int nodes=0, visited[n]={0}; ∥頂點(diǎn)計(jì)數(shù)和訪問(wèn)標(biāo)志數(shù)組 void index(int k,*i,*k) ∥由非零元素在一維數(shù)組S中的序號(hào)k計(jì)算其在鄰接矩陣中的下標(biāo)i和j {*i= é(-3+sqrt(9+8*k))/2

57、ù; *j=k-(*i)*(*i+1)/2 } void Tri_bfs(int v) ∥對(duì)下三角存儲(chǔ)的無(wú)向連通圖作寬度優(yōu)先遍歷，v是遍歷的開(kāi)始頂點(diǎn) {nodes++; QueueInit(Q); QueueIn(Q,v); printf(v); visited[v]=1; ∥初始化 while(!QueueEmpty(Q) && nodes<=n) {v=QueueOut(Q); for(k=0; k

58、零元素在鄰接矩陣中的下標(biāo) if(i==v || j==v) ∥頂點(diǎn)i或j是頂點(diǎn)v {if(i==v) ∥頂點(diǎn)i是頂點(diǎn)v {if(visited[j]==0) ∥頂點(diǎn)j是頂點(diǎn)v的鄰接點(diǎn)，且尚未訪問(wèn) {nodes++; printf(j); visited[j]=1; s[k]=0; QueueIn(Q,j); } else ∥頂點(diǎn)j是頂點(diǎn)v {if(visited[i]==0) ∥頂點(diǎn)i是頂點(diǎn)v的鄰接點(diǎn)，且尚未訪問(wèn) {nodes++; printf(i); visited[i]=1; s[k]=0; QueueIn(Q,i); }∥ } } } } }∥算法結(jié)束 [算法討論]對(duì)于連通圖，進(jìn)入BFS一次就可訪問(wèn)完圖的全部頂點(diǎn)；對(duì)于非連通圖，進(jìn)入BFS一次就可訪問(wèn)完圖的一個(gè)連通分量。若要遍歷全部頂點(diǎn)，在調(diào)用BFS的函數(shù)中加入語(yǔ)句： for(vi=0; vi