7第七章-圖(編輯修改稿)
2025-08-20 10:05 本頁面
【文章內(nèi)容簡介】 , w2, …, wt, 然后再 順序 訪問 w1, w2, …, w t 的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點， … 如此做下去，直到圖中所有頂點都被訪問到為止。 ? 廣度優(yōu)先搜索是一種 分層 的搜索過程 , 每向前走一步可能訪問一批頂點 , 不像深度優(yōu)先搜索那樣有往回退的情況。因此 , 廣度優(yōu)先搜索 不是一個遞歸 的過程。 連通分量 (Connected ponent) ? 當(dāng)無向圖為非連通圖時 , 從圖中某一頂點出發(fā) , 利用 深度優(yōu)先搜索 算法或 廣度優(yōu)先搜索 算法 不可能 遍歷到圖中的所有頂點 , 只能訪問到該頂點所在的最大連通子圖 (連通分量 )的所有頂點。 ? 若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷 , 可求得無向圖的所有連通分量。 圖的連通性問題 ? 求連通分量的算法需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量。 ? 對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。 A C D E I B F O G H J N M L K 非連通無向圖 A H K C D E I B F O G J N M L 非連通圖的連通分量 最小生成樹 ( minimum cost spanning tree ) ? 使用 不同 的遍歷圖的 方法 ，可以得到 不同的生成樹 ；從 不同 的 頂點 出發(fā)，也可能得到 不同的生成樹 。 ? 按照生成樹的定義， n 個頂點的連通 網(wǎng)絡(luò) 的生成樹有 n 個頂點、 n1 條邊 。 ? 構(gòu)造最小生成樹的準(zhǔn)則 ? 必須使用且僅使用該網(wǎng)絡(luò)中的 n1 條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的 n 個頂點； ? 不能 使用產(chǎn)生 回路 的邊； ? 各邊上的權(quán)值的總和達到 最小 。 普里姆 (Prim)算法 ? 普里姆算法的 基本思想 ： 從連通網(wǎng)絡(luò) N = { V, E }中的某一頂點 u0 出發(fā) , 選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊 ( u0, v ), 將其頂點加入到生成樹頂點集合 U中。 以后每一步從 一個頂點在 U 中 ,而 另一個頂點不在 U 中 的各條邊中選擇權(quán)值 最小 的邊 (u, v), 把它的頂點加入到集合 U 中。如此繼續(xù)下去 , 直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合 U 中為止。 25 25 10 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 5 0 4 6 1 3 2 5 0 4 6 1 3 2 10 原圖 (a) (b) 5 0 4 6 1 3 2 10 (c) (d) (e) (f) 5 0 4 6 1 3 2 10 22 12 5 0 4 6 1 2 10 25 14 22 16 12 3 25 22 12 圖 7 . 1 91 25 43656618143321191611( a ) 一 個 連 通 網(wǎng)( e ) 加 入 邊 (2 ， 6)1 25 436511( f ) 加 入 邊 (1 ， 2)1 25 436511( b ) 最 小 生 成 樹 的 初 始 狀 態(tài)1 25 436( c ) 加 入 邊 (2 ， 3)1 25 436( d ) 加 入 邊 (2 ， 4)1 25 4365566616( g ) 加 入 邊 (5 ， 4)1 25 43651161618活動網(wǎng)絡(luò) (Activity Network) ? 計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。 ? 例如，計算機專業(yè)學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。 用頂點表示活動的網(wǎng)絡(luò) (AOV網(wǎng)絡(luò) ) C1 高等數(shù)學(xué) C2 程序設(shè)計基礎(chǔ) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級語言程序設(shè)計 C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計算機原理 C8 課程代號 課程名稱 先修課程 學(xué)生課程學(xué)習(xí)工程圖 C8 C3 C5 C4 C9 C6 C7 C1 C2 ? 可以用有向圖表示一個工程。在這種有向圖中，用頂點表示活動，用有向邊 Vi, Vj表示活動 Vi 必須先于活動 Vj 進行。這種有向圖叫做 頂點表示活動的 AOV網(wǎng)絡(luò) (Activity On Vertices)。 ? 在 AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路 , 即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項活動應(yīng)以自己作為先決條件。 ? 因此，對給定的 AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1