算法與數(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)/27.2一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為多少？【解答】n-1 7.3要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要多少條弧?【解答】n7.4 n個(gè)頂點(diǎn)的完全有向圖含有弧的數(shù)目是多少?【解答】n(n-1)7.5一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖，最少有多少個(gè)連通分量，最多有多少個(gè)連通分量?！窘獯稹?, n7.6圖的BFS生成樹的樹高要小于等于同圖DFS生成樹的樹高，對(duì)嗎？【解答】對(duì)7.7無(wú)向圖G=(V,E)，其中：V=a,b,c,d,e,f，E=(a,b),(a,e),(a,c),(b,e),(c,f),

2、(f,d),(e,d)，寫出對(duì)該圖從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可能得到的全部頂點(diǎn)序列?！窘獯稹縜bedfc, acfdeb, aebdfc, aedfcb7.8 在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的 Prim 算法的時(shí)間復(fù)雜度是多少？【解答】O(n+e)7.9若一個(gè)具有n個(gè)頂點(diǎn)，e條邊的無(wú)向圖是一個(gè)森林，則該森林中必有多少棵樹？【解答】n-e7.10 n個(gè)頂點(diǎn)的無(wú)向圖的鄰接矩陣至少有多少非零元素？【解答】07.11證明:具有n個(gè)頂點(diǎn)和多于n-1條邊的無(wú)向連通圖G一定不是樹?！咀C明】具有n個(gè)頂點(diǎn)n-1條邊的無(wú)向連通圖是自由樹，即沒(méi)有確定根結(jié)點(diǎn)的樹，每個(gè)結(jié)點(diǎn)均可當(dāng)根。若邊數(shù)多于n-1條，因一條邊要

3、連接兩個(gè)結(jié)點(diǎn)，則必因加上這一條邊而使兩個(gè)結(jié)點(diǎn)多了一條通路，即形成回路。形成回路的連通圖不再是樹。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)，在鄰接矩陣中，非零元素（Aij=1）自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現(xiàn)弧頭頂點(diǎn)編號(hào)大于弧尾頂點(diǎn)編號(hào)的弧，否則，就必然存在環(huán)路。（對(duì)該類有向無(wú)環(huán)圖頂點(diǎn)編號(hào)，應(yīng)按頂點(diǎn)出度的

4、大小進(jìn)行順序編號(hào)。）7.13設(shè)G=(V，E)以鄰接表存儲(chǔ)，如圖所示，試畫出從頂點(diǎn)1出發(fā)所得到的深度優(yōu)先和廣度優(yōu)先生成樹。 習(xí)題7.13 的圖【解答】深度優(yōu)先生成樹12345寬度優(yōu)先生成樹：123457.14 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V=0，1，2，3，4，5，6，7；E=，；若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照頂點(diǎn)序號(hào)從小到大的次序鏈接的，則按教材中介紹的進(jìn)行拓?fù)渑判虻乃惴?，寫出得到的拓?fù)湫蛄?。【解答?-3-6-0-2-5-4-7-8 7.15一帶權(quán)無(wú)向圖的鄰接矩陣如下圖 ，試畫出它的一棵最小生成樹。 習(xí)題7.15 的圖 習(xí)題7.16 的圖【解答】設(shè)頂點(diǎn)集合為

5、1，2，3，4，5，6， 由下邊的邏輯圖可以看出，在1，2，3和4，5，6回路中，各任選兩條邊，加上（2，4），則可構(gòu)成9棵不同的最小生成樹。121111131234567.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)的生成樹；（3）以頂點(diǎn)V1為起點(diǎn)的深度優(yōu)先遍歷生成樹；（4）由頂點(diǎn)V1到頂點(diǎn)V3的最短路徑。333625181029383042143265【解答】(1) (2)V1,V2,V4,V6

6、,V3,V5124635(3) 頂點(diǎn)集合V(G)=V1,V2,V3,V4,V5,V6 邊的集合 E(G)=,(4) V1到V3最短路徑為67: (V1V4V3) 迭代 集合 S選擇頂點(diǎn) D D2 D3 D4 D5 D6初值 v1 33 29 251v1, v6v6 33 29 252 v1, v6, v4v433 67 29 71 3 v1, v6, v4, v2v233 67 71 4v1,v6, v4, v2,v3v3 67 71 5v1,v6,v4, v2,v3,v5v 717.17已知一有向網(wǎng)的鄰接矩陣如下，如需在其中一個(gè)頂點(diǎn)建立娛樂(lè)中心，要求該頂點(diǎn)距其它各頂點(diǎn)的最長(zhǎng)往返路程最短，相同

