[理學(xué)]數(shù)據(jù)結(jié)構(gòu)第7章(參考版)
2025-01-22 14:46本頁面
【正文】 59 習(xí) 題 一、填空題 參見教材 P166 二、選擇題 三、判斷題 四、應(yīng)用題 五、算法設(shè)計題 。 (3) 圖有很多方面的具體應(yīng)用，包括求最小生成樹、求最短路徑以及拓?fù)渑判颉? (2) 圖的遍歷算法是圖的基本算法，使用該算法，可以判斷圖的連通性及求圖的連通分量。 參見教材 P162 【 例 】 編程實現(xiàn) Dijkstra算法。 55 AOV網(wǎng)拓?fù)渑判? 圖(a)～圖 (h)給出了對圖AOV網(wǎng)使用上述算法進行拓?fù)渑判蜞徑渔湵砑皸５淖兓^程。 (4) 重復(fù) (2)和 (3)，直到棧空為止。 (2) 從棧中彈出棧頂元素并輸出，并把該頂點發(fā)出的所有有向邊刪去，即把它的各個鄰接頂點的入度減 1。 53 AOV網(wǎng)拓?fù)渑判? 對于圖 AOV網(wǎng)，其拓?fù)渑判虻倪^程如圖 所示，得到的一個拓?fù)湫蛄袨?(1, 6, 7, 2, 3, 4, 5)。 (3) 重復(fù) (1)和 (2)，直到找不到入度為 0的頂點。 12352 AOV網(wǎng)拓?fù)渑判? 對 AOV網(wǎng)進行拓?fù)渑判虻姆椒ㄈ缦拢? (1) 從 AOV網(wǎng)中選擇一個入度為 0的頂點，并且輸出它。通常，我們把這種頂點表示活動、弧表示活動間先后關(guān)系的有向圖稱作 AOV網(wǎng) (Activity On Vertex Network)。 38712 342 co st= ∞ 7 2 3 ∞ 8 ∞ 4 ∞ D ( 1)= ∞ 7 2 3 ∞ 8 ∞ 4 ∞ p a th ( 1)= 1 1 1 1 1 1 1 1 1 D ( 0) = ∞ 7 2 3 ∞ 5 ∞ 4 ∞ p a th ( 0) = 1 1 1 1 1 1 1 1 1 D ( 1) = ∞ 7 2 3 ∞ 5 7 4 ∞ p a t h ( 1) = 1 1 1 1 1 1 2 1 1 p a t h ( 2) = 1 3 1 1 1 1 2 1 1 D ( 2) = ∞ 6 2 3 ∞ 5 7 4 ∞ 49 AOV網(wǎng)拓?fù)渑判? AOV網(wǎng) 一個較大的工程往往被劃分成許多子工程，我們把這些子工程稱作活動 (activity)。 另一種方法是采用弗洛伊德 (Floyd)算法，此算法比較簡單，易于理解和編程。 圖 718是個有向網(wǎng)，圖 cost，表 ，以 1為源點，應(yīng)用迪杰斯特拉算法求 1到其余各頂點的最短路徑的全過程及各數(shù)據(jù)結(jié)構(gòu)的變化情況。 (4)重復(fù) (3)直到 T中只有一個連通分量為止。 (2)把 G的邊按權(quán)值升序排列。 42 圖 716 Prim 算法構(gòu)造最小生成樹的過程示意圖 A E B F C D A E B F C D A E B F C D A E B F C D A E B F C D A E B F C D (a) (b) (c) (d) (e) (f) 6 8 12 14 16 17 5 15 6 6 6 6 6 8 8 8 8 8 12 12 12 14 14 5 43 克魯斯卡爾 (Kruskal)算法 克魯斯卡爾算法構(gòu)造最小生成樹的基本思想是：假設(shè)G＝ (V, E)是連通網(wǎng)， T＝ (U, TE)為欲構(gòu)造的最小生成樹。 (2)從所有 u∈ U， v∈ VU的邊中，選取具有最小權(quán)值的邊 (u, v)，將頂點 v加入集合 U中，將邊 (u, v)加入集合 TE中。 40 最小生成樹 1．普里姆算法 2．克魯斯卡爾算法 41 普里姆 (Prim)算法 基本思想：假設(shè) G＝ (V, E)是連通網(wǎng)， T＝(U, TE)為欲構(gòu)造的最小生成樹。代價在網(wǎng)中用權(quán)值表示，一個生成樹的代價就是生成樹各邊的代價之和。 12343 ^2 ^1 ^123047657654 3 1 ^7 6 ^42 ^6 4 ^1234567得到的線性序列為 1,2,4,3,5,7,6 37 廣度優(yōu)先搜索 對圖 生成森林如圖 。若此時圖中仍有未被訪問的頂點，則另選一個未被訪問的頂點，開始再做廣度優(yōu)先搜索。 123456735 廣度優(yōu)先搜索 廣
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1