【正文】 *firstout。 //指向以該頂點(diǎn)為弧尾的第一個弧結(jié)點(diǎn) }DD。 DD g[M]。 //g[0]不用 data firstin firstout 例 b d a c a b c d 1 2 3 4 1 3 1 2 3 4 3 1 4 3 4 2 4 1 ^ ^ ^ ^ ^ ^ ^ ^ 藍(lán)色 —— 鄰接表 ，綠色 —— 第 2個域值相同的結(jié)點(diǎn)鏈 ?無向圖的鄰接多重表表示法 頂點(diǎn)結(jié)點(diǎn)： typedef struct dnode { int data。 //存與頂點(diǎn)有關(guān)的信息 struct node *firstedge。 //指向第一條依附于該頂點(diǎn)的邊 }DD。 DD ga[M]。 //ga[0]不用 data firstedge 邊結(jié)點(diǎn)： typedef struct node { int mark。 //標(biāo)志域 int ivex, jvex。 //該邊依附的兩個頂點(diǎn)在表頭數(shù)組中位置 struct node *ilink, *jlink。 //分別指向依附于 ivex和 jvex的下一條邊 }JD。 mark ivex ilink jvex jlink 例 a e c b d 1 2 3 4 a c d b 5 e 1 2 1 4 3 4 3 2 3 5 5 2 ^ ^ ^ ^ ^ 167。 圖的遍歷 (P167) ?深度優(yōu)先遍歷 (DFS) ?方法：從圖的某一頂點(diǎn) V0出發(fā)，訪問此頂點(diǎn)；然后依次從 V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和 V0相通的頂點(diǎn)都被訪問到；若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止 V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍歷： V1? V2 ?V4 ? V8 ?V5 ?V3 ?V6 ?V7 V1 V2 V4 V5 V3 V7 V6 V8 例 例 V1 V2 V4 V5 V3 V7 V6 V8 深度遍歷： V1? V2 ?V4 ? V8 ?V5 ?V6 ?V3 ?V7 或 V1? V2 ?V4 ? V8 ?V6 ?V3 ?V7 ?V5 或 … 深度遍歷： V1? V2 ?V4 ? V8 ?V5 ?V6 ?V3 ?V7 V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍歷： V1? V2 ?V4 ? V8 ?V3 ?V6 ?V7 ?V5 ?深度優(yōu)先遍歷算法 ?遞歸算法 開始 訪問 V0,置 標(biāo)志 求 V0鄰接點(diǎn) 有鄰接點(diǎn) w 求下一鄰接點(diǎn) w?V0 W訪問過 結(jié)束 N Y N Y DFS 開始 標(biāo)志數(shù)組初始化 Vi=1 Vi訪問過 DFS Vi=Vi+1 Vi==Vexnums 結(jié)束 N N Y Y V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍歷： V1? 1 2 3 4 1 3 4 2 vexdata firstarc 2 7 8 3 ^ ^ ^ adjvex next 5 5 6 4 1 ^ 5 1 2 8 2 ^ 6 7 8 6 7 8 7 3 6 3 5 4 ^ ^ ^ V3 ? V7 ? V6 ? V2 ? V5 ? V8 ? V4 V1 V2 V4 V5 V3 V7 V6 V8 例 1 2 3 4 1 3 4 2 vexdata firstarc 2 7 8 3 ^ ^ ^ adjvex next 5 5 6 ^ 4 8 2 ^ 6 7 8 6 7 8 7 ^ ^ ^ 深度遍歷： V1? V3 ? V7 ? V6 ? V2 ? V4 ? V8 ? V5 ?廣度優(yōu)先遍歷 (BFS) ?方法：從圖的某一頂點(diǎn) V0出發(fā)，訪問此頂點(diǎn)后，依次訪問 V0的各個未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止 V1 V2 V4 V5 V3 V7 V6 V8 例 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 V1 V2 V4 V5 V3 V7 V6 V8 例 例 V1 V2 V4 V5 V3 V7 V6 V8 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 V1 V2 V4 V5 V3 V7 V6 V8 例 廣度遍歷： V1? V2 ?V3 ? V4 ?V6 ?V7 ?V8 ?V5 （ V5逆向最后訪問） ?廣度優(yōu)先遍歷算法 開始 標(biāo)志數(shù)組初始化 Vi=1 Vi訪問過 BFS Vi=Vi+1 Vi==Vexnums 結(jié)束 N N Y Y 開始 訪問 V0,置 標(biāo)志 求 V鄰接點(diǎn) w w存在嗎 V下一鄰接點(diǎn) ?w w訪問過 結(jié)束 N Y N Y BFS 初始化隊(duì)列 V0入隊(duì) 隊(duì)列空嗎 隊(duì)頭 V出隊(duì) 訪問 w,置 標(biāo)志 w入隊(duì) N a a Y 例 1 4 2 3 5 1 2 3 4 1 3 4 2 vexdata firstarc 5 5 4 3 ^ ^ ^ adjvex next 5 5 1 ^ 5 1 1 4 3 ^ 2 2 0 1 2 3 4 5 1 f r 遍歷序列： 1 0 1 2 3 4 5 4 f r 遍歷序列： 1 4 0 1 2 3 4 5 4 3 f r 遍歷序列： 1 4 3 例 1 4 2 3 5 1 2 3 4 1 3 4 2 vexdata firstarc 5 5 4 3 ^ ^ ^ adjvex next 5 5 1 ^ 5 1 1 4 3 ^ 2 2 0 1 2 3 4 5 4 3 2 f r 遍歷序列： 1 4 3 2 0 1 2 3 4 5 3 2 f r 遍歷序列： 1 4 3 2 0 1 2 3 4 5 3 2 5 f r 遍歷序列： 1 4 3 2 5 鄰接表： 0 1 2 3 4 5 2 5 f r 遍歷序列： 1 4 3 2 5 0 1 2 3 4 5 5 f r 遍歷序列： 1 4 3 2 5 0 1 2 3 4 5 f r 遍歷序列： 1 4 3 2 5 例 1 4 2 3 5 1 2 3 4 1 3 4 2 vexdata firstarc 5 5 4 3 ^ ^ ^ adjvex next 5 5 1 ^ 5 1 1 4 3 ^ 2 2 167。 圖的連通性問題 ?生成樹 ?定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫 ~ ?深度優(yōu)先生成樹與廣度優(yōu)先生成樹 ?生成森林：非連通圖每個連通分量的生成樹組成的非連通圖的 ~ ?說明 ?一個圖可以有許多棵不同的生成樹 ?所有生成樹具有以下共同特點(diǎn)： ?生成樹的頂點(diǎn)個數(shù)與圖的頂點(diǎn)個數(shù)相同 ?生成樹是圖的極小連通子圖 ?一個有 n個頂點(diǎn)的連通圖的生成樹有 n1條邊 ?生成樹中任意兩個頂點(diǎn)間的路徑是唯一的 ?在生成樹中再加一條邊必然形成回路 ?含 n個頂點(diǎn) n1條邊的圖不一定是生成樹 ?無向圖的連通分量和生成樹 ?連通圖的生成樹 ?非連通圖的生成森林 V1 V2 V4 V5 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 V4 V5 V3 V7 V6 V8 V1 V2 V4 V5 V3 V7 V6 V8 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?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)絡(luò)網(wǎng)， 頂點(diǎn) —— 表示城市 權(quán) —— 城市間建立通信線路所需花費(fèi)代價 希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立 該通信網(wǎng)所需花費(fèi)的總代價）最小 ——— 最小代價生成樹 ?問題分析 1 6 5 4 3 2 7 13 17 9 18 12 7 5 24 10 n個城市間，最多可設(shè)置 n(n1)/2條線路 n個城市間建立通信網(wǎng)，只需 n1條線路 問題轉(zhuǎn)化為：如何在可能的線路中選擇 n1條，能把 所有城市（頂點(diǎn)）均連起來，且總耗費(fèi) （各邊權(quán)值之和）最小 ?構(gòu)造最小生成樹方法 ?方法一：普里姆 (Prim)算法 ?算法思想：設(shè) N=(V,{E})是連通網(wǎng)， TE是 N上最小生成樹中邊的集合 ?初始令 U={u0},(u0?V), TE=? ?在所有 u?U,v?VU的邊 (u,v)?E中，找一條代價最小的邊 (u0,v0) ?將 (u0,v0)并入集合 TE， 同時 v0并入 U ?重復(fù)上述操作直至 U=V為止，則 T=(V,{TE})為 N的最小生成樹 ?算法實(shí)現(xiàn)：圖用鄰接矩陣表示 ?算法描述 ?算法評價： T(n)=O(n178。) 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1