習題集解析部分

第7章 圖

——《數據結構題集》-嚴蔚敏.吳偉民版

       源碼使用說明  鏈接☛☛☛ 《數據結構-C語言版》（嚴蔚敏,吳偉民版）課本源碼+習題集解析使用說明

       課本源碼合輯  鏈接☛☛☛ 《數據結構》課本源碼合輯

       習題集全解析  鏈接☛☛☛ 《數據結構題集》習題解析合輯

      相關測試數據下載  鏈接☛ 數據包

      本習題文檔的存放目錄：數據結構\▼配套習題解析\▼07 圖

      文檔中源碼的存放目錄：數據結構\▼配套習題解析\▼07 圖\▼習題測試文檔-07

      源碼測試數據存放目錄：數據結構\▼配套習題解析\▼07 圖\▼習題測試文檔-07\Data

一、基礎知識題

7.1❶已知如下圖所示的有向圖，請給出該圖的

(1)每個頂點的入/出度；

(2)鄰接矩陣；

(3)鄰接表；

(4)逆鄰接表；

(5)強連通分量。

7.2❷已知有向圖的鄰接矩陣為An×n，試問每一個A(k)n×n(k=1,2,…,n)各具有何種實際含義?

7.3❷畫出下圖所示的無向圖的鄰接多重表，使得其中每個無向邊結點中第一個頂點號小於第二個頂點號，且每個頂點的各鄰接邊的鏈接順序，為它所鄰接到的頂點序號由小到大的順序。列出深度優先和廣度優先搜索遍歷該圖所得頂點序列和邊的序列。

7.4❷試對以下所示的無向圖，畫出其廣度優先生成森林。

7.5❷已知以二維數組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點1出發進行遍歷所得的深度優先生成樹和廣度優先生成樹。

7.6❺試證明教科書7.4.2節中求強連通分量的演算法（深度優先搜索）的正確性。

7.7❷請對下圖的無向帶權圖，

(1)寫出它的鄰接矩陣，並按普里姆演算法求其最小生成樹；

(2)寫出它的鄰接表，並按克魯斯卡爾演算法求其最小生成樹。

7.8❷試對以下所示無向圖執行求關節點的演算法，分別求出每個頂點的visited[i]和low[i]值，i=1,2, …,vexnum。

7.9❷試列出下圖中全部可能的拓撲有序序列，並指出應用7.5.1節中演算法Topological Sort求得的是哪一個序列（註意：應先確定其存儲結構）。

7.10❷對於下圖所示的AOE網路，計算各活動弧的e(ai)和l(aj)函數值、各事件(頂點)的ve(vi)和vl(vj)函數值；列出各條關鍵路徑。

7.11❷試利用Dijkstra演算法求下圖中從頂點a到其他各頂點間的最短路徑，寫出執行演算法過程中各步的狀態。

7.12❹試證明求最短路徑的Dijkstra演算法的正確性。

7.13❷試利用Floyd演算法求下圖所示有向圖中各對頂點之間的最短路徑。

轉載註明出處：原文鏈接

二、演算法設計題

鄰接表

7.14❸編寫演算法，由依次輸入的頂點數目、弧的數目、各頂點的信息和各條弧的信息建立有向圖的鄰接表。

鄰接矩陣

7.15❸試在鄰接矩陣存儲結構上實現圖的基本操作:InsertVex(G,v)，InsertArc(G,v,w)，DeleteVex(G,v)和DeleteArc(G,v,w)。

鄰接表

7.16❸試對鄰接表存儲結構重做7.15題。

十字鏈表

7.17❸試對十字鏈表存儲結構重做7.15題。

鄰接多重表

7.18❸試對鄰接多重表存儲結構重做7.15題。

7.19❸編寫演算法，由依次輸入的頂點數目、邊的數目、各頂點的信息和各條邊的信息建立無向圖的鄰接多重表。

鄰接矩陣

7.20❸下麵的演算法段可以測定圖G=(V,E)是否可傳遞： trans = TRUE; for(V中的每個x) for(N(x)中的每個y) for(N(y)中不等於x的每個z) if(z不在N(x)中) trans = FALSE; 其中N(x)表示x鄰接到的所有頂點的集合。試以鄰接矩陣存儲結構實現判定一個圖的可傳遞性的演算法，並通過n=|V|，m=|E|和d=結點度數的均值，估計執行時間。

鄰接表

