圖論模型基礎知識

1、下下回回停停 1. 圖論的基本概念圖論的基本概念2. 最短路問題及算法最短路問題及算法 圖論模型基礎知識圖論模型基礎知識 3. 最小生成樹及算法最小生成樹及算法 4. 旅行售貨員問題旅行售貨員問題1.圖論的基本概念圖論的基本概念1) 圖的概念圖的概念2) 賦權圖與子圖賦權圖與子圖3) 圖的矩陣表示圖的矩陣表示4) 圖的頂點度圖的頂點度5) 路和連通路和連通1) 圖的概念圖的概念 定義定義 一個一個圖圖G是指一個二元組是指一個二元組(V(G),E(G)，其中，其中: 其中元素稱為圖其中元素稱為圖G的的頂點頂點.組成的集合，即稱為組成的集合，即稱為邊集邊集,其中元素稱為其中元素稱為邊邊.),(ji

2、vv 定義定義 圖圖G的的階階是指圖的頂點數(shù)是指圖的頂點數(shù)|V(G)|, 用用來表示；來表示；v圖的邊的數(shù)目圖的邊的數(shù)目|E(G)|用用 來表示來表示. 也用也用來表示邊來表示邊jivv).,(jivv,)(21vvvGV是非空有限集，稱為是非空有限集，稱為頂頂點集點集，1)2) E(G)是頂點集是頂點集V(G)中的無序或有序的元素偶對中的無序或有序的元素偶對).,(EVG )(),(GEGVG 表示圖，表示圖，簡記簡記 用用 定義 若一個圖的頂點集和邊集都是有限集，則稱若一個圖的頂點集和邊集都是有限集，則稱 其為其為有限圖有限圖. 只有一個頂點的圖稱為只有一個頂點的圖稱為平凡圖平凡圖，其他的

3、，其他的 所有圖都稱為所有圖都稱為非平凡圖非平凡圖. 定義若若圖圖G中的邊均為中的邊均為有序有序偶對偶對,稱稱G為為有向有向),(jivv邊邊 為為無向邊無向邊，稱，稱e連接連接 和和 ，頂點，頂點 和和 稱稱圖圖. 稱邊稱邊為為有向邊有向邊或或弧弧,稱稱),(jivve 是從是從),(jivve iv連接連接jv，稱，稱 為為e的的尾尾，稱，稱 為為e的的頭頭. ivjv 若圖若圖G中的邊均為中的邊均為無序無序偶對偶對 ，稱，稱G為為無向圖無向圖.稱稱jivv為為e的的端點端點. jivve ivjvivjv 既有無向邊又有有向邊的圖稱為既有無向邊又有有向邊的圖稱為混合圖混合圖. 常用術語常

4、用術語1) 邊和它的兩端點稱為互相邊和它的兩端點稱為互相關聯(lián)關聯(lián).2)與同一條邊關聯(lián)的兩個端點稱與同一條邊關聯(lián)的兩個端點稱為為相鄰相鄰的頂點，與同一個頂點的頂點，與同一個頂點 點關聯(lián)的兩條邊稱為點關聯(lián)的兩條邊稱為相鄰相鄰的邊的邊. 3) 端點重合為一點的邊稱為端點重合為一點的邊稱為環(huán)環(huán)， 端點不相同的邊稱為端點不相同的邊稱為連桿連桿.4) 若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊 稱為稱為重邊重邊5) 既沒有既沒有環(huán)也沒有重邊環(huán)也沒有重邊的圖，稱為的圖，稱為簡單圖簡單圖 常用術語常用術語6) 任意兩頂點都相鄰的簡單圖任意兩頂點都相鄰的簡單圖,稱為稱為

5、完全圖完全圖. 記為記為Kv. 7) 若若 ， ，且且X 中任意兩頂點不中任意兩頂點不YXGV)(YX ， 相鄰，相鄰，Y 中任意兩頂點不相鄰，則稱為中任意兩頂點不相鄰，則稱為二部圖二部圖或或 偶圖偶圖；若；若X中每一頂點皆與中每一頂點皆與Y 中一切頂點相鄰中一切頂點相鄰,稱為稱為完全二部圖完全二部圖或或完全偶圖完全偶圖,記為記為 (m=|X|,n=|Y|)nmK,8) 圖圖 叫做叫做星星.nK, 1:X1x2x3x:Y1y2y3y4y二部圖二部圖6K:X1x2x3x:Y1y2y3y4y4 , 1K4 , 3K2) 2) 賦權圖與子圖賦權圖與子圖 定義定義 若圖若圖 的每一條邊的每一條邊e 都

