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

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

1、 第 7 章 圖 一、基礎(chǔ)知識題 7.1設(shè)無向圖的頂點個數(shù)為n，則該圖最多有多少條邊？ 【解答】n(n-1)/2 ? 7.2一個n個頂點的連通無向圖，其邊的個數(shù)至少為多少？ 【解答】n-1 ? 7.3要連通具有n個頂點的有向圖，至少需要多少條弧? 【解答】n ? 7.4 n個頂點的完全有向圖含有弧的數(shù)目是多少? 【解答】n(n-1) ? 7.5一個有n個頂點的無向圖，最少有多少個連通分量，最多有多少個連通分量。 【解答】1, n ? 7.6圖的BFS生成樹的樹高要小于等于同圖DFS生成樹的樹高，對嗎？ 【解答】對 ? 7.7無向圖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)}，寫出對該圖從頂點a出發(fā)進行深度優(yōu)先遍歷可能得到的全部頂點序列。 【解答】abedfc, acfdeb, aebdfc, aedfcb ? 7.8 在圖采用鄰接表存儲時，求最小生成樹的 Prim 算法的時間復(fù)雜度是多少？ 【解答】O(n+e) ? 7.9若一個具有n個頂點，e條邊的無向圖是一個森林，則該森林中必有多少棵樹？ 【解答】n-e ? 7.10 n個頂點的無向圖的鄰接矩陣至少有多少非零元素？ 【解答】0 ? 7.11證明:具有n個

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

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

5、 ? ? ? ? ? ? 7.14 已知一個圖的頂點集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>}； 若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照頂點序號從小到大的次序鏈接的，則按教材中介紹的進行拓撲排序的算法，寫出得到的拓撲序列。 【解答】1-3-6-0-2-5-4-7-8 ? 7.15一帶權(quán)無向圖的鄰接矩陣如下圖 ，試畫出它的一棵最小生成樹。

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

7、7.16如圖所示是一帶權(quán)有向圖的鄰接表法存儲表示。其中出邊表中的每個結(jié)點均含有三個字段，依次為邊的另一個頂點在頂點表中的序號、邊上的權(quán)值和指向下一個邊結(jié)點的指針。試求： （1）．該帶權(quán)有向圖的圖形； （2）．從頂點V1為起點的廣度優(yōu)先遍歷的頂點序列及對應(yīng)的生成樹； （3）．以頂點V1為起點的深度優(yōu)先遍歷生成樹； （4）．由頂點V1到頂點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)? 頂點集合V(G)={V1,V2,V3,V4,V5,V6} 邊的集合 E(G)={,,,,} (4)? V1到V3最短路徑為67: (V1—V4—V3) 迭代 集合 S ? 選擇 頂點 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)的鄰接矩陣如下，如需在其中一個頂點建立娛樂中心，要求該頂點距其它各頂點的最長往返路程最短，相同條件下總的往返路程越短越好，問娛樂中心應(yīng)選址何處？給出解題過程。 習(xí)題7.18的圖 習(xí)題7.17 的圖 【解答】下面用FLOYD算法求出任意兩頂點的最短路徑（如圖A（6）所示）。題目要求娛樂中心“距其它各結(jié)點的最長往返路程最短”，結(jié)點V1，V3，V5和V6最長往返路徑最短都是9。按著“相同條件下總的往返路徑越短越好”，選頂點V5，總的往返路徑是34。 A(0)= A(1)= A(2)= A(3)= A

11、(4)= A(5)= A(6)= 7.18求出圖中頂點1到其余各頂點的最短路徑。 【解答】本表中DIST中各列最下方的數(shù)字是頂點1到頂點的最短通路。 所選頂點 S（已確定最短路徑 的頂點集合） T(尚未確定最短 路徑的頂點集合) 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 頂點1到其它頂點的最短路徑依次是20