7、條件下總的往返路程越短越好，問(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(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(尚未確定最短

8、路徑的頂點(diǎn)集合) DIST2345678初態(tài)12,3,4,5,6,7,83060105 1,52,3,4,6,7,82560101761,5,62,3,4,7,8 203360172521,5,6,23,4,7,82033602571,5,6,2,73,4,83128253541,5,6,2,7,43,831283531,5,6,2,7,4,35,8313581,5,6,2,7,4,3,8835頂點(diǎn)1到其它頂點(diǎn)的最短路徑依次是20，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

9、)的函數(shù)值，各事件（頂點(diǎn)）的ve（vi）和vl (vi)的函數(shù)值，列出各條關(guān)鍵路徑?！窘獯稹宽旤c(diǎn)ABCDEFGHWVe(i)016342413392252Vl(i)02924373113392252活動(dòng)a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17e(i)000016633424131313392222l(i)281803292431343731203613392240aCFHGW，長(zhǎng)52。 關(guān)鍵路徑是： 活動(dòng)與頂點(diǎn)的對(duì)照表：a1 a2 a3 a4 a5 a6 a7 a8a9 a10 a11 a12 a13 a14 a15 a16 a177.20 利用弗洛

10、伊德算法，寫出如圖所示相應(yīng)的帶權(quán)鄰接矩陣的變化。3214596823110【解答】A0= A1= A2= A3= A4= 二、算法設(shè)計(jì)題7.21 設(shè)無(wú)向圖G有n個(gè)頂點(diǎn)，m條邊。試編寫用鄰接表存儲(chǔ)該圖的算法。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,in;i+)輸入頂點(diǎn)信息,建立頂點(diǎn)向量 scanf(&gi.vertex); gi.firstarc=null;for(k=0;kadjvex=j; p-next=gi.firstarc; gi.firstarc=p; 將

11、邊結(jié)點(diǎn)鏈入 p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=i;p-next=gj.firstarc;gj.frstarc=p;for 算法CreatGraph結(jié)束7.22 已知有向圖有n個(gè)頂點(diǎn)，請(qǐng)編寫算法，根據(jù)用戶輸入的偶對(duì)建立該有向圖的鄰接表。void CreatAdjList(AdjList g)建立有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)int n;scanf(%d,&n);for(i=0;iadjvex=j;p-next=gi.firstarc;gi.firstarc=p;scanf(&v1,&v2);while 7.23 給出以十字鏈表作存儲(chǔ)結(jié)構(gòu)，建立圖的算

12、法，輸入(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,iheadvex=j;p-tailvex=i;p-weight=v;弧結(jié)點(diǎn)中權(quán)值域 p-headlink=gj.firstin; gj.firstin=p; p-tailink=gi.firstout; gi.firstout=p;scanf(%d%d%d,&i,&j,&v);while 算法結(jié)束算法討論 本題已假定輸入的i和j是頂點(diǎn)號(hào),否則,頂點(diǎn)的信息要輸入,且用頂點(diǎn)定位函數(shù)求

13、出頂點(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ù)值類型相容的方式輸入。7.24 設(shè)有向圖G有n個(gè)點(diǎn)(用1，2，n表示)，e條邊，寫一算法根據(jù)G的鄰接表生成G的反向鄰接表，要求算法時(shí)間復(fù)雜性為O(n+e)。void InvertAdjList(AdjList gin,gout)將有向圖的出度鄰接表改為按入度建立的逆鄰接表 for(i=0;in;i+)設(shè)有向圖有n個(gè)頂點(diǎn)，建逆鄰接表的頂點(diǎn)向量。 gini.vertex=gouti.vertex; g

14、ini.firstarc=null; for(i=0;iadjvex; s=(ArcNode *)malloc(sizeof(ArcNode);申請(qǐng)結(jié)點(diǎn)空間 s-adjvex=i; s-next=ginj.firstarc; ginj.firstarc=s; p=p-next;下一個(gè)鄰接點(diǎn)。 while for 7.25 寫出從圖的鄰接表表示轉(zhuǎn)換成鄰接矩陣表示的算法。void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)將圖的鄰接表表示轉(zhuǎn)換為鄰接矩陣表示for(i=0;in;i+) 設(shè)圖有n個(gè)頂點(diǎn)，鄰接矩陣初始化 for(j=0;jn;j+) gmi

15、j=0; 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;in;i+) 鄰接表表頭向量初始化。 scanf(&gli.vertex); gli.firstarc=null; for(i=0;in;i+) for(j=0;jadjvex=j;頂點(diǎn)I的鄰接點(diǎn)是jp-next=gli.firstarc; gli.firstarc=p; 鏈入頂點(diǎn)i的鄰接點(diǎn)鏈表中if end7

16、.27 試編寫建立有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,in;i+) 建立頂點(diǎn)向量 scanf(&gi.vertex);gi.firstedge=null; for(k=0;kivex=i; p-jvex=j; p-ilink=gi.firstedge; p-jlink=gj.firstedge;gi.firstedge=p; gj.firstedge=p;for 算法結(jié)束7.28 已知某有向圖

17、（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)有向圖的各頂點(diǎn)入度f(wàn)or(i=0;in;j+)num=0;入度初始為0for(j=0;jadjvex=i) num+; p=p-next; printf(“頂點(diǎn)%d的入度為：%dn”,gi.vexdata,num); 設(shè)頂點(diǎn)數(shù)據(jù)為整型 7.29 已知無(wú)向圖G=(V，E)，給出求圖G的連通分量個(gè)數(shù)的算法?！绢}目分析】使用圖的遍歷可以求出圖的連通分量。進(jìn)入dfs或bfs一次，就可以訪問(wèn)到圖的一個(gè)連通分量的所

18、有頂點(diǎn)。void dfs (v)visitedv=1; printf (“%3d”,v); 輸出連通分量的頂點(diǎn)。p=gv.firstarc;while(p!=null) if（visitedp-adjvex=0） dfs(p-adjvex); p=p-next;while dfs void Count() 求圖中連通分量的個(gè)數(shù) int k=0 ; static AdjList g ; 設(shè)無(wú)向圖g有n個(gè)結(jié)點(diǎn) for(i=0;iadjvex=j) if(pre=null)gi.firstarc=p-next; else pre-next=p-next; free(p);釋放空間 else pre=

19、p; p=p-next; 沿鏈表繼續(xù)查找p=gj.firstarc; pre=null; 刪頂點(diǎn)j 的邊結(jié)點(diǎn)(j,i)while(p) if(p-adjvex=i) if(pre=null)gj.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ǔ)，試編寫算法刪除弧的算法。void D

