【正文】 熟練掌握拓?fù)渑判蚍椒? 4. 理解求解關(guān)鍵路徑和兩頂點(diǎn)間最短路徑問題。 2. 熟練掌握?qǐng)D的兩種搜索路徑的遍歷：遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。 假設(shè)求得最短路徑的頂點(diǎn)為 u， 若 Dist[u]+[u][k]Dist[k] 則將 Dist[k] 改為 Dist[u]+[u][k] ????INF INIT Ykvar c sGkD i s t]][0[.][V0和 k之間存在弧 V0和 k之間不存在弧 其中的最小值即為最短路徑的長(zhǎng)度 。 它或者是 直接從源點(diǎn)到該點(diǎn) (只含一條弧 )； 或者是， 從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn) 。 第七章 圖 拓?fù)渑判? 算法描述 輸入頂點(diǎn)和弧信息，建立其鄰接表 計(jì)算每個(gè)頂點(diǎn)的入度 對(duì)其進(jìn)行拓?fù)渑判? ?排序過程中求頂點(diǎn)的 Ve[i] ?將得到的拓?fù)湫蛄羞M(jìn)棧 按逆拓?fù)湫蛄星箜旤c(diǎn)的 Vl[i] 計(jì)算每條弧的 e[i]和 l[i],找出 e[i]=l[i]的關(guān)鍵活動(dòng) 改寫算法 第七章 圖 最短路徑 每一對(duì)頂點(diǎn) 之間的最短路徑 從某個(gè)源點(diǎn)到 其余各點(diǎn)的最短路徑 第七章 圖 最短路徑 ? 問題提出 用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng) 圖中： 頂點(diǎn) ——表示城市 邊 ——表示城市間的交通聯(lián)系 權(quán) ——表示此線路的長(zhǎng)度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等 問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑 ——最短路徑 第七章 圖 最短路徑 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑 24 15 8 6 3 9 7 3 5 10 4 a f e d b c g 2 最短路徑 長(zhǎng)度 a,d,g,b 22 a,c 8 a,d 15 a,c,f,e 13 a,c,f 11 a,g 19 第七章 圖 最短路徑 求 從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想 : 依 最短路徑的長(zhǎng)度 遞增的次序求得各條路徑 源點(diǎn) v1 … 其中， 從源點(diǎn)到頂點(diǎn) v1的最短路徑 是所有最短路徑中長(zhǎng)度最短者。 ve(k) = Max{ve(j) + dut(j, k)} vl(匯點(diǎn) ) = ve(匯點(diǎn) )。 ―事件 (頂點(diǎn) )‖ 的 最遲發(fā)生時(shí)間 vl(k) vl(k) = 從頂點(diǎn) k到匯點(diǎn)的最短路徑長(zhǎng)度 。 例如：有 一個(gè)工程有 11項(xiàng)活動(dòng)，9個(gè)事件 (v1v9) v1表示整個(gè)工程開始 v9表示整個(gè)工程結(jié)束 v9 v8 v7 v6 v4 v5 v3 v2 v1 a6=2 第七章 圖 拓?fù)渑判? 定義 AOE網(wǎng) (Activity On Edge)——即 邊 表示活動(dòng) 的網(wǎng)。 第七章 圖 拓?fù)渑判? 問題提出：學(xué)生選修課程問題 頂點(diǎn) ——表示課程 有向弧 ——表示先決條件，若課程 i是課程 j的先決條件，則圖中有弧 i,j 學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè) ——拓?fù)渑判? 定義 AOV網(wǎng) ——用 頂點(diǎn) 表示 活動(dòng) ，用 弧 表示 活動(dòng)間優(yōu)先關(guān)系 的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng) (Activity On Vertex work)， 簡(jiǎn)稱 AOV網(wǎng) ? 若 vi,vj是圖中有向邊，則 vi是 vj的直接前驅(qū)； vj是 vi的直接后繼 ? AOV網(wǎng)中 不允許有回路 ，這意味著某項(xiàng)活動(dòng)以自己為先決條件 第七章 圖 拓?fù)渑判? 拓?fù)渑判?——把 AOV網(wǎng)絡(luò)中各頂點(diǎn) 按照 它們 相互之間的優(yōu)先關(guān)系 排列成一個(gè)線性序列的過程 ? 檢測(cè) AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(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) 匯編語(yǔ)言 語(yǔ)言的設(shè)計(jì)和分析 計(jì)算機(jī)原理 編譯原理 操作系統(tǒng) 高等數(shù)學(xué) 線性代數(shù) 普通物理 數(shù)值分析 課程代號(hào) 課程名稱 先修課 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) 以鄰接表作存儲(chǔ)結(jié)構(gòu) 把鄰接表中所有入度為 0的頂點(diǎn)進(jìn)棧 棧非空時(shí)，輸出棧頂元素 Vj并退棧；在鄰接表中查找 Vj的直接后繼 Vk， 把 Vk的入度減 1；若 Vk的 入度為 0則進(jìn)棧 重復(fù)上述操作直至?？諡橹?。 檢查邊集 E 中第 i 條權(quán)值最小的邊 (u,v)。 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的最小生成樹 樹存儲(chǔ)結(jié)構(gòu)： 鄰接矩陣表示 算法實(shí)現(xiàn) 算法評(píng)價(jià)： O(n178。 第七章 圖 圖的遍歷 從圖的某頂點(diǎn)出發(fā)，對(duì)圖中的每個(gè)頂點(diǎn)進(jìn)行一次訪問且使每個(gè)頂點(diǎn)僅被訪問一次的過程。 //指向第 1條依附該頂點(diǎn)的邊 }VexBox。 infoType *info。 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 無向圖的鄰接多重表存儲(chǔ)表示 鄰接多重表結(jié)點(diǎn)結(jié)構(gòu) mark ivex ilink jvex info 邊結(jié)點(diǎn) jlink data firstedge 頂點(diǎn)結(jié)點(diǎn) i頂點(diǎn) 下一個(gè)依附于 i頂點(diǎn)的邊 j頂點(diǎn) 下一個(gè)依附于 j頂點(diǎn)的邊 第 1個(gè)依附于該頂點(diǎn)的邊 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 例 v1 v2 v4 v5 v3 0 1 2 3 v1 v3 v4 v2 4 v5 0 1 0 3 2 3 2 1 2 4 4 1 ^ ^ ^ ^ ^ 指向下一個(gè)依附于v1的邊 指向下一個(gè)依附于v2的邊 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 無向圖鄰接多重表存儲(chǔ)表示 define MAX_VERTEX_NUM 20 Typedef emnu {unvisited, visited} VisitIf。 Typedef struct { //頂點(diǎn)表 VexNode xlist[MAX_VERTEX_NUM]。 }ArcBox。為了求頂點(diǎn)的入度，有時(shí)可設(shè) 逆鄰接表 （指向某頂點(diǎn)的鄰接點(diǎn)鏈接成單鏈表） 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 建立鄰接表的算法 有向圖 G1 2 4 1 3 V1 V2 V3 V4 3 ? 0 ? 0 ? 2 ? 逆鄰接表 第 i(下標(biāo) i1)鏈表的結(jié)點(diǎn)個(gè)數(shù)即為 Vi頂點(diǎn)的入度。 int vexnum, arum, kind。 Typedef struct Vnode //頭結(jié)點(diǎn) { VertexType data。 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 建立無向圖鄰接矩陣的算法 算法中： [ ]， 一維 ， 頂點(diǎn)向量 .arcs[ ][ ]， 二維 ， 鄰接矩陣 .vexnum， 頂點(diǎn)數(shù) .arum， 邊數(shù) 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 圖的鄰接表存儲(chǔ)表示 鄰接表 是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，為依附每個(gè)頂點(diǎn)的邊（或?。┙⒁粋€(gè)單鏈表 頂點(diǎn)結(jié)構(gòu) adjvex nextarc info 表結(jié)點(diǎn) data firstarc 頭結(jié)點(diǎn) 頂點(diǎn)位置 下一條弧 相關(guān)信息 頂點(diǎn)數(shù)據(jù) 第一條弧 第七章 圖 V1 V2 ? V3 V4 0 1 2 3 V1 V2 V3 V4 V5 0 1 2 3 4 圖的存儲(chǔ)結(jié)構(gòu) 有向圖 G1 2 4 1 3 無向圖 G2 2 5 1 4 3 1 2 ? 3 ? 0 ? 3 1 ? 4 2 0 ? 4 3 1 ? 2 0 ? 2 1 ? 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 圖的 鄰接表 存儲(chǔ)表示 define MAX_VERTEX_NUM 20 Typedef struct ArcNode //表結(jié)點(diǎn) { int Adjvex。 //頂點(diǎn)向量 AdjMatrix arcs。