數(shù)據(jù)結(jié)構(gòu)答案 job8

8-1 畫出1個頂點、2個頂點、3個頂點、4個頂點和5個頂點的無向完全圖。試證明在n個頂點的無向完全圖中，邊的條數(shù)為n(n-1)/2。8-2 右邊的有向圖是強連通的嗎？請列出所有的簡單路徑。8-3 給出右圖的鄰接矩陣、鄰接表和鄰接多重表表示。8-4 用鄰接矩陣表示圖時，若圖中有1000個頂點，1000條邊，則形成的鄰接矩陣有多少矩陣元素？有多少非零元素？是否稀疏矩陣？【解答】一個圖中有1000個頂點，其鄰接矩陣中的矩陣元素有10002 = 1000000個。它有1000個非零元素（對于有向圖）或2000個非零元素（對于無向圖），因此是稀疏矩陣。8-5 用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？【解答】用鄰接矩陣表示圖，矩陣元素的個數(shù)是頂點個數(shù)的平方，與邊的條數(shù)無關(guān)。矩陣中非零元素的個數(shù)與邊的條數(shù)有關(guān)。8-6 有n個頂點的無向連通圖至少有多少條邊？有n個頂點的有向強連通圖至少有多少條邊？試舉例說明?！窘獯稹縩個頂點的無向連通圖至少有n-1條邊，n個頂點的有向強連通圖至少有n條邊。例如：8-7對于有n個頂點的無向圖，采用鄰接矩陣表示，如何判斷以下問題： 圖中有多少條邊？任意兩個頂點i和j之間是否有邊相連？任意一個頂點的度是多少？【解答】用鄰接矩陣表示無向圖時，因為是對稱矩陣，對矩陣的上三角部分或下三角部分檢測一遍，統(tǒng)計其中的非零元素個數(shù)，就是圖中的邊數(shù)。如果鄰接矩陣中Aij 不為零，說明頂點i與頂點j之間有邊相連。此外統(tǒng)計矩陣第i行或第i列的非零元素個數(shù)，就可得到頂點i的度數(shù)。8-8對于如右圖所示的有向圖，試寫出：(1) 從頂點出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 8-9 試擴充深度優(yōu)先搜索算法，在遍歷圖的過程中建立生成森林的左子女-右兄弟鏈表。算法的首部為viod Graph:DFS ( const int v, int visited , TreeNode * t ) 其中，指針t指向生成森林上具有圖頂點v信息的根結(jié)點。（提示：在繼續(xù)按深度方向從根v的某一未訪問過的鄰接頂點w向下遍歷之前，建立子女結(jié)點。但需要判斷是作為根的第一個子女還是作為其子女的右兄弟鏈入生成樹。）8-10 用鄰接表表示圖時，頂點個數(shù)設(shè)為n，邊的條數(shù)設(shè)為e，在鄰接表上執(zhí)行有關(guān)圖的遍歷操作時，時間代價是O(n*e)？還是O(n+e)？或者是O(max(n,e)？【解答】在鄰接表上執(zhí)行圖的遍歷操作時，需要對鄰接表中所有的邊鏈表中的結(jié)點訪問一次，還需要對所有的頂點訪問一次，所以時間代價是O(n+e)。8-15 右圖是一個連通圖，請畫出(1) 以頂點為根的深度優(yōu)先生成樹；(2) 如果有關(guān)節(jié)點，請找出所有的關(guān)節(jié)點。(3) 如果想把該連通圖變成重連通圖，至少在圖中加幾條邊？如何加？ 【解答】(1) 從頂點出發(fā)的深度優(yōu)先生成樹為 此答案不唯一(2) 8-16試證明在一個有n個頂點的完全圖中，生成樹的數(shù)目至少有2n-1-1。8-17 編寫一個完整的程序，首先定義堆和并查集的結(jié)構(gòu)類型和相關(guān)操作，再定義Kruskal求連通網(wǎng)絡(luò)的最小生成樹算法的實現(xiàn)。并以右圖為例，寫出求解過程中堆、并查集和最小生成樹的變化。8-18 利用Dijkstra算法的思想，設(shè)計一個求最小生成樹的算法。8-19以右圖為例，按Dijkstra算法計算得到的從頂點到其它各個頂點的最短路徑和最短路徑長度。8-20 在以下假設(shè)下，重寫Dijkstra算法：(1) 用鄰接表表示帶權(quán)有向圖G，其中每個邊結(jié)點有3個域：鄰接頂點vertex，邊上的權(quán)值length和邊鏈表的鏈接指針link。(2)用集合T = V(G) - S代替S(已找到最短路徑的頂點集合)，利用鏈表來表示集合T。試比較新算法與原來的算法，計算時間是快了還是慢了，給出定量的比較。8-22使用Floyd算法計算8-19題所用的帶權(quán)有向圖的各對頂點之間的最短路徑。8-23 下面是基于元素0到4的一些優(yōu)先關(guān)系的集合，試問它們是否定義了一個偏序關(guān)系？為什么？01;13;12;23;24;40 8-24 試證明：對于一個無向圖G = (V, E)，若G中各頂點的度均大于或等于2，則G中必有回路?！窘獯稹糠醋C法：對于一個無向圖G=（V，E），若G中各頂點的度均大于或等于2，則G中沒有回路。此時從某一個頂點出發(fā)，應(yīng)能按拓?fù)溆行虻捻樞虮闅v圖中所有頂點。但當(dāng)遍歷到該頂點的另一鄰接頂點時，又可能回到該頂點，沒有回路的假設(shè)不成立。8-25 設(shè)有一個有向圖存儲在鄰接表中。試設(shè)計一個算法，按深度優(yōu)先搜索策略對其進(jìn)行拓?fù)渑判颉２⒁杂覉D為例檢驗?zāi)愕乃惴ǖ恼_性?！窘獯稹?1) 定義鄰接表結(jié)構(gòu)const n = ;頂點個數(shù)type pointer = node node = record adj : integer;鄰接頂點號 cost : real;邊上的權(quán)值 link : pointer; end; vex = record ind : integer;頂點入度 fout : pointer;出邊表頭指針 end; nodelist = array1.n of vex;鄰接表 另設(shè)一個輔助數(shù)組，記錄訪問順序：visited : array1.n of integer。 初始時，各結(jié)點的visitedi均為0。 還有一個訪問計數(shù)count，初始時為0。(2) 拓?fù)渑判蛩惴╬rocedure dfs ( G : nodelist; v : integer );var w : integer; p : pointer; begin count := count + 1;visitedv := count; p := Gv.fout; while p nil do begin w := p.adj; Gw.ind := Gw.ind - 1; if ( visitedw = 0 ) and ( Gw.ind = 0 ) then dfs ( G, w ); p := p.link; end; end;主程序for i := 1 to n do visitedi := 0;count := 0;read ( i, j, w);while ( i 0 ) and ( j 0 ) do begin new(p); p.adj := j; p.cost := w; Gj.ind := Gj.ind + 1; p.link := Gi.fout; Gi.fout := p; read ( i, j, w); end;for i := 1 to n do if ( visitedi = 0 ) and ( Gi.ind = 0 ) then dfs ( G, i );if count n then write (排序失敗);8-26 試對右圖所示的AOE網(wǎng)絡(luò)(1) 這個工程最早可能在什么時間結(jié)束。(2) 求每個活動的最早開始時間e( )和最遲開始時間l( )。(3) 確定哪些活動是關(guān)鍵活動。 【解答】按拓?fù)溆行虻捻樞蛴嬎愀鱾€頂點的最早可能開始時間Ve和最遲允許開始時間Vl。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間l，根據(jù)l - e = 0? 來確定關(guān)鍵活動，從而確定關(guān)鍵路徑。 1 2 3 4 5 6 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43 e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38l-e 17 0 0 8 0 12 8 0此工程最早完成時間為43。關(guān)鍵路徑為8-27 若AOE網(wǎng)絡(luò)的每一項活動都是關(guān)鍵活動。令G是將該網(wǎng)絡(luò)的邊去掉方向和權(quán)后得到的無向圖。 (1) 如果圖中有一條邊處于從開始頂點到完成頂點的每一條路徑上，則僅加速該邊表示的活動就