6、賦以都賦以)(),(GEGVG 一個實數(shù)一個實數(shù)w(e)，稱，稱w(e)為邊為邊e的的權權，G 連同邊上的權連同邊上的權稱為稱為賦權圖賦權圖. 定義定義 設設 和和 是兩個圖是兩個圖.),(EVG ),(EVG 1) 若若 ,稱稱 是是 的一個的一個子圖子圖,記記 EEVV,GG.GG 2) 若若 ， ，則稱，則稱 是是 的的生成子圖生成子圖.VV EE GG 3) 若若 ，且，且 ，以，以 為頂點集，以兩端點為頂點集，以兩端點 VV VV 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱的子圖，稱 VG 為為 的的由由 導出的子圖導出的子圖，記為，記為 .GVVG4) 若若

7、 ，且，且 ，以，以 為邊集，以為邊集，以 的端點的端點EE EEE 集為頂點集的圖集為頂點集的圖 的子圖，稱為的子圖，稱為 的的由由 導出的導出的GGE 邊導出的子圖邊導出的子圖，記為，記為 . EG,321vvvG,6543eeeeG 3) 若若 ，且，且 ，以，以 為頂點集，以兩端點為頂點集，以兩端點 VV VV 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱的子圖，稱 VG4) 若若 ，且，且 ，以，以 為邊集，以為邊集，以 的端點的端點EE EEE 集為頂點集的圖集為頂點集的圖 的子圖，稱為的子圖，稱為 的的由由 導出的導出的GGE 邊導出的子圖邊導出的子圖，記為

8、，記為 . EGGVVG 為為 的的由由 導出的子圖導出的子圖，記為，記為 .3) 3) 圖的矩陣表示圖的矩陣表示 鄰接矩陣鄰接矩陣:1) 對無向圖對無向圖 ，其鄰接矩陣，其鄰接矩陣 ，其中：，其中： G)(ijaA., 0, 1不相鄰與若相鄰與若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv(以下均假設圖為簡單圖以下均假設圖為簡單圖).2) 對有向圖對有向圖 ,其鄰接矩陣其鄰接矩陣 ,其中：其中： )(ijaA),(EVG .),(, 0,),(, 1EvvEvvajijiij若若4321432101000010000011

9、10uuuuAuuuu其中：其中：3) 對有向賦權圖對有向賦權圖 , 其鄰接矩陣其鄰接矩陣 ,)(ijaA),(EVG .),(,0,),(,EvvjiwEvvwajiijjiijij若，為其權，且若43214321040608730uuuuAuuuu對于無向賦權圖的鄰接矩陣可類似定義對于無向賦權圖的鄰接矩陣可類似定義. 關聯(lián)矩陣關聯(lián)矩陣 1) 對無向圖對無向圖 ，其關聯(lián)矩陣，其關聯(lián)矩陣 ,),(EVG )(ijmM其中：其中：., 0, 1不關聯(lián)與若相關聯(lián)與若jijiijevevm54321543211000001000111100010100011vvvvvMeeeee2) 對有向圖對有向

10、圖 ，其關聯(lián)矩陣，其關聯(lián)矩陣 ,),(EVG )(ijmM., 0, 1, 1的頭與尾不是若的頭是若的尾是若jijijiijevevevm其中：其中：43215432111000101100001101101uuuuMeeeee4) 圖的頂點度圖的頂點度定義定義 1) 在無向圖在無向圖G中，與頂點中，與頂點v關聯(lián)的邊的數(shù)目關聯(lián)的邊的數(shù)目(環(huán)環(huán)算兩次算兩次),稱為頂點稱為頂點v的的度度或或次數(shù)次數(shù)，記為，記為d(v)或或 dG(v).稱度為奇數(shù)的頂點為稱度為奇數(shù)的頂點為奇點奇點，度為偶數(shù)的頂點為，度為偶數(shù)的頂點為偶點偶點.2) 在有向圖中，從頂點在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點引出的邊

