數(shù)據(jù)結(jié)構(gòu)習題解答參考第8章

8入了生成樹與生成森林的概念。對于帶權(quán)圖，給出了最小生成樹的兩種方法：Prim算法和Kruskal算法后者使用了最小堆和并查集作為它的輔助求解在解決最短路徑問題時，PrimKruskal方求解最小生成樹的Kruskaldijkstra算法，注意dist為防止重復已經(jīng)過的頂點，需要設(shè)置一個標志數(shù)組visited對于連通網(wǎng)絡(luò)、可用不會構(gòu)成環(huán)路的權(quán)值最小的n-1會畫出用KruskalPrim6n(n-1)/2。1個頂點的

2 3個頂點的

4 5個頂點的ijjin(n-1)/2條邊。ADADBECFCC→F，C→F→E。DD→B，D→B→C，D→B→C→F，D→ADADBECF

0 0 0Edge0 0A11B22C5∧0A11B22C5∧3D14∧4E∧5F4∧0A∧1B03∧2C3D4E35∧5F

0 0 00 3∧4∧1∧01∧0∧12∧一個圖中有1000個頂點，其鄰接矩陣中的矩陣元素有10002 nn個頂點的有向強連通圖至少有多少條nn-1nnn10ij之間是否有邊相連？任意一個頂點的度是多少？A[i][j]不為零，說明頂②①③④②①③④⑤③④ ③④ ① 操作時，時間代價是O(n*e)？還是O(n+e)O(max(n,e))？需要對所有的頂點一次，所以時間代價是O(n+e)。⑨⑧8-11右圖是通圖，請畫⑨⑧⑩① ⑩①

⑩① ⑩① (1,103,44,55,6)。從③的子孫結(jié)點⑩到③的祖先結(jié)點①引一 8-15Dijkstra算法計算得到的從頂點①(A)到其它各個頂點的最短路徑和最AA5522D2E源點終點AB源點終點ABCDEG=（V，E有nn≥1)n-1有nn≥1)n在AOE(1) (2)(3)(4)(5)(6)(7)(8)(9) (10)(11)(12)(13)(14)(15) 倍在一個具有n個頂點的無向完全圖中，包含有 在一個具有n個頂點的無向圖中，要連通所有頂點則至少需 條邊 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊 對于一個具有n個頂點和e條邊的有向圖和無向圖，若采用鄰接多重表表示，則存 對于一個具有n個頂點和e條邊的無向圖，當分別采用鄰接矩陣、鄰接表和鄰接多 假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣、鄰接表和鄰接多重表表示 對于一個具有n個頂點和e (2)n(n-1)/2,n(n-(3)n- (4)鄰接矩陣,鄰接表,(5) (6)e,(7)出邊,入 (8)2n,n,(9)O(n),O(e/n), (10)O(n2),O(n+e),(11)O(n2), (12)n,n-采用鄰接表的圖的深度優(yōu)先遍歷算法類似于二叉樹的（A采用鄰接表的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（ 復雜性為（C ，利用Kruskal算法產(chǎn)生最小生成樹，其時間復雜性為（D 設(shè)圖中有n個頂點和e條邊，進行深度優(yōu)先搜索的時間復雜度至多為（E 行廣度優(yōu)先搜索的時間復雜性至多為（F 對于一個具有n個頂點和e條邊的無向圖進行拓撲排序時總的時間（ (4)判斷有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用（H AB②③④C,D：①②③④E,F：①②③④G：①n ②n+1 ③n-1 ④n+eH：①求關(guān)鍵路徑的方法 ②求最短路徑的Dijkstra方法③深度優(yōu)先遍歷算 ④廣度優(yōu)先遍歷算 610515726105157235364245(始頂點號，終頂點號，權(quán)值(,,)(,,)(,,)(,,)(,,)(1)選出的邊順序為:始頂點號，終頂點號，權(quán)值(0,3,1)，(3,5,4)，(5,2,2)，(3,4,5)(3,1,5)，(4,1,3)，(1,4,3nijij之間用邊連接，邊上的權(quán)值wijn