【正文】 下一條次短的路徑可通過下面的算法求得： 設(shè)次短路徑的終點(diǎn)是 Vk ， 則這條路徑或者是 (V, Vk ) ,或者是 (V, Vj, Vk ) 。 第 7章 圖 圖的定義和術(shù)語 圖的存儲結(jié)構(gòu) 圖的遍歷操作 圖的連通性問題 有向無環(huán)圖及其應(yīng)用 最短路徑 有向無環(huán)圖及其應(yīng)用 一個無環(huán)的有向圖稱做有向無環(huán)圖 (DAG）。m2=E[j].v。 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 3 1 1 6 3 1 4 1 6 4 3 1 4 2 1 1 6 4 3 2 1 4 2 5 1 6 5 4 3 2 1 4 2 5 3 Prim算法構(gòu)造最小生成樹過程 a b c d e g f 例如 :利用 普里姆 算法構(gòu)造最小生成樹 19 5 14 18 27 16 8 21 3 12 7 所得生成樹權(quán)值和 = 14+8+3+5+16+21 = 67 假設(shè)開始頂點(diǎn)就選為頂點(diǎn) 1， 故首先有 U={1}， W={2，3， 4， 5， 6} (a ) 無向網(wǎng) ( b ) u = { 1 } w = { 2 , 3 , 4 , 5 , 6 } 6 4 1 2 4 6 3 6 2 1 3 5 7 6 5 5 5 1 2 3 4 5 6 6 ? 5 1 ? i 1 2 3 4 5 6 closest[i] 1 1 1 1 1 1 lowcost[i] 0 6 1 5 ∞ ∞ ??????????????????????????????06246053207545705135065160closest用于存放頂點(diǎn)序號 lowest存放權(quán)值 3 1 2 4 6 5 6 1 4 5 5 5 3 1 2 4 6 5 6 4 2 1 5 5 (c ) u ={1 ,3} w ={2 ,4,5,6 } (d ) u={ 1,3 ,6} w ={2 ,4,5} i 1 2 3 4 5 6 closest[i] 1 3 1 1 3 3 lowcost[i] 0 5 0 5 5 4 i 1 2 3 4 5 6 closest[i] 1 3 1 6 3 3 lowcost[i] 0 5 0 2 5 0 3 1 2 4 6 5 6 4 2 1 5 5 (e) u= {1, 3,6, 4} w={2, 5} (f) u= {1, 3,6, 4,2} w={5} 1 2 4 6 3 5 6 4 2 1 5 3 (g ) u= { 1,3,6,4,2,5} w = { } 5 4 2 1 3 1 2 4 6 3 5 6 圖 8 20 pr i m 方法構(gòu)造最小生成樹的過程 i 1 2 3 4 5 6 closest[i] 1 3 1 6 3 3 lowcost[i] 0 5 0 0 5 0 i 1 2 3 4 5 6 closest[i] 1 3 1 6 2 3 lowcost[i] 0 0 0 0 3 0 i 1 2 3 4 5 6 closest[i] 1 3 1 6 2 3 lowcost[i] 0 0 0 0 0 0 求最小生成樹的兩種方法 克魯斯卡爾（ kruskal）算法 考慮問題的出發(fā)點(diǎn) : 為使生成樹上 邊的權(quán)值之和達(dá)到最小 ，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。 /*p指向 u的第一條弧的弧頭結(jié)點(diǎn) */ while (p!=NULL) { m=padjvex。 從頂點(diǎn) u開始，進(jìn)行深度優(yōu)先搜索，在搜索過程中，需要把當(dāng)前的搜索線路記錄下來。遍歷圖的過程實(shí)質(zhì)上是通過邊或弧找鄰接 點(diǎn)的過程、因此廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之 處僅僅在于對頂點(diǎn)訪問的順序不同。 // 置空的輔助隊(duì)列 Q for ( v=0。amp。 深度優(yōu)先搜索算法分析 深度優(yōu)先搜索算法分析 0111100010000100100001001000001010000010011000010001100100000110 圖 8 14 無向圖 G 7 的鄰接矩陣 (1) 用鄰接矩陣實(shí)現(xiàn)圖的深度優(yōu)先搜索 深度優(yōu)先搜索算法分析 D F S ( 1) D F S ( 2) D F S ( 4) D F S ( 8) D F S ( 5) D F S ( 6) D F S ( 3) D F S ( 7) 圖 8 15 鄰接矩陣深度優(yōu)先搜索示意圖 當(dāng)用二維數(shù)組表示鄰接矩陣作圖的存儲結(jié)構(gòu)時，查找每個頂點(diǎn)的鄰接點(diǎn)所需時間為 O（ n2），其中 n為圖中頂點(diǎn)數(shù)。// visitfunc為指向函數(shù)的指針變量 void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 對圖 G 作深度優(yōu)先遍歷。 } VexNode。 //該弧所指向的頂點(diǎn)的位置 struct arode *nextarc 。 （ 3） 第 i列中 1的個數(shù)為頂點(diǎn) i的入度 。 2：對任意一個城市，輸出都能夠直接通達(dá)哪些城市，距離多少？ 5 1 3 2 4 平頂山 鄭州 洛陽 許昌 漯河 100 150 120 150 200 180 第 7章 圖 圖的定義和術(shù)語 圖的存儲結(jié)構(gòu) 圖的遍歷操作 圖的連通性問題 有向無環(huán)圖及其應(yīng)用 最短路徑 圖的定義和術(shù)語 圖的結(jié)構(gòu)定義、圖形結(jié)構(gòu)特點(diǎn) 頂點(diǎn)、弧、邊、弧頭、弧尾 無向圖和有向圖 完全圖和有向完全圖 網(wǎng)、子圖 頂點(diǎn)的度、入度和出度、 邊、弧與各頂點(diǎn)度的關(guān)系 圖的定義和術(shù)語 路徑、路徑長度、回路（環(huán)）、簡單路徑 連通、連通圖、連通分量 強(qiáng)連通圖、強(qiáng)連通分量 生成樹、有向樹、生成森林 圖的存儲表示 ? 圖的數(shù)組 (鄰接矩陣 )存儲表示 （重點(diǎn)） ? 圖的 鄰接表 存儲表示 （重點(diǎn)） ? 有向圖的 十字鏈表 存儲表示 ? 無向圖的 鄰接多重表 存儲表示 回答問題 什么是圖形結(jié)構(gòu)？它和線性結(jié)構(gòu)、樹形結(jié)構(gòu)有何區(qū)別？ 以下圖為例，理解圖的相關(guān)術(shù)語，并回答有關(guān)問題。 圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間 的 關(guān)系 可以是 任意 的，任意兩個數(shù)據(jù)元素 之間都可能 相關(guān) 。 // 圖的種類標(biāo)志 } MGraph。 從有向圖的鄰接表可以得到如下結(jié)論： （ 1） 第 i 個鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn) i的出度； （ 2） 所有鏈表中結(jié)點(diǎn)數(shù)目為圖中弧數(shù)； （ 3） 占用的存儲單元數(shù)目為 n+e 。 } VexNode。但是 ,若我們給定圖的存貯結(jié)構(gòu) ,則從某一頂點(diǎn)出發(fā)的遍歷結(jié)果應(yīng)是唯一的。 // 對 v的尚未訪問的鄰接頂點(diǎn) w // 遞歸調(diào)用 DFS } // DFS 分析上述過程，在遍歷圖時，對圖中每個頂點(diǎn)至多調(diào)用一次 dfs過程，因?yàn)橐坏┠硞€ 頂點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行搜索。 else return 1。 v。 若從頂點(diǎn) 3出發(fā) ， 廣度優(yōu)先搜索序列為：3， 1， 6， 7， 2， 8， 4， 5,從其它點(diǎn)出發(fā)的廣度優(yōu)先搜索序列可根據(jù)同樣類似方法分析 。 } 假設(shè)圖 G采用鄰接表存儲，設(shè)計(jì)一個算法，輸出圖 G中從頂點(diǎn) u到 v的長度為 l的所有簡單路徑。i++) printf(%d ,path[i])。 欲在 n個城市間建立通信網(wǎng)，則 n個城市應(yīng)鋪 n1條線路；但因?yàn)槊織l線路都會有對應(yīng)的經(jīng)