7.21❸試對鄰接表存儲結構重做7.20題。

7.22❸試基於圖的深度優先搜索策略寫一演算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點vi到頂點vj的路徑(i≠j)。註意：演算法中涉及的圖的基本操作必須在此存儲結構上實現。

7.23❸同7.22題要求。試基於圖的廣度優先搜索策略寫一演算法。

鄰接矩陣

7.24❸試利用棧的基本操作編寫，按深度優先搜索策略遍歷一個強連通圖的非遞歸形式的演算法。演算法中不規定具體的存儲結構，而將圖Graph看成是一種抽象的數據類型。

類似鄰接表

7.25❺假設對有向圖中n個頂點進行自然編號，並以三個數組s[1…max],fst[1…n]和lst[1…n]表示之。其中數組s存放每個頂點的後繼頂點的信息，第i個頂點的後繼頂點存放在s中下標從fst[i]起到lst[i]的分量中(i=1,2,…,n)。若fst[i]>lst[i]，則第i個頂點無後繼頂點。試編寫判別該有向圖中是否存在迴路的演算法。

鄰接矩陣

7.26❺試證明，對有向圖中頂點適當地編號，可使其鄰接矩陣為下三角形且主對角線為全零的充要條件是：該有向圖不含迴路。然後寫一演算法對無環有向圖的頂點重新編號，使其鄰接矩陣變為下三角形，並輸出新舊編號對照表。

鄰接表

7.27❹採用鄰接表存儲結構，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的演算法（一條路徑為簡單路徑指的是其頂點序列中不含有重現的頂點)。

7.28❺已知有向圖和圖中兩個頂點u和v，試編寫演算法求有向圖中從u到v的所有簡單路徑，並以下圖為例手工執行你的演算法，畫出相應的搜索過程圖。

鄰接矩陣

7.29❺試寫一個演算法，在以鄰接矩陣方式存儲的有向圖G中求頂點i到頂點j的不含迴路的、長度為k的路徑數。

7.30❺試寫一個求有向圖G中所有簡單迴路的演算法。

十字鏈表

7.31❸試完成求有向圖的強連通分量的演算法，並分析演算法的時間複雜度。

鄰接表

7.32❷試修改普里姆演算法，使之能在鄰接表存儲結構上實現求圖的最小生成森林，並分析其時間複雜度（森林的存儲結構為孩子-兄弟鏈表）。

7.33❺已知無向圖的邊集存放在某個類型為EdgeSetType的數據結構EdgeSet 中（沒有端點相重的環邊），併在此結構上已定義兩種基本運算:

(1)函數GetMinEdge(EdgeSet, u, v)：若EdgeSet非空，則必存在最小邊，變參u和v分別含最小邊上兩頂點，並返回true；否則返回false；

(2)過程DelMinEdge(EdgeSet, u, v)：從EdgeSet中刪除依附於頂點u和v的最小邊。 試在上述結構上實現求最小生成樹（以孩子-兄弟鏈表表示）的克魯斯卡爾演算法。

7.34❸試編寫一個演算法，給有向無環圖G中每個頂點賦以一個整數序號，並滿足以下條件：若從頂點i至頂點j有一條弧，則應使i<j。

7.35❹若在DAG(有向無環圖)圖中存在一個頂點r，在r和圖中所有其他頂點之間均存在由r出發的有向路徑，則稱該DAG圖有根。試編寫求DAG圖的根的演算法。

7.36❹在圖的鄰接表存儲結構中，為每個頂點增加一個MPL域。試寫一演算法，求有向無環圖G的每個頂點出發的最長路徑的長度，並存入其MPL域。請給出演算法的時間複雜度。

7.37❺試設計一個求有向無環圖中最長路徑的演算法，並估計其時間複雜度。

7.38❸一個四則運算算術表達式以有向無環圖的鄰接表方式存儲，每個操作數原子都由單個字母表示。寫一個演算法輸出其逆波蘭表達式。

二叉鏈表

7.39❸把存儲結構改為二叉鏈表，重做7.38題。

鄰接表

7.40❸若7.38題的運算符和操作數原子分別由字元和整數表示，請設計鄰接表的結點類型，並且寫一個表達式求值的演算法。

7.41❹試編寫利用深度優先遍歷有向圖實現求關鍵路徑(CPM)的演算法。

7.42❹以鄰接表作存儲結構實現求從源點到其餘各頂點的最短路徑的Dijkstra演算法。