11、的數(shù)目稱為頂點 v的的出度出度，記為，記為d+(v)，從頂點，從頂點v引入的邊的數(shù)目稱為引入的邊的數(shù)目稱為 v的的入度入度，記為，記為d -(v). 稱稱d(v)= d+(v)+d -(v)為頂點為頂點v的的 度度或或次數(shù)次數(shù)定理定理.2)(Vvvd的個數(shù)為偶數(shù)的個數(shù)為偶數(shù)推論推論 任何圖中奇點任何圖中奇點4)(1vd1)(3ud2)(3ud3)(3ud5) 路和連通路和連通 定義定義1) 無向圖無向圖G的一條的一條途徑途徑（或（或通道通道或或鏈鏈）是指）是指一個有限非空序列一個有限非空序列 ，它的項交替，它的項交替kkveevevW2110 地為頂點和邊，使得對地為頂點和邊，使得對 ， 的端

12、點是的端點是 和和 ,ki 1ie1iviv稱稱W是從是從 到到 的一條的一條途徑途徑，或一條，或一條 途徑途徑. 整整0vkv),(0kvv數(shù)數(shù)k稱為稱為W的的長長. 頂點頂點 和和 分別稱為的分別稱為的起點起點和和終點終點 ,0vkv而而 稱為稱為W的的內(nèi)部頂點內(nèi)部頂點.121,kvvv 2) 若途徑若途徑W的的邊互不相同但頂點可重復邊互不相同但頂點可重復，則稱，則稱W為為跡跡或或簡單鏈簡單鏈. 3) 若途徑若途徑W的的頂點和邊均互不相同頂點和邊均互不相同，則稱，則稱W為為路路或或路徑路徑. 一條起點為一條起點為 ,終點為終點為 的路稱為的路稱為 路路0vkv),(0kvv記為記為).,(

13、0kvvP 定義定義 1) 途徑途徑 中由相繼項構成子序列中由相繼項構成子序列kkvevevW.110 稱為途徑稱為途徑W的的節(jié)節(jié).jjiiivevev.11 2) 起點與終點重合的途徑稱為起點與終點重合的途徑稱為閉途徑閉途徑. 3) 起點與終點重合的的路稱為起點與終點重合的的路稱為圈圈(或或回路回路)，長長為為k的圈稱為的圈稱為k階圈階圈，記為，記為Ck. 4) 若在圖若在圖G中存在中存在(u,v)路，則稱頂點路，則稱頂點u和和v在圖在圖G中中連通連通. 5) 若在圖若在圖G中頂點中頂點u和和v是連通的，則頂點是連通的，則頂點u和和v之之之間的之間的距離距離d(u,v)是指圖是指圖G中中最短

14、最短(u,v)路的長路的長；若沒；若沒沒有路連接沒有路連接u和和v，則定義為無窮大，則定義為無窮大. 6) 圖圖G中中任意兩點皆連通任意兩點皆連通的圖稱為的圖稱為連通圖連通圖 7) 對于有向圖對于有向圖G，若，若 ，且，且 有有kkveevevW2110ie 類似地，可定義類似地，可定義有向跡有向跡，有向路有向路和和有向圈有向圈.頭頭 和尾和尾 ，則稱，則稱W為為有向途徑有向途徑.iv1iv 例例 在右圖中：在右圖中： 途徑或鏈：途徑或鏈： 跡或簡單鏈：跡或簡單鏈： 路或路徑：路或路徑： 圈或回路：圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg2最短

15、路問題及算法最短路問題及算法 最短路問題是圖論應用的基本問題，很多實際最短路問題是圖論應用的基本問題，很多實際問題，如線路的布設、運輸安排、運輸網(wǎng)絡最小費問題，如線路的布設、運輸安排、運輸網(wǎng)絡最小費用流等問題用流等問題,都可通過建立最短路問題模型來求解都可通過建立最短路問題模型來求解.最短路的定義最短路的定義最短路問題的兩種方法：最短路問題的兩種方法：Dijkstra和和Floyd算法算法 .1) 求賦權圖中從給定點到其余頂點的最短求賦權圖中從給定點到其余頂點的最短路路. .2) 求賦權圖中任意兩點間的最短路求賦權圖中任意兩點間的最短路. 2) 在賦權圖在賦權圖G中，從頂點中，從頂點u到頂點到