20、eleteArc（AdjList g,vertype vi,vj） 刪除以鄰接表存儲(chǔ)的有向圖g的一條弧，假定頂點(diǎn)vi和vj存在i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); 頂點(diǎn)定位 p=gi.firstarc; pre=null;while(p) if(p-adjvex=j) if(pre=null) gi.firstarc=p-next;else pre-next=p-next;free(p);釋放結(jié)點(diǎn)空間 else pre=p; p=p-next;結(jié)束7.32 設(shè)計(jì)一個(gè)算法利用遍歷圖的方法判別一個(gè)有向圖G中是否存在從頂點(diǎn)Vi到V

21、j的長(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; /找到了一條路徑,且長(zhǎng)度符合要求 else if(k0) visitedi=1; for(p=G.verticesi.firstarc;p;p=p-next) m

22、=p-adjvex; if(!visitedm) if(existpathlen(G,m,j,k-1) return 1; /剩余路徑長(zhǎng)度減一 visitedi=0; /本題允許曾經(jīng)被訪問(wèn)過(guò)的結(jié)點(diǎn)出現(xiàn)在另一條路徑中 return 0; /沒(méi)找到 7.33 設(shè)有向圖G采用鄰接矩陣存儲(chǔ)，編寫算法求出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; /找到了一條路徑,且

23、長(zhǎng)度符合要求 else if(k0) sum=0; /sum表示通過(guò)本結(jié)點(diǎn)的路徑數(shù) visitedi=1; for(k=0;k0 | p) p=gstop.firstarc; 第一個(gè)鄰接點(diǎn) while(p!=null & visitedp-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,sk); printf( %3dn,v);if else visitedi=1; s+top=i;

24、else深度優(yōu)先遍歷 else while AllSPdfs7.35 以鄰接表作存儲(chǔ)結(jié)構(gòu)，編寫拓?fù)渑判虻乃惴ā?.36 試寫一算法，判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑（ij）?！绢}目分析】從Vi深度優(yōu)先遍歷,若在未退出深度優(yōu)先遍歷時(shí)遍歷到Vj，說(shuō)明Vi間Vj存在路徑int visitedn; 設(shè)有向圖有n個(gè)頂點(diǎn)int Pathitoj(AdjList g,int Vi,int Vj) 判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑if(Vi=Vj) return 1; Vi到頂點(diǎn)Vj存在路徑 elsevisitedVi=1; for(p=gVi.

25、firstarc;p;p=p-next) k=p-adjvex; if(!visitedk & Pathitoj(g,k, Vj) return 1; for return 0; Vi到頂點(diǎn)Vj不存在路徑else 結(jié)束 【算法討論】若頂點(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，否則返回0for(i=1;i0)k=stacktop-; p=gk.first

26、arc;while(p & visitedp-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 visitedi=1; stack+top=i;else whilereturn(0); 頂點(diǎn)Vi和Vj間無(wú)通路 7.37假設(shè)有向圖G以十字鏈表形式存儲(chǔ)，試寫一個(gè)判斷該有向圖中是否有環(huán)路（回路）的算法?！绢}目分析】有幾種方法判斷有向圖是否存在環(huán)路，這里使用拓?fù)渑判蚍ā?duì)有向圖的頂點(diǎn)進(jìn)行拓?fù)渑判?，若拓?fù)渑判虺晒?，則無(wú)環(huán)路；否則，存在環(huán)路。題目

