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