16、頂點v的具有最小權的具有最小權定義定義 1) 若若H是賦權圖是賦權圖G的一個子圖，則稱的一個子圖，則稱H的各的各邊的權和邊的權和 為為H的的權權. 類似地，若類似地，若)()()(HEeewHw稱為路稱為路P的的權權若若P(u,v)是賦權圖是賦權圖G中從中從u到到v的路的路,稱稱)()()(PEeewPw 的路的路P*(u,v)，稱為，稱為u到到v的的最短路最短路 3) 把賦權圖把賦權圖G中一條路的權稱為它的中一條路的權稱為它的長長，把，把(u,v)路的最小權稱為路的最小權稱為u和和v之間的之間的距離距離，并記作，并記作 d(u,v). 1) 賦權圖中從給定點到其余頂點的最短路賦權圖中從給定點

17、到其余頂點的最短路 假設假設G為賦權有向圖或無向圖，為賦權有向圖或無向圖，G邊上的權均非邊上的權均非負負若若 ，則規(guī)定，則規(guī)定 )(),(GEvu.),(vuw最短路是一條路，且最短路的任一節(jié)也是最短路最短路是一條路，且最短路的任一節(jié)也是最短路求下面賦權圖中頂點求下面賦權圖中頂點u0到其余頂點的最短路到其余頂點的最短路Dijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把

18、達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj01Su 10 ,min)(1ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并

19、把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj01Su 1)(1ul02Su Dijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(

20、vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul03Su )(3ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(m

21、invliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul04Su )(3ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvli

22、Sv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul05Su )(3ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvl

23、iSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul06Su )(3ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)

24、(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul4)(6ul07Su Dijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小

25、值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個

26、最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul)()(min10ulvlSv8)(7ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(min

27、vuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 對

28、每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路. 1) 置置 ，對，對 ， ， 且且 .0)

29、(0ul0uv )(vl00uS 0i 2) 對每個對每個 ，用，用iSv),()(),(minvuwulvlii代替代替 ，計算，計算 ，并把達到這個最小值的，并把達到這個最小值的)(vl)(minvliSv一個頂點記為一個頂點記為 ，置，置1iu.11iiiuSS 3) 若若 ，則停止；若，則停止；若 ，則用，則用 i+1 代代1i1i替替i，并轉(zhuǎn)，并轉(zhuǎn)2).定義 根據(jù)頂點根據(jù)頂點v的標號的標號l(v)的取值途徑，使的取值途徑，使 到到v0u的最短路中與的最短路中與v相鄰的前一個頂點相鄰的前一個頂點w，稱為，稱為v的的先驅(qū)先驅(qū)點點，記為，記為z(v), 即即z(v)=w.先驅(qū)點可用于追蹤最

30、短路徑先驅(qū)點可用于追蹤最短路徑. 例例5的標號過程也的標號過程也可按如下方式進行：可按如下方式進行： 首先寫出左圖帶權鄰接矩陣首先寫出左圖帶權鄰接矩陣024782063446046340357630135102273201847210W因因G是無向圖，故是無向圖，故W是對稱陣是對稱陣1u0u6u7u2u4u3u5uDijkstra算法：算法：求求G中從頂點中從頂點u0到其余頂點的最短路到其余頂點的最短路設設G為賦權有向圖或無向圖，為賦權有向圖或無向圖，G邊上的權均均非負邊上的權均均非負. 對每個頂點，定義兩個標記（對每個頂點，定義兩個標記（l(v)，z(v)），其中），其中: l(v) ：表從