27、已假定有向圖用十字鏈表存儲(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)。由于十字鏈表邊（弧）結(jié)點(diǎn)個(gè)數(shù)與邊（?。﹤€(gè)數(shù)相同（不象無(wú)向圖邊結(jié)點(diǎn)個(gè)數(shù)是邊的二倍），因此，對(duì)某頂點(diǎn)v, 要判斷其鄰接點(diǎn)是headvex還是tailvex。int Topsor(OrthList g)判斷十字鏈表為存儲(chǔ)結(jié)構(gòu)的有向圖g是否有環(huán)，如是返回1，否則返回0int top=-1; 用作棧頂指針 for(i=0;iheadvex=i) p=p-hea

28、dlink; else p=p-taillink; 找頂點(diǎn)i的鄰接點(diǎn)while(p) forfor(i=1;i=n;i+) if(gi.indegree=0)gi.indegree=top;top=i;建入度為0頂點(diǎn)的棧m=0; m為計(jì)數(shù)器，記輸出頂點(diǎn)個(gè)數(shù)while(top-1) i=top; top=gtop.indegree; m+; top指向下一入度為0的頂點(diǎn) p=gi.firstout; while(p) 處理頂點(diǎn)i的各鄰接點(diǎn)的入度 if(p-tailvex=i) k=p-headvex; else k=p-tailvex; 找頂點(diǎn)i的鄰接點(diǎn) gk.indegree-; 鄰接點(diǎn)入度減

29、1 if(gk.indegree=0) gk.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(top0)if(mn) retun(1)有向圖存在環(huán)路; else return(0); 有向圖無(wú)環(huán)路算法結(jié)束7.38已知n個(gè)頂點(diǎn)的有向圖，用鄰接矩陣表示，編寫函數(shù)，計(jì)算每對(duì)頂點(diǎn)之間的最短路徑。本題用FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) 求具有n個(gè)頂點(diǎn)的有向圖每對(duì)頂點(diǎn)間的最短路徑 A

