【文章內(nèi)容簡介】 ication Engineering V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍歷： V1? V2 ?V4 ? V8 ?V3 ?V6 ?V7 ?V5 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 2 廣度優(yōu)先遍歷 (BFS) 從圖的某一頂點 V0出發(fā)，訪問此頂點后，依次訪問 V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止 V1 V2 V4 V5 V3 V7 V6 V8 例 BFS： V1? V2 ?V3 ? V4 ? V5 ?V6 ?V7 ?V8 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering V1 V2 V4 V5 V3 V7 V6 V8 例 例 V1 V2 V4 V5 V3 V7 V6 V8 BFS： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 BFS： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering V1 V2 V4 V5 V3 V7 V6 V8 例 BFS： V1? V2 ?V3 ? V4 ?V6 ?V7 ?V8 ?V5 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 一、生成樹 所有頂點均由邊連接在一起，但不存在回路的圖 . 一個圖可以有許多棵不同的生成樹 。所有生成樹具有以下共同特點： ? 生成樹的頂點個數(shù)與圖的頂點個數(shù)相同 ? 生成樹是圖的極小連通子圖 ? 一個有 n個頂點的連通圖的生成樹有 n1條邊 ? 生成樹中任意兩個頂點間的路徑是唯一的 ? 在生成樹中再加一條邊必然形成回路 ? 含 n個頂點 n1條邊的圖不一定是生成樹 G H K I 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering V1 V2 V4 V5 V3 V7 V6 V8 深度優(yōu)先生成樹 V1 V2 V4 V5 V3 V7 V6 V8 廣度優(yōu)先生成樹 V1 V2 V4 V5 V3 V7 V6 V8 V1 V2 V4 V5 V3 V7 V6 V8 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 例 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)先生成森林 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 最小生成樹 問題提出 :n個城市間，最多可設置 n(n1)/2條線路 n個城市間建立通信網(wǎng)，只需 n1條線路 問題轉(zhuǎn)化為：如何在可能的線路中選擇 n1條，能把 所有城市（頂點）均連起來，且總耗費 （各邊權值之和）最小 問題分析 要在 n個城市間建立通信聯(lián)絡網(wǎng)， 頂點 —— 表示城市 權 —— 城市間建立通信線路所需花費代價 希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網(wǎng)所需花費的總代價）最小 ——— 最小代價生成樹 1 6 5 4 3 2 7 13 17 9 18 12 7 5 24 10 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 方法一：普里姆 (Prim)算法 方法二：克魯斯卡爾 (Kruskal)算法 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 6 5 4 3 2 1 2 3 4 5 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 二、拓撲排序 定義 AOV網(wǎng) —— 用頂點表示活動，用弧表示活動間優(yōu)先關系的有向圖稱為頂點表示活動的網(wǎng) (Activity On Vertex work)， 簡稱 AOV網(wǎng) 若 vi,vj是圖中有向邊，則 vi是 vj的直接前驅(qū)；vj是 vi的直接后繼 AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件 軟 件 技 術 基 礎 主講：李中 電子與通信工程系 Department of Electronic and Communication Engineering 拓撲排序 —— 把 AOV網(wǎng)絡中各頂點按照它們相互之間的優(yōu)先關系排列成一個線性序列的過程 檢測 AOV網(wǎng)中是否存在環(huán)方法：對有向圖構造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該 AOV網(wǎng)必定不存在環(huán) 拓撲排序的方法 1. 在有向圖中選一個沒有前驅(qū)的頂點且輸出之 2. 從圖中刪除該頂點和所有以它為尾的弧 3. 重復上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅(qū)的頂點