31、頂點表從頂點u0到到v的一條路的權的一條路的權 z(v) ：v的先驅(qū)點，用以確定最短路的路線的先驅(qū)點，用以確定最短路的路線.l(v)為從頂點為從頂點u0到到v的最短路的權的最短路的權算法的過程就是在每一步改進這兩個標記，使最終算法的過程就是在每一步改進這兩個標記，使最終S：具有永久標號的頂點集：具有永久標號的頂點集.輸入輸入: G的帶權鄰接矩陣的帶權鄰接矩陣 w(u,v)備用備用-將求最短路與最短路徑結(jié)合起來將求最短路與最短路徑結(jié)合起來:算法步驟：算法步驟：l(v)u0vl(u)uw(u,v)首先寫出帶權鄰接矩陣首先寫出帶權鄰接矩陣0247820634460463403576301351022

32、73201847210W例例 求下圖從頂點求下圖從頂點u0到到其余頂點的最短路其余頂點的最短路因因G是無向圖，故是無向圖，故W是對稱陣是對稱陣1u0u6u7u2u4u3u5u見見Matlab程序程序-Dijkstra.doc2) 求賦權圖中任意兩頂點間的最短路求賦權圖中任意兩頂點間的最短路 算法的基本思想算法的基本思想 （I）求距離矩陣的方法）求距離矩陣的方法.（II）求路徑矩陣的方法）求路徑矩陣的方法.（III）查找最短路路徑的方法）查找最短路路徑的方法. Floyd算法：求任意兩頂點間的最短路算法：求任意兩頂點間的最短路. 舉例說明舉例說明算法的基本思想算法的基本思想（I）求距離矩陣的方法

33、）求距離矩陣的方法.（II）求路徑矩陣的方法）求路徑矩陣的方法.在建立距離矩陣的同時可建立路徑矩陣在建立距離矩陣的同時可建立路徑矩陣R ivjv（III）查找最短路路徑的方法）查找最短路路徑的方法.然后用同樣的方法再分頭查找若：然后用同樣的方法再分頭查找若：1av2av3avkav1bv2bvmbv（IV）Floyd算法：求任意兩頂點間的最短路算法：求任意兩頂點間的最短路.例例 求下圖中加權圖的任意兩點間的距離與路徑求下圖中加權圖的任意兩點間的距離與路徑. ,053142503330212044401210 )0(D,654321654321654321654321654321654321 )

34、0(R,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入點插入點 v1，得：得：,053132503330212043401210)1(D,654311654321654321654321154321654321 )1(R矩陣中帶矩陣中帶“=”的項為經(jīng)迭代比較以后有變化的元素的項為經(jīng)迭代比較以后有變化的元素.,min) 1() 1() 1()(kkjkikkijkijdddd插入點插入點 v2，得：得：,053132503330212043401210)1(D矩陣中帶矩陣中帶“=”的項為經(jīng)迭代比較以后有變化的元素

35、的項為經(jīng)迭代比較以后有變化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654333654322153321653221 )3(R插入點插入點 v3，得：得：,05313250333021204534012510)2(D,min) 1() 1() 1()(kkjkikkijkijdddd,0531325033302671204

36、53640127510)3(D插入點插入點 v4，得：得：,05313250359103302671520453964012107510)4(D,654311654444654333644322143321643221 )4(R,)4()5(DD插入點插入點 v5，得：得：,)4()5(RR,min) 1() 1() 1()(kkjkikkijkijdddd插入點插入點 v6，得：得：,05313250359103302671520453964012107510)5(D,053132503587330265152043386401275310)6(D.654311654466654336644

37、326163321666621 )6(R,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R8)6(52d8)6(52d故從故從v5到到v2的最短路為的最短路為8 6)6(52R由由v6向向v5追溯追溯: . 6)6(56R由由v6向向v2追溯追溯: , 1)6(62R. 2)6(12R所以從到的最短路徑為：所以從到的最短路徑為： .2165vvvv見見Matlab程序程序-Floyd.doc3最小生成樹及算法最小生成樹及算法1v1) 樹的定義與樹的特征樹的定義與樹的特征定義定義

38、連通且不含圈的無向圖連通且不含圈的無向圖稱為稱為樹樹常用常用T表示表示. 樹中的邊稱為樹中的邊稱為樹枝樹枝. 樹中度為樹中度為1的頂點稱為的頂點稱為樹葉樹葉.孤立頂點稱為孤立頂點稱為平凡樹平凡樹.2v3v4v5v平凡樹平凡樹定理定理2 設設G是具有是具有n個頂點的圖，則下述命題等價：個頂點的圖，則下述命題等價：1) G是樹（是樹（ G無圈且連通）；無圈且連通）；2) G無圈，且有無圈，且有n-1條邊；條邊；3) G連通，且有連通，且有n-1條邊；條邊；4) G無圈，但添加任一條新邊恰好產(chǎn)生一個圈無圈，但添加任一條新邊恰好產(chǎn)生一個圈; 5) G連通，且刪去一條邊就不連通了（即連通，且刪去一條邊就