30、djMatrix length; lengthij存放頂點(diǎn)vi到vj的最短路徑長(zhǎng)度。 for(i=1;i=n;i+) for(j=1;j=n;j+) lengthij=gij; 初始化。 for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(lengthik+lengthkjlengthij) lengthij=lengthik+lengthkj; 算法結(jié)束7.39設(shè)計(jì)算法求距離頂點(diǎn)V0的最短路徑長(zhǎng)度(以弧數(shù)為單位)為K的所有頂點(diǎn)，要求盡可能地節(jié)省時(shí)間。【題目分析】 本題應(yīng)用寬度優(yōu)先遍歷求解。若以v0作生成樹的根為第層，則距頂點(diǎn)v0最短路徑長(zhǎng)度為

31、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)記 visitedv0=1; 設(shè)v0為根 Q+r=v0; t=r; level=1; v0入隊(duì) while(fr & level=K+1) v=Q+f; w=GraphFirstAdj(g,v

32、); while(w!=0) w!=0 表示鄰接點(diǎn)存在 if(visitedw=0) Q+r=w; visitedw=1;鄰接點(diǎn)入隊(duì)列 if(level=K+1) printf(距頂點(diǎn)v0最短路徑為k的頂點(diǎn)%d ,w); flag=1; if w=GraphNextAdj(g ,v ,w); while(w!=0) if(f=t) level+；t=r; 當(dāng)前層處理完，修改層數(shù)，t指向下一層最后一個(gè)頂點(diǎn) while(fr & level=K+1) if(flag=0) printf( 圖中無(wú)距v0頂點(diǎn)最短路徑為%d的頂點(diǎn)。n,K);算法結(jié)束 算法討論本題亦可采取另一個(gè)算法。由于在生成樹中結(jié)點(diǎn)的

33、層數(shù)等于其雙親層次數(shù)加1，故可設(shè)頂點(diǎn)和層次數(shù)個(gè)隊(duì)列，其入隊(duì)和出隊(duì)操作同步，其核心語(yǔ)句段如下：QueueInit(Q1) ; QueueInit(Q2); Q1和Q2是頂點(diǎn)和頂點(diǎn)所在層次數(shù)的隊(duì)列 visitedv0=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ì) w=GraphFirstAdj(g,v0); wh

34、ile(w!=0) 鄰接點(diǎn)存在 if(visitedw=0) if(level=K+1) printf(距離頂點(diǎn)v0最短路徑長(zhǎng)度為K的頂點(diǎn)是%dn,w); visitedw=1; flag=1; QueueIn(Q1 ,w); QueueIn(Q2,level+1); w=GraphNextAdj(g ,v ,w); while(w!=0) while(!empty(Q1) & level0)個(gè)頂點(diǎn)的無(wú)向連通圖G， 可以鄰接矩陣Anxn存儲(chǔ)，由于鄰接矩陣的對(duì)稱性，只將其下三角順序存儲(chǔ)在數(shù)組S中。請(qǐng)編寫對(duì)以數(shù)組S存儲(chǔ)的圖G進(jìn)行寬度優(yōu)先遍歷的算法。【題目分析】 由寬度優(yōu)先遍歷的定義，首先訪問(wèn)任一頂

35、點(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ù)組。矩陣元素的下標(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)/2int nodes=0, visitedn=0; 頂點(diǎn)計(jì)數(shù)和訪問(wèn)標(biāo)志數(shù)組void index(int k,*i,*k) 由非零

36、元素在一維數(shù)組S中的序號(hào)k計(jì)算其在鄰接矩陣中的下標(biāo)i和j *i= (-3+sqrt(9+8*k)/2; *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); visitedv=1; 初始化 while(!QueueEmpty(Q) & nodes=n) v=QueueOut(Q); for(k=0; km; k+) if(sk!=0) index(k,&i,&j); 求非零元素在鄰接矩陣中的下標(biāo) if(i=v | j=v

37、) 頂點(diǎn)i或j是頂點(diǎn)v if(i=v) 頂點(diǎn)i是頂點(diǎn)v if(visitedj=0) 頂點(diǎn)j是頂點(diǎn)v的鄰接點(diǎn)，且尚未訪問(wèn) nodes+; printf(j); visitedj=1; sk=0; QueueIn(Q,j); else 頂點(diǎn)j是頂點(diǎn)v if(visitedi=0) 頂點(diǎn)i是頂點(diǎn)v的鄰接點(diǎn)，且尚未訪問(wèn) nodes+; printf(i); visitedi=1; sk=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; vin;vi+) if(visitedvi=0) Tri_bfs(vi);