【文章內(nèi)容簡介】 1條邊的圖不一定是生成樹 第七章 圖 生成樹 V5 V1 V2 V4 V3 V7 V6 V8 例 深度： V1? V2 ?V4 ? V8 ?V5?V3 ?V6 ?V7 V1 V2 V4 V5 V3 V7 V6 V8 深度優(yōu)先生成樹 V1 V2 V4 V5 V3 V7 V6 V8 廣度優(yōu)先生成樹 廣度： V1? V2 ?V3 ? V4 ?V5?V6 ?V7 ?V8 V5 V1 V2 V4 V3 V7 V6 V8 V5 V1 V2 V4 V3 V7 V6 V8 第七章 圖 生成樹 例 A B L M C F D E G H K I J A B L M C F J D E G H K I 深度優(yōu)先生成森林 第七章 圖 生成樹 最小生成樹 問題提出 假設要在 n 個城市之間建立通訊聯(lián)絡網(wǎng)，則連通 n 個城市只需要修建 n1條線路， 如何在最節(jié)省經(jīng)費的前提下建立 這個 通訊網(wǎng) ？ 頂點 ——表示城市 權 ——城市間建立通信線路所需花費代價 最?。ù鷥r）生成樹 ：希望找到一棵生成樹，它的每條邊上的權值之和即建立該通信網(wǎng)所需花費的總代價）最小 第七章 圖 生成樹 問題分析 n個城市間，最多可設置 n(n1)/2條線路 n個城市間建立通信網(wǎng)，只需 n1條線路 該問題等價于 ：構造網(wǎng)的一棵 最小生成樹 ，即： 在 e條帶權的邊中選取 n1條邊 （不構成回路），使 “ 權值之和 ” 為最小 。 1 6 5 4 3 2 7 13 17 9 18 12 7 5 24 10 第七章 圖 生成樹 構造最小生成樹方法 方法一：普里姆 (Prim)算法（選點法） 思想：設 N=(V,{E})是連通網(wǎng)， TE是 N上最小生成樹中邊的集合 （ 1） 初始令 U={u0},(u0?V), TE=? （ 2） 在所有 u?U,v?VU的邊 (u,v)?E中，找一條代價最小的邊 (u0,v0) （ 3） 將 (u0,v0)并入集合 TE， 同時 v0并入 U （ 4） 重復上述操作直至 U=V為止，則 T=(V,{TE})為 N的最小生成樹 樹存儲結構： 鄰接矩陣表示 算法實現(xiàn) 算法評價： O(n178。) 第七章 圖 生成樹 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 5 3 5 2 4 6 1 3 1 4 2 1 1 3 1 6 1 3 1 4 4 6 1 3 1 4 2 5 2 4 6 1 3 1 4 2 第七章 圖 生成樹 方法二：克魯斯卡爾 算法（選邊法） 思想：設 N=(V,{E})是連通網(wǎng)， TE是 N上最小生成樹中邊的集合 （ 1）初始狀態(tài)為只有 n個頂點而無邊的非連通圖 T=(V,{?})，每個頂點自成一個連通分 （ 2）在 E中選取代價最小的邊，若該邊依附的頂點落在 T中不同的連通分量上，則將此邊加入到 T中；否則，舍去此邊，選取下一條代價最小的邊 （ 3） 依此類推，直至 T中所有頂點都在同一連通分量上為止 第七章 圖 生成樹 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 第七章 圖 生成樹 算法描述： 構造非連通圖 ST=( V,{ } )。 k = i = 0。 // k 計選中的邊數(shù) while (kn1) { ++i。 檢查邊集 E 中第 i 條權值最小的邊 (u,v)。 若 (u,v)加入 ST后不使 ST中產(chǎn)生回路 ， 則 輸出邊 (u,v)。 且 k++。 } 第七章 圖 生成樹 普里姆算法 克魯斯卡爾算法 時間復雜度 O(n2) O(eloge) 稠密圖 稀疏圖 算法名 適應范圍 比較兩種算法 第七章 圖 拓撲排序 有向無環(huán)圖 拓撲排序 關鍵路徑 第七章 圖 拓撲排序 有向無環(huán)圖：一個無環(huán)的有向圖 （ DAG） 是描述一項工程或系統(tǒng)的進行過程的有效工具。 第七章 圖 拓撲排序 問題提出：學生選修課程問題 頂點 ——表示課程 有向弧 ——表示先決條件，若課程 i是課程 j的先決條件，則圖中有弧 i,j 學生應按怎樣的順序學習這些課程，才能無矛盾、順利地完成學業(yè) ——拓撲排序 定義 AOV網(wǎng) ——用 頂點 表示 活動 ，用 弧 表示 活動間優(yōu)先關系 的有向圖稱為頂點表示活動的網(wǎng) (Activity On Vertex work)， 簡稱 AOV網(wǎng) ? 若 vi,vj是圖中有向邊，則 vi是 vj的直接前驅； vj是 vi的直接后繼 ? AOV網(wǎng)中 不允許有回路 ，這意味著某項活動以自己為先決條件 第七章 圖 拓撲排序 拓撲排序 ——把 AOV網(wǎng)絡中各頂點 按照 它們 相互之間的優(yōu)先關系 排列成一個線性序列的過程 ? 檢測 AOV網(wǎng)中是否存在環(huán)方法：對有向圖構造其頂點的拓撲有序序列，若 網(wǎng)中所有頂點 都在它的拓撲有序序列中，則該 AOV網(wǎng)必定不存在環(huán) 拓撲排序的方法 在有向圖中選一個 沒有前驅 的頂點且輸出之 從圖中 刪除 該頂點和所有 以它為尾的弧 重復上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止 第七章 圖 拓撲排序 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 無 C1 C1,C2 C1 C3,C4 C11 C3,C6 無 C9 C9 C1,C9,C10 程序設計基礎 離散數(shù)學 數(shù)據(jù)結構 匯編語言 語言的設計和分析 計算機原理 編譯原理 操作系統(tǒng) 高等數(shù)學 線性代數(shù) 普通物理 數(shù)值分析 課程代號 課程名稱 先修課 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 例 第七章 圖 拓撲排序 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓撲序列： C1C2C3C4C5C7C9C10C11C6C12C8 或 ： C9C10C11C6C1C12C4C2C3C5C7C8 一個 AOV網(wǎng)的拓撲序列不是唯一的 第七章 圖 拓撲排序 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 第七章 圖 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓撲排序 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 第七章 圖 拓撲排序 C4 C5 C6 C7 C8 C9 C10 C11 C12 C5 C6 C7 C8 C9 C10 C11 C12 第七章 圖 C6 C8 C9 C10 C11 C12 拓撲排序 C6 C7 C8 C9 C10 C11 C12 C6 C8 C10 C11 C12 C6 C8 C11 C12 第七章 圖 拓撲排序 C6 C8 C12 C8 C12 C8 第七章 圖 拓撲排序 算法實現(xiàn) 以鄰接表作存儲結構 把鄰接表中所有入度為 0的頂點進棧 棧非空時，輸出棧頂元素 Vj并退棧；在鄰接表中查找 Vj的直接后繼 Vk， 把 Vk的入度減 1；若 Vk的 入度為 0則進棧 重復上述操作直至棧空為止。若?？諘r輸出的頂點個數(shù)不是 n， 則有向圖有環(huán)；否則，拓撲排序完畢 第七章 圖 5 5 4 3 2 5 2 4 0 1 2 2 in link ^ ^ ^ vex next 3 ^ ^ 0 1 2 3 4 5 6 ^ 拓撲排序 3 2 1 0 4 例 1 2 3 4 5 6 top 1 6 top top 算法描述 入度 第七章 圖 拓撲排序 5 5 4 3 2 5 2 4 0 1 2 2 in link ^ ^ ^ vex next 3 ^ ^ 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 6 top top 第七章 圖 拓撲排序 輸出序列： 6 3 2 1 0 4 1 top p 5 5 4 3 2 5 2 4 0 1 2 2 in link ^ ^ ^ vex next 3 ^ ^ 0 1 2 3 4 5 6 ^ 第七章 圖 拓撲排序 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 第七章 圖 拓撲排序 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 第七章 圖 拓撲排序 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 第七章 圖 拓撲排序 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p=NULL 第七章 圖 拓撲排序 0 1 1 2 in link 5 5 4 3 ^ ^