課后答案網(wǎng) 7 章 圖 一、基礎(chǔ)知識(shí)題 無向圖的頂點(diǎn)個(gè)數(shù)為 n，則該圖最多有多少條邊？ 【解答】 n(2 個(gè) 邊的個(gè)數(shù)至少為多少？ 【解答】 連通具有 少需要多少條弧 ? 【解答】 n 7.4 n 個(gè)頂點(diǎn)的完全有向圖含有弧的數(shù)目是多少 ? 【解答】 n(個(gè)有 少有多少個(gè)連通分量，最多有多少個(gè)連通分量。 【解答】 1, n 的 成樹的樹高要小于等于同圖 成樹的樹高，對(duì) 嗎？ 【解答】對(duì) 向圖 G=(V,E)，其中： V=a,b,c,d,e,f，E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，寫出對(duì)該圖從頂點(diǎn) 【解答】 圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的 法的時(shí)間復(fù)雜度是多少？ 【解答】 O(n+e) 一個(gè)具有 該森林中必有多少棵樹？ 【解答】 n 個(gè)頂點(diǎn)的無向圖的鄰接矩陣至少有多少非零元素？ 【解答】 0 明 :具有 一定不是樹。 【證明】 具有 n 個(gè)頂點(diǎn) 邊的無向連通圖是自由樹，即沒有確定根結(jié)點(diǎn)的樹，每個(gè)結(jié)點(diǎn)均可當(dāng)根。若邊數(shù)多于 一條邊要連接兩個(gè)結(jié)點(diǎn)，則必因加上這一條邊而使兩個(gè)結(jié)點(diǎn)多了一條通路，即形成回路。形成回路的連通圖不再是樹。 明對(duì)有向圖頂點(diǎn)適當(dāng)編號(hào)，使其鄰接矩陣為下三角形且主對(duì)角線為全零的充要條件是該圖是無環(huán)圖。 課后答案網(wǎng) 證明】 該有向圖頂點(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ì)該類有向無環(huán)圖頂點(diǎn)編號(hào)，應(yīng)按頂點(diǎn)出度的大小進(jìn)行順序編號(hào)。） G=(V， E)以鄰接表存儲(chǔ)，如圖所示，試畫出從頂點(diǎn) 1 出發(fā)所得到的深度優(yōu)先和廣度優(yōu)先生成樹。 習(xí)題 圖 【解答】 深度優(yōu)先生成樹 1 2 3 4 5 寬度優(yōu)先生成樹： 1 2 3 4 5 課后答案網(wǎng) 知一個(gè)圖的頂點(diǎn)集 分別為： 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ù)湫蛄小?【解答】 1帶權(quán)無向圖的鄰接矩陣如下圖 ，試畫出它的一棵最小生成樹。 習(xí)題 圖 習(xí)題 圖 【解答】 設(shè)頂點(diǎn)集合為 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 課后答案網(wǎng) 圖所示是一帶權(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) 起點(diǎn)的廣度優(yōu)先遍歷的頂點(diǎn)序列及對(duì)應(yīng)的生成樹； （ 3）以頂點(diǎn) 起點(diǎn)的深度優(yōu)先遍歷生成樹； （ 4）由頂點(diǎn) 頂點(diǎn) 33 36 25 18 10 29 38 30 42 1 4 3 2 6 5 【解答】 (1) (2)2,6,5 1 2 4 6 3 5 課后答案網(wǎng) 3) 頂點(diǎn)集合 V(G)=2,4,6 邊的集合 E(G)=, (4) 短路徑為 67: ( 知一有向網(wǎng)的鄰接矩陣如下，如需在 其中一個(gè)頂點(diǎn)建立娛樂中心，要求該頂點(diǎn)距其它各頂點(diǎn)的最長往返路程最短，相同條件下總的往返路程越短越好，問娛樂中心應(yīng)選址何處？給出解題過程。 習(xí)題 圖 習(xí)題 圖 【解答】 下面用 法求出任意兩頂點(diǎn)的最短路徑（如圖 A（ 6） 所示）。題目要求娛樂中心“距其它各結(jié)點(diǎn)的最長往返路程最短”，結(jié)點(diǎn) 。按著“相同條件下總的往返路徑越短越好”，選頂點(diǎn)的往返路徑是 34。 A(0)=A(1)=A(2)=A(3)=A(4)=A(5)=A(6)=出圖中頂點(diǎn) 1到其余各頂點(diǎn)的最短路徑。 【解答】本表中 各列最下方的數(shù)字是頂點(diǎn) 1到頂點(diǎn)的最短通路。 迭代 集合 S 選擇 頂點(diǎn) D D2 D3 D4 D5 D6 初值 33 29 25 1 33 29 25 2 3 67 29 71 3 3 67 71 4 v1,v2, 67 71 5 v1,v6,v2,v3,v 71 所選頂點(diǎn) S（已確定最短路徑 的頂點(diǎn)集合） T(尚未確定最短 路徑的頂點(diǎn)集合 ) 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,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 課后答案網(wǎng) 點(diǎn) 1到其它 頂點(diǎn)的最短路徑依次是 20， 31， 28， 10， 17， 25， 35。按 ， 6， 2， 7， 4， 3， 8。 圖示的 絡(luò)，計(jì)算各活動(dòng)弧的 e( l(函數(shù)值，各事件（頂點(diǎn)）的 函數(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 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 C F H G W ，長 52。 關(guān)鍵路徑是： 活動(dòng)與頂點(diǎn)的對(duì)照表： a1 a2 a3 a4 a5 a6 a7 a8 a9 利用弗洛伊德算法，寫出如圖所示相應(yīng)的帶權(quán)鄰接矩陣的變化。 3 2 1 4 5 9 6 8 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 課后答案網(wǎng) 3 1 10 【解答】 1=3=、算法設(shè)計(jì)題 無向圖 G有 編寫用鄰接表存儲(chǔ)該圖的算法。 g)建立有 m 條邊的無向圖的鄰接表存儲(chǔ)結(jié)構(gòu) n,m; %d%d,&n,&m); i=0,j; p-gigip; 將邊結(jié)點(diǎn)鏈入 p=(); p-i; p-gjgjp; 算法 束 課后答案網(wǎng) 知有向圖有 編寫算法，根據(jù)用戶輸入的偶對(duì)建立該有向圖的鄰接表。 g)建立有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) n; %d,&n); i=0;j; p-gigip; 出以十字鏈表作存儲(chǔ)結(jié)構(gòu)，建立圖的算法，輸入 (i， j， v)其中 i， j 為頂點(diǎn)號(hào)， g)建立有向圖的十字鏈表存儲(chǔ)結(jié)構(gòu) i,j,v; 假定權(quán)值為整型 %d,&n); i=0,j; p-i; p-v;弧結(jié)點(diǎn)中權(quán)值域 p-gjgjp; p-gigip; %d%d%d,&i,&j,&v); 算法結(jié)束 算法討論 本題已假定輸入的 i 和 否則 ,頂點(diǎn)的信息要輸入 ,且用頂點(diǎn)定位函數(shù)求出頂點(diǎn)在頂點(diǎn)向量中的下標(biāo)。圖 建立時(shí)，若已知邊數(shù)（如上面 1 和 2題），可以用 環(huán)；若不知邊數(shù)，可用 環(huán)（如本題），規(guī)定輸入特殊數(shù)（如本題的零值）時(shí)結(jié)束運(yùn)行。本題中數(shù)值設(shè)為整型，否則應(yīng)以和數(shù)值類型相容的方式輸入。 課后答案網(wǎng) 有向圖 G有 用 1， 2， ， e 條邊，寫一算法根據(jù) G 的鄰接表生成 求算法時(shí)間復(fù)雜性為 O(n+e)。 將有向圖的出度鄰接表改為按入度建立的逆鄰接表 i=0;s=();申請(qǐng)結(jié)點(diǎn) 空間 s-i; s-jjs; p=p-下一個(gè)鄰接點(diǎn)。 出從圖的鄰接表表示轉(zhuǎn)換成鄰接矩陣表示的算法。 將圖的鄰接表表示轉(zhuǎn)換為鄰接矩陣表示 i=0;1;p=p- 算法結(jié)束 寫出把圖的鄰接矩陣表示轉(zhuǎn)換為鄰接表表示的算法。 將圖的鄰接矩陣表示轉(zhuǎn)換為鄰接表表示 i=0;j;頂點(diǎn) I 的鄰接點(diǎn)是 j p-gli glip; 鏈入頂點(diǎn) i 的鄰接點(diǎn)鏈表中 編寫建立有 g) 建立有 e 條邊的無向圖的鄰接多重表的存儲(chǔ)結(jié)構(gòu) n,e; %d%d,&n,&e); i=0,i; p-j; p-gip-gjgip; gjp; 算法結(jié)束 知某有向圖（ n 個(gè)結(jié)點(diǎn)）的鄰接表，求該圖各結(jié)點(diǎn)的入度數(shù)。 【題目分析】 在有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)中求頂點(diǎn)的入度，需要遍歷整個(gè)鄰接表。 g)求以鄰接表為存儲(chǔ)結(jié)構(gòu)的 n 個(gè)頂點(diǎn)有向圖的各頂點(diǎn)入度 i=0;i) ; p=p- 頂點(diǎn) %d 的入度為： %dn” ,gi 設(shè)頂點(diǎn)數(shù)據(jù)為整型 課后答案網(wǎng) 知無向圖 G=(V， E)，給出求圖 【題目分析】 使用圖的遍歷可以求出圖的連通分量。進(jìn)入 次， 就可以訪問到圖的一個(gè)連通分量的所有頂點(diǎn)。 v) v=1; “ %3d” ,v); 輸出連通分量的頂點(diǎn)。 p=gvp!=p-0） p- p=p- 求圖中連通分量的個(gè)數(shù) k=0 ; g ; 設(shè)無 向圖 g 有 i=0;j) if(gip-p-p); 釋放空間 p; p=p- 沿鏈表繼續(xù)查找 p=gj 刪頂點(diǎn) j 的邊結(jié)點(diǎn) (j,i) p) if(p-i) 課后答案網(wǎng) if(gjp- p-p); 釋放空間 p; p=p- 沿鏈表繼續(xù)查找 算法討論】 算法中假定給的 i， j 均存在，否則應(yīng)檢查其合法性。若未給頂點(diǎn)編號(hào)，而給出頂點(diǎn)信息，則先 用頂點(diǎn)定位函數(shù)求出其在鄰接表頂點(diǎn)向量中的下標(biāo) i和 j。 設(shè)有向圖以鄰接表存儲(chǔ)，試編寫算法刪除弧 的算法。 g,vi, 刪除以鄰接表存儲(chǔ)的有向圖 假定頂點(diǎn) i=g, j=g, 頂點(diǎn)定位 p=gi p) if(p-j) if(gip-p-p); 釋放結(jié)點(diǎn)空間 p; p=p- 結(jié)束 設(shè)計(jì)一個(gè)算法利用遍歷圖的方法判別一個(gè)有向圖 G 中是否存在從頂點(diǎn) 長度為 k 的簡單路徑，假設(shè)有向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)。 【題目分析】本題利用深度優(yōu)先遞歸的搜索方法判斷有向圖 G 的頂點(diǎn) i 到 j 是否存在長度為 k 的簡單路 徑，先找到 m，再從 m到 j 的長度為 簡單路徑。 ,i,j,k) /判斷鄰接表方式存儲(chǔ)的有向圖 G 的頂點(diǎn) i到 j 是否存在長度為 k 的簡單路徑 if(i=j&k=0) ; /找到了一條路徑 ,且長度符合要求 if(k0) i=1; p=ip;p=p- m=p- 課后答案網(wǎng) m) if(,m,j, ; /剩余路徑長度減一 i=0; /本題允許曾經(jīng)被訪問過的結(jié)點(diǎn)出現(xiàn)在另一條路徑中 ; /沒找到 設(shè)有向圖 G 采用鄰接矩陣存儲(chǔ)，編寫算法求出 G 中頂點(diǎn) j 的不含回路的、長度為 k 的路徑數(shù)。 A,i,j,k,n) /求鄰接矩陣方式存儲(chǔ)的有向圖 i到 k 的簡單路徑條數(shù) /n 為頂點(diǎn)個(gè)數(shù) if(i=j&k=0) ; /找到了一條路徑 ,且長度符合要求 if(k0) ; / i=1; k=0;| p) p=gs 第一個(gè)鄰接點(diǎn) p!=& p-=1) p=p-下一個(gè)訪問鄰接點(diǎn)表 if(p=退棧 i=p-取鄰接點(diǎn)（編號(hào)） if(i=v) 找到從 u 到 v 的一條簡單路徑，輸出 k=1; 【題目分析】 從 若在未退出深度優(yōu)先遍歷時(shí)遍歷到 明 n; 設(shè)有向圖有 n 個(gè)頂點(diǎn) g,i,j) 判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn) i=; 頂點(diǎn) 在路徑 i=1; p=gp;p=p-k=p-k & g,k, ; ; 頂點(diǎn) 存在路徑 課后答案網(wǎng) 結(jié)束 【算法討論】 若頂點(diǎn) 是編號(hào)，必須先用頂點(diǎn)定位函數(shù) ,查出其在鄰接表頂點(diǎn)向量中的下標(biāo)。下面再對(duì)本題用非遞歸算法求解如下。 g , i , 判斷 g 中，頂點(diǎn) 否有路徑，有則返回 1，否則返回 0 i=1;k= p=gkp & p-=1) p=p-查第 k 個(gè)鏈表中第一個(gè)未訪問的弧結(jié)點(diǎn) if(p=i=p-if(i=j) ); 頂點(diǎn) j 間有路徑 i=1; +i; ); 頂點(diǎn) 設(shè)有向圖 G 以十字鏈表形式存儲(chǔ)，試寫 一個(gè)判斷該有向圖中是否有環(huán)路（回路）的算法。 【題目分析】 有幾種方法判斷有向圖是否存在環(huán)路，這里使用拓?fù)渑判蚍?。?duì)有向圖的頂點(diǎn)進(jìn)行拓?fù)渑判颍敉負(fù)渑判虺晒?，則無環(huán)路；否則，存在環(huán)路。題目已假定有向圖用十字鏈表存儲(chǔ)，為方便運(yùn)算，在頂點(diǎn)結(jié)點(diǎn)中，再增加一個(gè)入度域放頂點(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ù)相同（不象無向圖邊結(jié)點(diǎn)個(gè)數(shù)是邊的二倍 ），因此，對(duì)某頂點(diǎn) v, 要判斷其鄰接點(diǎn)是 是 g) 判斷十字鏈表為存儲(chǔ)結(jié)構(gòu)的有向圖 g 是否有環(huán)，如是返回 1，否則返回0 課后答案網(wǎng) 1; 用作棧頂指針 i=0;i) p=p- p=p-找頂點(diǎn) p) i=1; i=gm+; 向下一入度為 0 的頂點(diǎn) p=gi p) 處理頂點(diǎn) if(p-i) k=p- k=p-找頂點(diǎn) gk鄰接點(diǎn)入度減 1 if(gk0) gkk; 入度為 0 的頂點(diǎn)再入棧 if(p-i) p=p- p=p-找頂點(diǎn) p) 頂點(diǎn)的無向連通圖 G， 可以鄰接矩陣 于鄰接矩陣的對(duì)稱性，只將其下三角順序存 儲(chǔ)在數(shù)組 S 中。請(qǐng)編寫對(duì)以數(shù)組 S 存儲(chǔ)的圖 【題目分析】 由寬度優(yōu)先遍歷的定義，首先訪問任一頂點(diǎn)，然后