39、不連通了（即G為為最最最小連通圖最小連通圖）；）；6) G中任意兩頂點間有唯一一條路中任意兩頂點間有唯一一條路.2）圖的生成樹）圖的生成樹定義定義 若若T是是包含圖包含圖G的全部頂點的全部頂點的子圖的子圖,它又是樹它又是樹,則稱則稱T是是G的的生成樹生成樹. 圖圖G中不在生成樹的邊叫做中不在生成樹的邊叫做弦弦.定理定理3 圖圖G=(V,E)有生成樹的充要條件是圖有生成樹的充要條件是圖G是連是連 通的通的.證明證明 必要性必要性是顯然的是顯然的.（II）找圖中生成樹的方法）找圖中生成樹的方法可分為兩種：避圈法和破圈法可分為兩種：避圈法和破圈法 A 避圈法避圈法 : 深探法和廣探法深探法和廣探法

40、B 破圈法破圈法 A 避圈法避圈法 定理定理3的充分性的證明提供了一種構造圖的生的充分性的證明提供了一種構造圖的生成樹的方法成樹的方法. 這種方法就是在已給的圖這種方法就是在已給的圖G中，每步選出一中，每步選出一條邊使它與已選邊不構成圈，直到選夠條邊使它與已選邊不構成圈，直到選夠n-1條邊為條邊為止止. 這種方法可稱為這種方法可稱為“避圈法避圈法”或或“加邊法加邊法” 在避圈法中，按照邊的選法不同，找圖中生在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種：成樹的方法可分為兩種：深探法深探法和和廣探法廣探法.a) 深探法深探法 若這樣的邊的另一端均已有標號，就退到標號為若這樣的邊的另一

41、端均已有標號，就退到標號為步驟如下：步驟如下：i) 在點集在點集V中任取一點中任取一點u,ii) 若某點若某點v已得標號，檢已得標號，檢端是否均已標號端是否均已標號. 若有邊若有邊vw之之w未標號未標號,則給則給w代代v，重復，重復ii).i-1的的r點點,以以r代代v,重復重復ii),直到全部點得到標號為止直到全部點得到標號為止.給以標號給以標號0.查一端點為查一端點為v的各邊，另一的各邊，另一w以標號以標號i+1，記下邊，記下邊vw.令令例例用深探法求出下圖用深探法求出下圖10的一棵生成樹的一棵生成樹 圖1001234567891011121313a) 深探法深探法圖10012345678

42、9101112步驟如下：步驟如下： 若這樣的邊的另一端均已有標號，就退到標號為若這樣的邊的另一端均已有標號，就退到標號為i) 在點集在點集V中任取一點中任取一點u,ii) 若某點若某點v已得標號，檢已得標號，檢端是否均已標號端是否均已標號. 若有邊若有邊vw之之w未標號未標號,則給則給w代代v，重復，重復ii).i-1的的r點點,以以r代代v,重復重復ii),直到全部點得到標號為止直到全部點得到標號為止.給給u以標號以標號0.查一端點為查一端點為v的各邊，另一的各邊，另一w以標號以標號i+1，記下邊，記下邊vw.令令例例用深探法求出下圖用深探法求出下圖10的一棵生成樹的一棵生成樹 3b)廣探法

43、廣探法步驟如下：步驟如下：i) 在點集在點集V中任取一點中任取一點u,ii) 令所有標號令所有標號i的點集為的點集為是否均已標號是否均已標號. 對所有未標對所有未標號之點均標以號之點均標以i+1,記下這些記下這些 iii) 對標號對標號i+1的點重復步的點重復步步驟步驟ii)，直到全部點得到，直到全部點得到給給u以標號以標號0.Vi,檢查檢查Vi,VVi中的邊端點中的邊端點邊邊.例例用廣探法求出下圖用廣探法求出下圖10的一棵生成樹的一棵生成樹 圖101012213212234標號為止標號為止.圖103b)廣探法廣探法步驟如下：步驟如下：i) 在點集在點集V中任取一點中任取一點u,ii) 令所有

