【文章內(nèi)容簡介】 ?起始頂點(diǎn) V1 V1 ?訪問 V1的未被訪問過的 所有鄰接點(diǎn) V3,V2,V4 （ V1,V3） (V1,V2) (V1,V4) ?訪問 V3的未被訪問過 的所有的鄰接點(diǎn) V5 （ V3,V5） ?訪問 V2的未被訪問過 的所有的鄰接點(diǎn) 無 ?訪問 V4的未被訪問過 的所有的鄰接點(diǎn) V6 (V4,V6) ?所有頂點(diǎn)已被訪問 ,結(jié)束。 V1 V3 V5 V4 V6 G6 V2 示例 下一頁 上一頁 停止放映 第 37 頁 遍歷產(chǎn)生的結(jié)果 廣度優(yōu)先遍歷 G6所走過的序列： V1? V3 ? V2 ? V4 ? V5 ? V6 所走過的邊： （ V1， V3） ， （ V1， V2） ， （ V1， V4） ， （ V3，V5） ， （ V4， V6） 遍歷生成樹 V1 V3 V5 V2 V4 V6 下一頁 上一頁 停止放映 第 38 頁 程序舉例 圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。 V1 V3 V5 V4 V6 G6 V2 深度優(yōu)先遍歷序列： V1 V3 V5 V2 V4 V6 廣度優(yōu)先遍歷序列： V1 V3 V2 V4 V5 V6 1 3 2 4 G2 深度優(yōu)先遍歷序列： 1 3 4 2 廣度優(yōu)先遍歷序列： 1 3 2 4 示例 下一頁 上一頁 停止放映 第 39 頁 四、圖的操作 圖中頂點(diǎn)無序可言 任一頂點(diǎn)都可以看作第一個(gè)頂點(diǎn)； 任一頂點(diǎn)的鄰接點(diǎn)間也無序可言； 為操作方便 ， 對(duì)圖中頂點(diǎn)按人為意志給其排序；同樣 ， 也可以對(duì)某個(gè)頂點(diǎn)的所有鄰接點(diǎn)進(jìn)行排隊(duì) ， 在這個(gè)隊(duì)列中自然形成第一個(gè)或第 K個(gè)鄰接點(diǎn) 。 若某個(gè)頂點(diǎn)的鄰接點(diǎn)個(gè)數(shù)大于 K， 則稱第 K+1個(gè)鄰接點(diǎn)為第 K個(gè)鄰接點(diǎn)的下一個(gè)鄰接點(diǎn) ， 而最后一個(gè)鄰接點(diǎn)的下一個(gè)鄰接點(diǎn)為 ? 空 ? 。 下一頁 上一頁 停止放映 第 40 頁 圖的常用基本操作 LOC_VERTEX（ G， Vi） 確定頂點(diǎn) Vi在 G中的位置 。 GET_VERTEX（ G， i） 求圖 G中第 i個(gè)頂點(diǎn) 。 FIRST_VERTEX（ G， i） 求圖 G中 Vi的第 1個(gè)鄰接點(diǎn) 。 NEXT_ADJ(G,v,w) 已知 w為 G中頂點(diǎn) v的第 1個(gè)鄰接點(diǎn) ,求頂點(diǎn) w的下一個(gè)鄰接點(diǎn) 。 INS_VERTEX(G,u) 在圖 G中插入一個(gè)頂點(diǎn) u,為圖 G的第 n+1個(gè)頂點(diǎn) 。 INS_ARC(G,v,w) 在圖 G中插入一條從頂點(diǎn) v到頂點(diǎn) w的弧 。 DEL_VERTEX(G,Vi) 刪除圖 G中頂點(diǎn) Vi,以及與 Vi相關(guān)聯(lián)的邊或弧 。 DEL_ARC(G,v,w) 刪除圖 G中從頂點(diǎn) v到頂點(diǎn) w的弧 。 下一頁 上一頁 停止放映 第 41 頁 五、圖的應(yīng)用 最小生成樹 拓?fù)渑判? 關(guān)鍵路徑 最短路徑 下一頁 上一頁 停止放映 第 42 頁 圖的應(yīng)用實(shí)例 ? [生成樹 ] 設(shè) G= (V,E)是一個(gè)無向圖，當(dāng)且僅當(dāng) G中每一對(duì)頂點(diǎn)之間有一條路徑時(shí)，可認(rèn)為 G是連通的（ connected）。 ? 一個(gè) n節(jié)點(diǎn)的連通圖必須至少有 n 1條邊。因此當(dāng)通信網(wǎng)絡(luò)的每條鏈路具有相同的建造費(fèi)用時(shí)，在任意一棵生成樹上建設(shè)所有的鏈路可以將網(wǎng)絡(luò)建設(shè)費(fèi)用減至最小，并且能保證每兩個(gè)城市之間存在一條通信路徑。如果鏈路具有不同的耗費(fèi)，那么需要在一棵最小耗費(fèi)生成樹上建立鏈路。 下一頁 上一頁 停止放映 第 43 頁 圖的應(yīng)用實(shí)例 下一頁 上一頁 停止放映 第 44 頁 最小生成樹 該問題是構(gòu)造連通圖的最小代價(jià)生成樹問題 。 一棵生成樹的代價(jià)就是樹上各邊 （ 弧 ）的代價(jià)之和 。 例如 ， 若要在 n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng) ，則只需 n1條線路 。 但在 n個(gè)城市間 ， 最多可能架設(shè) n（ n1） /2條線路 ， 選擇哪 n1條線路 ， 使費(fèi)用最少 。 普里姆 （ Prim） 算法 克魯斯卡爾 （ Kruskal） 算法 下一頁 上一頁 停止放映 第 45 頁 普里姆（ Prim）算法 假設(shè) N=（ V， E） 是連通圖 ， TE是 N上最小生成樹中邊的集合 。 從 U={u0} （ u0 ? V） ， TE= 空開始； 重復(fù)執(zhí)行： 在所有 u?U， v ?VU的邊 （ u， v）?E中找一條代價(jià)最小的邊 （ u0， v0） 并入TE， 同時(shí) u0并入 U， 直到 U=V為止； 此時(shí) TE中必有 n1條邊 ， 則 T=（ V， TE） 為 N的最小生成樹 。 下一頁 上一頁 停止放映 第 46 頁 普里姆（ Prim）算法舉例 1 2 3 4 5 6 8 7 2 1 4 3 5 7 6 8 11 10 9 12 U={1}， VU={2， 3， 4， 5， 6， 7， 8} 1 2 2 1 2 4 2 1 4 7 3 （ 1） （ 2） （ 3） (1) U={1,2},VU={3,4,5,6,7,8} (2) U={1,2,4},VU={3,5,6,7,8} (3) U={1,2,4,7},VU={3,5,6,8} 例子 下一頁 上一頁 停止放映 第 47 頁 普里姆（ Prim）算法舉例 (續(xù) ) 4 7 5 3 5 （ 4） 7 6 （ 5） 6 (4) U={1,2,4,7,5} , VU={3,6,8} (5) U={1,2,4,7,5,6}, VU={3,8} (6) U={1,2,4,7,5,6,3}, VU={8} (7) U={1,2,4,7,5,6,3,8), VU={ } 4 3 （ 7） 8 3 6 5 4 7 2 2 1 3 6 5 8 9 1 5 5 （ 6） 4 7 6 3 6 3 5 5 8 下一頁 上一頁 停止放映 第 48 頁 克魯斯卡爾（ Kruskal）算法 操作步驟 : – 假設(shè) N=（ V， E） 是連通圖 – 取圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量 – 在 { E }中選擇代價(jià)最小的邊 ， 若該邊所依附的頂點(diǎn)落在 T中不同的連通分量上 ， 則將此邊加入生成樹 T中；否則 ， 舍去此邊 ， 再選擇下一條代價(jià)最小的邊 。 – 重復(fù)上述步 ， 直到 T中所有頂點(diǎn)都在同一連通分量上為止 。 下一頁 上一頁 停止放映 第 49 頁 克魯斯卡爾（ Kruskal）算法舉例 1 2 3 4 5 6 1 5 2 4 6 6 3 5 5 6 2 5 1 3 4 6 1 2 3 (4) 1 3 1 4 6 2 (3) 1 2 3 4 5 6 (1) 1 3 (2) 1 下一頁 上一頁 停止放映 第 50 頁 克魯斯卡爾（ Kruskal）算法舉例 (續(xù)） 1 2 3 4 5 6 (5) 1 2 3 4 1 2 3 4 5 6 1 5 2 4 6 6 3 5 5 6 1 3 2 5 6 4 1 2 4 3 5 （ 6） 下一頁 上一頁 停止放映 第 51 頁 拓?fù)渑判? 研究一個(gè)有機(jī)整體中不同個(gè)體間的次序問題 。例如課程間優(yōu)先關(guān)系有向圖問題 。 軟件專業(yè)的課程優(yōu)先關(guān)系： 課程編號(hào) 課程名稱 先決條件 C1 程序設(shè)計(jì)基礎(chǔ) 無 C2 離散數(shù)學(xué) C1 C3 匯編語言 C1， C2 …… C9 高等數(shù)學(xué) 無 下一頁 上一頁 停止放映 第 52 頁 拓?fù)渑判蚺e例 方法步驟 ?在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)并輸出 。 ?從圖中刪除該頂點(diǎn)和所有以它為尾的弧 。 ?重復(fù)前 2步 ,直到全部頂點(diǎn)均輸出為止 。 ?輸出序列即為拓?fù)渑判蛐蛄?。 拓?fù)渑判蛐蛄胁晃ㄒ?。 下一頁 上一頁 停止放映 第 53 頁 拓?fù)渑判蚺e例 C1 C9 C4 C2 C3 C5 C7 C12 C10 C11 C6 C8 ?C1 C2 C3 C4 C5 C7 C9 C10 C11 C6 C12 C8 ?C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C8 例子 1 2 3 4 5 6 下一頁 上一頁 停止放映 第 54 頁 關(guān)鍵路徑 研究的是在一個(gè)有機(jī)整體中不同個(gè)體間的次序問題 ， 即研究的是工程進(jìn)度及影響進(jìn)度的關(guān)鍵因素問題 。 下一頁 上一頁 停止放映 第 55 頁 圖的應(yīng)用實(shí)例 ? [路徑問題 ] 城市中有許多街道，每一個(gè)十字路口都可以看作圖中一個(gè)頂點(diǎn)，鄰接兩個(gè)十字路口之間的每一段街道既可以看作一條，也可以看作兩條有向邊。如果街道是雙向的，就用兩條有向邊。如果街道是單向的，就用一條有向邊。 (路線咨詢 ) 下一頁 上一頁 停止放映 第 56 頁 最短路徑 研究的是類似于交通調(diào)度一類的帶權(quán)有向圖問題 。 求路徑最短或費(fèi)用最省 。 從源到其余各頂點(diǎn)的最短路徑 圖中 7個(gè)頂點(diǎn) 、 13條弧 。 Floyd算法 。 例子 1 2 3 4 5 6 7 2 4 1 3 2 3 4 7 6 9 8 5 9 下一頁 上一頁 停止放映 第 57 頁 最短路徑問題描述 ? 設(shè)下一條最短路的終點(diǎn)為 vk，則這條路徑或者是 (v,vk) 或者是 （ v,vj,vk） 它的長度或者是從 v到 vk的弧的權(quán)值，或者是 disk[j]和從 vj到 vk的弧上的權(quán)值之和。 下一頁 上一頁 停止放映 第 58 頁 最短路徑算法描述 （ 1）假設(shè)用帶權(quán)的鄰接矩陣 cost來表示帶權(quán)有向圖，cost[i,j]表示弧