13、，31，28，10，17，25，35。按Dijkstra算法所選頂點依次是5，6，2，7，4，3，8。 ? 7.19對圖示的AOE網(wǎng)絡(luò)，計算各活動弧的e(ai)和l(ai)的函數(shù)值，各事件（頂點）的ve（vi）和vl (vi)的函數(shù)值，列出各條關(guā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 ? 活動 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 ，長52。 關(guān)鍵路徑是： ? 活動與頂點的對照表：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??????????? 利用弗洛伊德算法，寫出如圖所示相應(yīng)的帶權(quán)鄰接矩陣的變化。 3 2 1 4 5 9 6 8 2 3 1 10 ? ? ? ? ? ? ? ? ? ? ? 【解答】A0= A1= A2= A3= A4= ? 二、算法設(shè)計題 7.21 設(shè)無向圖G有n個頂點，m條邊。試編寫用鄰接表存儲該

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

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

18、的鄰接表存儲結(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 給出以十字鏈表作存儲結(jié)構(gòu)，建立圖的算法，輸入(i，j，v)其中i，j為頂點號，v為權(quán)值。 void CreatOrthList(OrthList g)∥建立有向圖的十字鏈表存儲結(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時,結(jié)束算法運行 {p=(OrArcNode *)malloc(sizeof(OrArcNode)); ∥申請結(jié)點 p->headvex=j; p->tailvex=i; p->weight=v;∥弧結(jié)點中權(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是頂點號,否則,頂點的信息要輸入,且用頂點定位函數(shù)求出頂點在頂點向量中的下標。圖建立時，若已知邊數(shù)（如上面1和2題），可以用for循環(huán)；若不知邊數(shù)，可用while循環(huán)（如本題），規(guī)定輸入特殊數(shù)（如本題的零值）時結(jié)束運行。本題中數(shù)值設(shè)為整型，否則應(yīng)以和數(shù)值類型相容的方式輸入。 ? 7.24 設(shè)有向圖G有n個點(用1，2，…，n表示)，e條邊，寫一算法根據(jù)G的鄰接表生成G的反向鄰接表，要求算法時間復(fù)雜性為O(n+e)。 void InvertAdjList(AdjList gin,gout)∥將有向圖的出度鄰接表改為按入度建立的逆鄰接表

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

23、->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s; p=p->next;∥下一個鄰接點。 }∥while }∥for } ? 7.25 寫出從圖的鄰接表表示轉(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 試寫出把圖的鄰接矩陣表示轉(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;∥頂點I的鄰接點是j p->next=gl[i].firstarc; gl[i].firstarc=p; ∥鏈入頂點i的鄰接點鏈表中 }∥if }∥end ? 7.27 試編寫

26、建立有n個頂點，m條邊且以鄰接多重表為存儲結(jié)構(gòu)表示的無向圖的算法。 void CreatMGraph(AdjMulist g) ∥建立有n個頂點e條邊的無向圖的鄰接多重表的存儲結(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個結(jié)點）的鄰接表，求該圖各結(jié)點的入度數(shù)。 【題目分析】在有向圖的鄰接表存儲結(jié)構(gòu)中求頂點的入度，需要遍歷整個鄰接表。 void Indegree(AdjList g)∥求以鄰接表為存儲結(jié)構(gòu)的n個頂點有向圖

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

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

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

31、式存儲的無向圖g中，刪除邊(i,j) {p=g[i].firstarc; pre=null; ∥刪頂點i 的邊結(jié)點(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; ∥刪頂點j 的邊結(jié)點(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)檢查其合法性。若未給頂點編號，而給出頂點信息，則先用頂點定位函數(shù)求出其在鄰接表頂點向量中的下標i和j。 ? 7.31 假設(shè)有向圖以鄰接表存儲，試編寫算法刪除弧的算法。 void DeleteArc（AdjList g,ver

33、type vi,vj） ∥刪除以鄰接表存儲的有向圖g的一條弧，假定頂點vi和vj存在 {i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); ∥頂點定位 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é)點空間 else {pre=p; p=p->

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

35、到了一條路徑,且長度符合要求 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; //剩余路徑長度減一 } visited[i]=0; //本題允許曾經(jīng)被訪問過的結(jié)點出

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

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

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

39、p!=null && visited[p->adjvex]==1) p=p->next; ∥下一個訪問鄰接點表 if(p==null) top--; ∥退棧 else {i=p->adjvex; ∥取鄰接點（編號） if(i==v) ∥找到從u到v的一條簡單路徑，輸出 {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 以鄰接表作存儲結(jié)構(gòu)，編寫拓撲排序的算法。 7.36 試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑（i<>j）。 【題目分析】從Vi深度優(yōu)先遍歷,若在未退出深度優(yōu)先遍歷時遍歷到Vj，說明Vi間Vj存在路徑 int visited[n]; ∥設(shè)有向圖有n個頂點 int Pathitoj(AdjList g,int

41、 Vi,int Vj) ∥ 判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑 {if(Vi==Vj) return 1; ∥Vi到頂點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到頂點Vj不存在路徑 }∥else }∥結(jié)束 【算

42、法討論】若頂點vi和vj 不是編號，必須先用頂點定位函數(shù),查出其在鄰接表頂點向量中的下標。下面再對本題用非遞歸算法求解如下。 int Connectij (AdjList g , vertype Vi , Vj ) ∥判斷n個頂點以鄰接表表示的有向圖g中，頂點 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個鏈表中第一個未訪問的弧結(jié)點 if(p==null) top--; else {i=p->adjvex; if(i==j) return(1); ∥頂點Vi和Vj 間有路徑 else {visited[i]=1; stack[++top]=i;} }∥else }while return(0); ∥頂點Vi和V

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

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

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

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

48、無環(huán)路 }∥算法結(jié)束 ? 7.38已知n個頂點的有向圖，用鄰接矩陣表示，編寫函數(shù)，計算每對頂點之間的最短路徑。 本題用FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) ∥求具有n個頂點的有向圖每對頂點間的最短路徑 {AdjMatrix length; ∥length[i][j]存放頂點vi到vj的最短路徑長度。 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、短路徑長度為K的頂點均在第K+1層?？捎藐犃写娣彭旤c，將遍歷訪問頂點的操作改為入隊操作。隊列中設(shè)頭尾指針f和r，用level表示層數(shù)。 void bfs_K(graph g,int v0,K) ∥輸出無向連通圖g中距頂點v0最短路徑長度為K的頂點 {int Q[]; ∥Q為頂點隊列，容量足夠大 int f=0,r=0,t=0; ∥f和r分別為隊頭和隊尾指針，t指向當(dāng)前層最后頂點 int level=0,flag=0;∥層數(shù)和訪問成功標記 visited[v0]=1; ∥設(shè)v0為根 Q[++r]=v0; t=r;

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

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

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

54、 w=GraphFirstAdj(g,v0); while(w!=0) ∥鄰接點存在 {if(visited[w]==0) if(level==K+1) {printf("距離頂點v0最短路徑長度為K的頂點是%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， 可以鄰接矩陣Anxn存儲，由于鄰接矩陣的對稱性，只將其下三角順序存儲在數(shù)組S中。請編寫對以數(shù)組S存儲的圖G進行寬度優(yōu)先遍歷的算法。 【題目分析】 由寬度優(yōu)先遍歷的定義，首先訪問任一頂點，然后訪問該頂點的未曾訪問的鄰接點，如此下去，直至全部頂點訪問完成。在鄰接矩陣中，第i行非零元素都是第i個頂點的鄰接點，而在壓縮存儲下，找某頂點的鄰接點要遍歷整個數(shù)組。矩陣元

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

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

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