44、標號令所有標號i的點集為的點集為是否均已標號是否均已標號. 對所有未標對所有未標號之點均標以號之點均標以i+1,記下這些記下這些 iii) 對標號對標號i+1的點重復步的點重復步步驟步驟ii)，直到全部點得到，直到全部點得到給給u以標號以標號0.Vi,檢查檢查Vi,VVi中的邊端點中的邊端點邊邊.例例用廣探法求出下圖用廣探法求出下圖10的一棵生成樹的一棵生成樹 圖101012213212234標號為止標號為止.顯然圖顯然圖10的生成樹的生成樹不唯一不唯一.B 破圈法 相對于避圈法，還有一種求生成樹的方法叫做相對于避圈法，還有一種求生成樹的方法叫做“破圈法破圈法”. 這種方法就是在圖這種方法就是

45、在圖G中任取一個圈，中任取一個圈，任意舍棄一條邊，將這個圈破掉，重復這個步驟任意舍棄一條邊，將這個圈破掉，重復這個步驟直到圖直到圖G中沒有圈為止中沒有圈為止.例例 用破圈法求出用破圈法求出下圖的一棵生成樹下圖的一棵生成樹.B 破圈法例例 用破圈法求出下圖的另一棵生成樹用破圈法求出下圖的另一棵生成樹.不難發(fā)現(xiàn)，圖不難發(fā)現(xiàn)，圖的生成樹不是的生成樹不是唯一的唯一的 .3) 最小生成樹與算法最小生成樹與算法 介紹最小樹的兩種算法：介紹最小樹的兩種算法：Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法. A Kruskal算法（或避圈法）算法（或避圈法）步驟如下：步驟如下： 1) 選擇邊選

46、擇邊e1，使得，使得w(e1)盡可能小；盡可能小；2) 若已選定邊若已選定邊 ，則從，則從ieee,.,21,.,21ieeeE中選取中選取 ，使得，使得:1iei) 為無圈圖，為無圈圖，,.,121ieeeG ii) 是滿足是滿足i)的盡可能小的權，的盡可能小的權，)(1iew 3) 當?shù)诋數(shù)?)步不能繼續(xù)執(zhí)行時，則停止步不能繼續(xù)執(zhí)行時，則停止.定理定理4 由由Kruskal算法構作的任何生成樹算法構作的任何生成樹,.,121*eeeGT都是最小樹都是最小樹.,876432eeeeee例例10用用Kruskal算法求下圖的最小樹算法求下圖的最小樹.在左圖中在左圖中 權值權值,.,821eee

47、最小的邊有最小的邊有 任取一條任取一條 ,51ee,1e 在在 中選取權值中選取權值,.,832eee,5e最小的邊最小的邊 中權值最小邊有中權值最小邊有 , 從中選從中選：73,ee;3e任取一條邊任取一條邊,87642eeeee會與已選邊構成圈會與已選邊構成圈,故停止故停止,得得中選取在中選取中選取在中選取,7e,42ee在 中選取中選取 . 但但 與與 都都,86ee84,ee4e8eB破圈法算法算法2 步驟如下：步驟如下： 1) 從圖從圖G中任選一棵樹中任選一棵樹T1.2) 加上一條弦加上一條弦e1，T1+e1中中 立即生成一個圈立即生成一個圈. 去掉此去掉此 圈中最大權邊，得到新圈中最大權邊，得到新樹樹T2,以以T2代代T1,重復重復2)再再檢查剩余的弦，直到全檢查剩余的弦，直到全部弦檢查完畢為止部弦檢查完畢為止.例例11用破圈法求下圖的最小樹用破圈法求下圖的最小樹.先求出上圖的一棵生成樹先求出上圖的一棵生成樹. 加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的權邊去掉最大的權邊e2,得到一棵新得到一棵新樹仍是原來的樹；樹仍是原來的樹；2e 再加上弦再加上弦e7，得到圈