圖的定義和基本術(shù)語圖的存儲結(jié)構(gòu)圖的遍歷生成樹最短路徑ppt課件

1、n 圖的定義和根本術(shù)語圖的定義和根本術(shù)語n 圖的存儲構(gòu)造圖的存儲構(gòu)造n 圖的遍歷圖的遍歷n 生成樹生成樹n 最短途徑最短途徑一一 、圖的定義、圖的定義 本章引見另一種非線性數(shù)據(jù)構(gòu)造 圖, 主要學(xué)習(xí)圖的存儲構(gòu)造以及假設(shè)干圖的操作的實現(xiàn)。 圖是一種多對多的構(gòu)造關(guān)系，每個元素可以圖是一種多對多的構(gòu)造關(guān)系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼。有零個或多個直接前趨；零個或多個直接后繼。 圖圖G由兩個集合構(gòu)成，記作由兩個集合構(gòu)成，記作G= (V, A) 其中其中V是頂點的非空有限集合，是頂點的非空有限集合， A 是邊的有限是邊的有限集合，其中邊是頂點的無序?qū)蛴行驅(qū)?，其中邊是頂點的無

2、序?qū)蛴行驅(qū)?此時此時的圖稱為無向圖或有向圖的圖稱為無向圖或有向圖)。無向圖無向圖G1=(V1, A1)G1=(V1, A1)， V1= v0 ,v1 ,v2 V1= v0 ,v1 ,v2 ,v3 ,v4 ,v3 ,v4 ，A1= (v0,v1) , (v0,v3) , (v1,v2) , A1= (v0,v1) , (v0,v3) , (v1,v2) , (v1,v4) , (v2,v3) , (v2,v4) (v1,v4) , (v2,v3) , (v2,v4) 無序?qū)o序?qū)?vi ,vj)：用銜接頂點用銜接頂點vi、vj的線段的線段表示，稱為無向邊；表示，稱為無向邊；G1圖示圖示 V0

3、V4 V3 V1 V2有序?qū)τ行驅(qū)?：用以為用以為vi起點起點(弧尾弧尾)、以、以vj為終點為終點(弧頭弧頭)的有向線段表示，稱為有向邊或弧；的有向線段表示，稱為有向邊或?。籊2 圖示圖示 V0 V1 V2 V3有向圖有向圖G2=(V2, A2)G2=(V2, A2)， V2=v0 V2=v0 v1,v2,v3 v1,v2,v3 ，A2= , , v2 A2= , , , ,v3 , 例例1 1 交通圖公路、鐵路交通圖公路、鐵路 頂點：地點頂點：地點 邊：銜接地點的路邊：銜接地點的路 交通圖中的有單行道、雙行道，分別用有向交通圖中的有單行道、雙行道，分別用有向 邊、無向邊表示；邊、無向邊表示；

4、例例2 2 電路圖電路圖 頂點：元件頂點：元件 邊：銜接元件之間的線路邊：銜接元件之間的線路例例3 3 通訊線路圖通訊線路圖 頂點：地點頂點：地點 邊：地點間的連線邊：地點間的連線例例4 4 各種流程圖各種流程圖( (如消費流程圖如消費流程圖) ) 頂點：工序頂點：工序 邊：各道工序之間的順序關(guān)系邊：各道工序之間的順序關(guān)系 V0 V4 V3 V1 V2 V0 V1 V2 V3圖的實例ADT Graph 數(shù)據(jù)對象數(shù)據(jù)對象V : V是具有一樣特性的數(shù)據(jù)元素的集合，是具有一樣特性的數(shù)據(jù)元素的集合， 稱為頂點集。稱為頂點集。 ADT 圖圖 的的 定定 義義根本操作根本操作 :CreateGraph(&

5、amp;G , V, V R ) / 按定義構(gòu)造圖按定義構(gòu)造圖 初始條件初始條件:V是圖的頂點集是圖的頂點集, V R 是圖中弧的集合。是圖中弧的集合。 操作結(jié)果操作結(jié)果:按按V和和V R的定義構(gòu)造圖的定義構(gòu)造圖G 。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R : R=VR VR =v ,w V ，且，且p(v ,w ) , 表表 示從示從v到到w 的弧，謂詞的弧，謂詞p(v ,w )定定義義 了弧了弧的意義或信息。的意義或信息。DestroyGraph (&G ) / 銷毀銷毀 初始條件初始條件:圖圖G存在。存在。 操作結(jié)果操作結(jié)果:銷毀圖銷毀圖G 。LocateVex(G, u) / 定位定位 初始條件初

6、始條件:圖圖G存在，存在，u 和和G中頂點有一樣特性中頂點有一樣特性 。 操作結(jié)果操作結(jié)果: 假設(shè)假設(shè)G中存在頂點中存在頂點u ，那么前往該頂點在，那么前往該頂點在 圖中位置圖中位置 ；否那么前往其它信息。；否那么前往其它信息。GetVex(G, v)/ 求值求值 初始條件初始條件:圖圖G存在，存在，v 是是G中某個頂點。中某個頂點。 操作結(jié)果操作結(jié)果:前往前往v的值。的值。PutVex(&G, v, value) / 賦值賦值 初始條件初始條件:圖圖G存在，存在，v 是是G中某個頂點。中某個頂點。 操作結(jié)果操作結(jié)果:對對 v 賦值賦值value。FirstAdjVex(G, v) /

7、 求第一個鄰接點求第一個鄰接點 初始條件初始條件:圖圖G存在，存在，v 是是G中某個頂點。中某個頂點。 操作結(jié)果操作結(jié)果:前往前往 v 的第一個鄰接點。假設(shè)頂點的第一個鄰接點。假設(shè)頂點v在在 G 中沒有鄰接頂點，那么前往中沒有鄰接頂點，那么前往“空空 。NextAdjVex(G, v, w) / 求下一個鄰接點求下一個鄰接點 初始條件初始條件:圖圖G存在，存在，v 是是G中某個頂點，中某個頂點， w 是是 v 的鄰接的鄰接點點 。 操作結(jié)果操作結(jié)果: 前往前往 v 的相對于的相對于 w 的下一個鄰接點。的下一個鄰接點。 假設(shè)假設(shè) w 是是 v 的最后一個鄰接點，那么前往的最后一個鄰接點，那么前

8、往“空?？铡nsertVex(&G, v); / 插入頂點插入頂點 初始條件初始條件:圖圖G存在，存在，v和和G中頂點有一樣特性中頂點有一樣特性 。 操作結(jié)果操作結(jié)果: 在圖在圖G中增添新頂點中增添新頂點v。DeleteVex(&G, v) /刪除頂點刪除頂點 初始條件初始條件: 圖圖G存在，存在， v和和G中頂點有一樣特性中頂點有一樣特性 。 操作結(jié)果操作結(jié)果:刪除刪除G中頂點中頂點v及其相關(guān)的弧。及其相關(guān)的弧。InsertArc(&G, v, w) /插入弧插入弧 初始條件初始條件:圖圖G存在，存在，v 和和w是是G中兩個頂點。中兩個頂點。 操作結(jié)果操作結(jié)果:在在

9、G中增添弧中增添弧，假設(shè)，假設(shè)G是無向的，是無向的， 那么還增添對稱弧那么還增添對稱弧。DeleteArc(&G, v, w) /刪除弧刪除弧 初始條件初始條件:圖圖G存在，存在，v 和和w是是G中兩個頂點。中兩個頂點。 操作結(jié)果操作結(jié)果:在在G中刪除弧中刪除弧，假設(shè)，假設(shè)G是無向的，是無向的， 那么還刪除對稱弧那么還刪除對稱弧。DFSTraverse(G, v, Visit() /深度優(yōu)先遍歷深度優(yōu)先遍歷 初始條件初始條件:圖圖G存在，存在，v 是是G中某個頂點，中某個頂點， Visit是頂點的運用函數(shù)是頂點的運用函數(shù) 。 操作結(jié)果操作結(jié)果: 從頂點從頂點v起深度優(yōu)先遍歷圖起深度優(yōu)先

10、遍歷圖G，并對每，并對每 個頂點調(diào)用函數(shù)個頂點調(diào)用函數(shù)Visit一次且僅一次。一次且僅一次。 一旦一旦Visit失敗，那么操作失敗。失敗，那么操作失敗。BFSTraverse(G, v, Visit() /廣度優(yōu)先遍歷廣度優(yōu)先遍歷 初始條件初始條件:圖圖G存在，存在，v 是是G中某個頂點，中某個頂點， Visit是頂點的運用函數(shù)是頂點的運用函數(shù) 。 操作結(jié)果操作結(jié)果: 從頂點從頂點v起廣度優(yōu)先遍歷圖起廣度優(yōu)先遍歷圖G，并對每，并對每 個頂點調(diào)用函數(shù)個頂點調(diào)用函數(shù)Visit一次且僅一次。一次且僅一次。 一旦一旦Visit失敗，那么操作失敗。失敗，那么操作失敗。2 頂點的度、入度、出度頂點的度、入

11、度、出度 頂點頂點v的度的度 TD(v)= 與與v相關(guān)聯(lián)的邊的數(shù)目。相關(guān)聯(lián)的邊的數(shù)目。 在有向圖中：頂點在有向圖中：頂點v的出度的出度OD(v) =以以v為起點有向邊數(shù)；為起點有向邊數(shù)； 頂點頂點v的入度的入度ID(v) =以以v為終點有向邊數(shù)；為終點有向邊數(shù)； TD(v) = OD(v) + ID(v) V0 V4 V3 V1 V2 V0 V1 V2 V3二、圖的根本術(shù)語二、圖的根本術(shù)語1 鄰接點及關(guān)聯(lián)邊鄰接點及關(guān)聯(lián)邊 鄰接點：邊的兩個頂點；鄰接點：邊的兩個頂點； 關(guān)聯(lián)邊：假設(shè)邊關(guān)聯(lián)邊：假設(shè)邊e= (v, u), 那么稱邊那么稱邊e與頂點與頂點 v和和u 相關(guān)聯(lián)；相關(guān)聯(lián)；設(shè)圖設(shè)圖G的頂點數(shù)為

12、的頂點數(shù)為n，邊數(shù)為，邊數(shù)為e那么圖的一切頂點的度數(shù)之和那么圖的一切頂點的度數(shù)之和 = 2*e 每條邊對圖的一切頂點的度數(shù)之和每條邊對圖的一切頂點的度數(shù)之和 “奉獻奉獻 2度度 無向圖無向圖G1有向圖有向圖G2 V0 V4 V3 V1 V2 V0 V1 V2 V3 途徑、回路途徑、回路(環(huán)環(huán)) 無向圖無向圖G1=V1，E1中的頂點序列中的頂點序列v1,v2, ,vk,假設(shè)假設(shè)(vi,vi+1)E1 ( i=1,2,k-1), v =v1, u =vk, 那么稱該序列是從頂點那么稱該序列是從頂點v到到頂點頂點u的途徑；假設(shè)的途徑；假設(shè)v=u，那么稱該序列為，那么稱該序列為回路；在回路；在G1中，

13、中，v0,v1,v2,v3 是是v0到到v3的途的途徑；徑； v0,v1,v2,v3 , v0是回路；是回路； 有向圖有向圖G2=V2，E2中的頂點序列中的頂點序列v1,v2, ,vk, E2 (i=1,2,k-1),假設(shè)假設(shè)v =v1, u =vk,那么稱該那么稱該 序列是從頂點序列是從頂點v到頂點到頂點u的途徑；假設(shè)的途徑；假設(shè)v=u，那么稱該序，那么稱該序 列為回路；在列為回路；在G2中，中， v0, v2, v3是是v0到到v3的途徑的途徑 v0,v2,v3,v0是回路；是回路； 簡單途徑和簡單回路簡單途徑和簡單回路 在一條途徑中在一條途徑中, ,假設(shè)一切頂假設(shè)一切頂點各不一樣點各不一

14、樣, ,那么稱該途徑為簡單途徑那么稱該途徑為簡單途徑；假設(shè)除起點和終點外；假設(shè)除起點和終點外, , 其他頂點各不一樣的回路稱為簡單其他頂點各不一樣的回路稱為簡單回路?；芈?。 例例有向圖有向圖G2無向圖無向圖G1 V0 V4 V3 V1 V2 V0 V1 V2 V3在圖在圖G1中，中，V0,V1,V2,V3 是簡單途徑；是簡單途徑； V0,V1,V2,V4,V1不是簡單途徑不是簡單途徑； 在圖在圖G2中，中，V0,V2,V3,V0是簡單回是簡單回路；路； 連通圖強連通圖連通圖強連通圖 在無有向圖在無有向圖G=( V, E )G=( V, E )中，假設(shè)對任何兩個頂點中，假設(shè)對任何兩個頂點 v v

15、、u u 都存都存在從在從v v 到到 u u 的途徑，那么稱的途徑，那么稱G G是連通是連通圖強連通圖圖強連通圖 非連通圖非連通圖 連通圖連通圖 強連通圖強連通圖 V0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1 V5 V4 非強連通圖非強連通圖設(shè)有兩個圖設(shè)有兩個圖G=V，E、G1= V1，E1，假設(shè)假設(shè)V1 V，E1 E，E1關(guān)聯(lián)的頂點都在關(guān)聯(lián)的頂點都在V1中，中，那么稱那么稱 G1是是G的子圖；的子圖； (a)(b)(c) V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V25 子圖子圖例 以下 (b

16、)、(c) 是 (a) 的子圖 (強)連通分量 無向圖G的極大連通子圖稱為G的連通分量。 極大連通子圖意思是：該子圖是 G 連通子圖，將G 的任何不在該子圖中的頂點參與，子圖不再連通； 連通分量連通分量非連通圖非連通圖 V0 V2 V3 V1 V5 V4 V0 V2 V1非連通分量非連通分量有向圖有向圖D 的極大強連通子圖稱為的極大強連通子圖稱為D 的強連通的強連通分量。極大強連通子圖意思是：該子圖是分量。極大強連通子圖意思是：該子圖是D強連通子圖，將強連通子圖，將D的任何不在該子圖中的頂?shù)娜魏尾辉谠撟訄D中的頂點參與，子圖不再是強連通的。點參與，子圖不再是強連通的。強連通分量強連通分量 V0

17、V1 V2 V3 V0 V2 V3 V1非強連通圖非強連通圖7 生成樹生成樹 包含無向圖包含無向圖G 一切頂點的極小連通一切頂點的極小連通子圖稱為子圖稱為G 的生成樹。極小連通子圖意思的生成樹。極小連通子圖意思是：該子圖是是：該子圖是G 的連通子圖，在該子圖中的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。刪除任何一條邊，子圖不再連通。 G的生成樹的生成樹 V0 V4 V3 V1 V2連通圖連通圖 G V0 V4 V3 V1 V2 V0 V4 V3 V1 V2假設(shè)假設(shè)T是是G 的生成樹當(dāng)且僅當(dāng)?shù)纳蓸洚?dāng)且僅當(dāng)T 滿足如下條件滿足如下條件： T是是G 的連通子圖；的連通子圖； T包含包含G

18、的一切頂點；的一切頂點； T中無回路。中無回路。一棵一棵n n個頂點的生成樹有且僅有足以構(gòu)成樹個頂點的生成樹有且僅有足以構(gòu)成樹的的n-1n-1條邊。條邊。闡明：闡明：G的生成樹的生成樹 V0 V4 V3 V1 V2連通圖連通圖 G V0 V4 V3 V1 V2 V0 V4 V3 V1 V2假設(shè)在一棵生成樹上刪除一條邊，就不再連假設(shè)在一棵生成樹上刪除一條邊，就不再連通。通。 假設(shè)在一棵生成樹上添加一條邊，必定構(gòu)成假設(shè)在一棵生成樹上添加一條邊，必定構(gòu)成一個環(huán)。一個環(huán)。 不再連通不再連通構(gòu)成環(huán)構(gòu)成環(huán) 由于圖中恣意兩個頂點之間都能夠存在聯(lián)由于圖中恣意兩個頂點之間都能夠存在聯(lián)絡(luò)，因此難以以數(shù)據(jù)元素在存儲

19、區(qū)中物理位置絡(luò)，因此難以以數(shù)據(jù)元素在存儲區(qū)中物理位置表示它們間的關(guān)系，仍可以借助數(shù)組表示之。表示它們間的關(guān)系，仍可以借助數(shù)組表示之。 另一方面，用也可以多重鏈表示圖。但由另一方面，用也可以多重鏈表示圖。但由于圖中頂點的度能夠相差懸殊，會因此呵斥空于圖中頂點的度能夠相差懸殊，會因此呵斥空間的浪費；反之，假設(shè)按每個頂點的度設(shè)計不間的浪費；反之，假設(shè)按每個頂點的度設(shè)計不同的結(jié)點構(gòu)造，又會呵斥操作上的不便。同的結(jié)點構(gòu)造，又會呵斥操作上的不便。 應(yīng)根據(jù)詳細(xì)的圖和需求，設(shè)計恰當(dāng)?shù)慕Y(jié)應(yīng)根據(jù)詳細(xì)的圖和需求，設(shè)計恰當(dāng)?shù)慕Y(jié)點構(gòu)造和表構(gòu)造。點構(gòu)造和表構(gòu)造。圖的存儲構(gòu)造至少要保管兩類信息圖的存儲構(gòu)造至少要保管兩類信息

20、： 1)1)頂點的數(shù)據(jù)；頂點的數(shù)據(jù)； 2)2)頂點間的關(guān)系。頂點間的關(guān)系。 如何表示頂點間的關(guān)系？ V0 V4 V3 V1 V2 V0 V1 V2 V3常用圖的存儲表示常用圖的存儲表示一、圖的數(shù)組一、圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲表示存儲表示二、圖的鄰接表存儲表示二、圖的鄰接表存儲表示三、有向圖的十字鏈表存儲表示三、有向圖的十字鏈表存儲表示 四、無向圖的鄰接多重表存儲表示四、無向圖的鄰接多重表存儲表示鄰接矩陣：鄰接矩陣：G的鄰接矩陣是滿足如下條件的的鄰接矩陣是滿足如下條件的n階矩陣：階矩陣： Aij=1 假設(shè)假設(shè)(vi,vj)E 或或 E0 否那么否那么0 1 0 1 00 1 0 1 00

21、 1 0 10 1 0 10 1 0 1 10 1 0 1 10 1 0 00 1 0 00 1 1 0 00 1 1 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 10 0 00 0 0 V0 V4 V3 V1 V2 V0 V1 V2 V3一、數(shù)組表示法一、數(shù)組表示法( (鄰接矩陣表示鄰接矩陣表示) )在數(shù)組表示法中，在數(shù)組表示法中，用鄰接矩陣表示頂點間的關(guān)系用鄰接矩陣表示頂點間的關(guān)系typedef struct ArcCell / 弧的定義弧的定義 VRType adj;/VRType是頂點關(guān)系類型。對無是頂點關(guān)系類型。對無權(quán)圖，權(quán)圖， /用用1或

22、或0表示相鄰否；對帶權(quán)圖，那么為表示相鄰否；對帶權(quán)圖，那么為權(quán)值類型。權(quán)值類型。 InfoType *info; / 該弧相關(guān)信息的指針該弧相關(guān)信息的指針 ArcCell , AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM; / 圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲表示存儲表示#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20/最大頂點個數(shù)typedef enumDG,DN,UDG, UDN graphkind； /有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef struct /圖的定義圖的定義 Vert

23、exType vexsMAX_VERTEX_NUM; /頂點向量頂點向量保管頂點數(shù)據(jù)保管頂點數(shù)據(jù) AdjMatrix arcs; /鄰接矩陣鄰接矩陣保管頂點間關(guān)保管頂點間關(guān)系系 int vexnum, arcnum; /頂點數(shù)，弧頂點數(shù)，弧數(shù)數(shù) GraphKind kind; /圖的種類標(biāo)志圖的種類標(biāo)志 MGraph;無向圖數(shù)組表示法特點：無向圖數(shù)組表示法特點：1 1無向圖鄰接矩陣是對稱矩陣，同一條邊表示了無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；兩次；0 1 0 1 00 1 0 1 00 1 0 10 1 0 10 1 0 1 10 1 0 1 10 1 0 00 1 0 00 1 1

24、 0 00 1 1 0 0對有向圖的數(shù)組表示法對有向圖的數(shù)組表示法可做類似的討論可做類似的討論 V0 V4 V3 V1 V22頂點頂點v的度：等于二維數(shù)組對應(yīng)行或列中的度：等于二維數(shù)組對應(yīng)行或列中1的個數(shù)；的個數(shù)；3判別兩頂點判別兩頂點v、u能否為鄰接點：只需判二維數(shù)組對應(yīng)能否為鄰接點：只需判二維數(shù)組對應(yīng)分量能否非零；分量能否非零；4頂點不變，在圖中添加、刪除邊：只需對二維數(shù)組對頂點不變，在圖中添加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦非零值或清零；應(yīng)分量賦非零值或清零；5用二維數(shù)組存儲頂點數(shù)為用二維數(shù)組存儲頂點數(shù)為 n的圖的圖, 占用存儲空間只與它占用存儲空間只與它的頂點數(shù)的頂點數(shù)n有關(guān)，與邊數(shù)

25、有關(guān)，與邊數(shù)e無關(guān)。適用于邊稠密的圖。無關(guān)。適用于邊稠密的圖。 圖的根本操作的實現(xiàn)圖的根本操作的實現(xiàn)(采用數(shù)組表示法采用數(shù)組表示法)：1求無向圖某頂點求無向圖某頂點vi的度：的度：(或有向圖或有向圖vi的出的出度度) Ai0 到到Ain-1中的非零個數(shù)，即數(shù)組中的非零個數(shù)，即數(shù)組A第第i行的非零元素的個數(shù)；行的非零元素的個數(shù)；0 1 0 1 00 1 0 1 00 1 0 10 1 0 10 1 0 1 10 1 0 1 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0 V0 V4 V3 V1 V2 V0 V1 V2 V30 1 1 00 1 1 00 0 0 00 0 0

26、00 0 0 10 0 0 10 0 00 0 02求有向圖某頂點求有向圖某頂點vi 的的 入度：入度：A0i到到An-1i 中中的非零個數(shù)，即數(shù)組的非零個數(shù)，即數(shù)組A中第中第i列的非零元素的個數(shù)；列的非零元素的個數(shù)；3求圖中的總邊數(shù)：掃描整個數(shù)組求圖中的總邊數(shù)：掃描整個數(shù)組A，統(tǒng)計出數(shù)組，統(tǒng)計出數(shù)組中非零元素的個數(shù)。無向圖的總邊數(shù)為非零元素個中非零元素的個數(shù)。無向圖的總邊數(shù)為非零元素個數(shù)的一半，而有向圖的總弧數(shù)為非零元素個數(shù)。數(shù)的一半，而有向圖的總弧數(shù)為非零元素個數(shù)。圖的構(gòu)造操作的實現(xiàn)圖的構(gòu)造操作的實現(xiàn)(采用數(shù)組表示法采用數(shù)組表示法)Status CreateGraph(Mgraph &am

27、p;G) /采用數(shù)組表示法采用數(shù)組表示法, 構(gòu)造圖構(gòu)造圖G scanf(&G.kind); switch(G.kind) case DG: return CreateDG(G); /構(gòu)造有向圖構(gòu)造有向圖G case DN: return CreateDN(G); /構(gòu)造有向網(wǎng)構(gòu)造有向網(wǎng)G case UDG: return CreateUDG(G);/構(gòu)造無向圖構(gòu)造無向圖G case UDN: return CreateUDN(G);/構(gòu)造無向網(wǎng)構(gòu)造無向網(wǎng)G default : return ERROR; / CreateGraph無向網(wǎng)的構(gòu)造算法無向網(wǎng)的構(gòu)造算法Status Creat

28、eUDN(Mgraph &G) /采用數(shù)組表示法采用數(shù)組表示法, 構(gòu)造無向網(wǎng)構(gòu)造無向網(wǎng)G scanf(&G.vexnum, &G.arcnum , &IncInfo); /IncInfo為為0那么各不含其它信息那么各不含其它信息 for(i=0;i G.vexnum;+i) scanf(G.vexsi); /構(gòu)造頂點構(gòu)造頂點向量向量 for(i=0;i G.vexnum;+i) /初始化鄰接矩陣初始化鄰接矩陣 for(j=0;j G.vexnum;+j) G.arcsij=INFINITY,NULL; for(k=0;k G.arcnum;+k) /構(gòu)造鄰接矩陣

29、構(gòu)造鄰接矩陣 scanf(&v1, &v2, &w); /輸入一條邊依靠的頂點及權(quán)輸入一條邊依靠的頂點及權(quán)值值 i=LocateVex(G,v1); j=LocateVex(G,v2); /確定確定v1和和v2在在G中位置中位置 G.arcsij.adj=w; /弧弧的權(quán)值的權(quán)值 if (IncInfo) input(* G.arcsij) /假設(shè)弧含有相關(guān)信息假設(shè)弧含有相關(guān)信息,那么輸入那么輸入 G.arcsji= G.arcsij /置置的對稱弧的對稱弧 return OK / CreateUDN例例V0V4V3V1V22 0 1 2 3 4V0V1V2V3V413

30、422110034下標(biāo)頂點頭指針編號1 1 無向圖的鄰接表無向圖的鄰接表 頂點通常按編號順序?qū)㈨旤c數(shù)據(jù)頂點通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中；關(guān)聯(lián)同一頂點的存儲在一維數(shù)組中；關(guān)聯(lián)同一頂點的邊用線性鏈表存儲。邊用線性鏈表存儲。二、鄰接表二、鄰接表該結(jié)點表示邊該結(jié)點表示邊V4, Vj,其中其中的的j是是Vj在一維數(shù)組中的位置在一維數(shù)組中的位置0 1 2 3 4 A B C D EABECD可見，在有向圖的可見，在有向圖的鄰接表中不易找到鄰接表中不易找到指向該頂點的弧。指向該頂點的弧。1 4230 122 2 有向圖的鄰接表有向圖的鄰接表ABECD303420 在有向圖的逆鄰接在有向圖的逆鄰接

31、表中，對每個頂點，鏈表中，對每個頂點，鏈接的是指向該頂點的弧。接的是指向該頂點的弧。A B C D E 012343 3 有向圖的逆鄰接表有向圖的逆鄰接表typedef struct ArcNode int adjvex; / 該弧所指向的頂點的位該弧所指向的頂點的位置置 struct ArcNode *nextarc; / 指向下一條弧的指針指向下一條弧的指針 InfoType *info; / 該弧相關(guān)信息的指該弧相關(guān)信息的指針針 ArcNode; / 表結(jié)點表結(jié)點弧的結(jié)點構(gòu)造弧的結(jié)點構(gòu)造adjvex nextarc info/ 圖的鄰接表存儲表示圖的鄰接表存儲表示typedef stru

32、ct VNode VertexType data; / 頂點信息頂點信息 ArcNode *firstarc; / 指向第一條依靠自該頂點的指向第一條依靠自該頂點的弧弧 VNode, AdjListMAX_VERTEX_NUM; / 頭結(jié)點、頭結(jié)點數(shù)組類頭結(jié)點、頭結(jié)點數(shù)組類型型 data firstarc頂點的結(jié)點構(gòu)造頂點的結(jié)點構(gòu)造typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 圖的種類標(biāo)志圖的種類標(biāo)志 ALGraph;圖的構(gòu)造定義圖的構(gòu)造定義(鄰接表鄰接表)無向圖的鄰接表的特點無向圖的鄰接表的特點 1在在G鄰接

33、表中，同一條邊對應(yīng)兩個表結(jié)點；鄰接表中，同一條邊對應(yīng)兩個表結(jié)點； 2頂點頂點v的度：等于的度：等于v對應(yīng)線性鏈表的長度；對應(yīng)線性鏈表的長度； 3斷定兩頂點斷定兩頂點v ，u能否鄰接：要看能否鄰接：要看v對應(yīng)線性對應(yīng)線性鏈表中有無對應(yīng)的結(jié)點鏈表中有無對應(yīng)的結(jié)點u ； 4在在G中增減邊：在兩個單鏈表插入、刪除結(jié)中增減邊：在兩個單鏈表插入、刪除結(jié)點；點； 5設(shè)存儲頂點的一維數(shù)組大小為設(shè)存儲頂點的一維數(shù)組大小為m(m圖的頂圖的頂點數(shù)點數(shù)n), 圖的邊數(shù)為圖的邊數(shù)為e，G占用存儲空間為：占用存儲空間為：m+2e，與，與 G 的頂點數(shù)、邊數(shù)均有關(guān)，適用于的頂點數(shù)、邊數(shù)均有關(guān)，適用于邊稀疏的圖。邊稀疏的圖。

34、 0 0 1 1 2 2 3 3 4 4V0V1V2V3V41 13 34 42 22 21 11 10 00 04 43 3鄰接表的空間代價鄰接表的空間代價與圖的邊及頂點數(shù)均有關(guān)與圖的邊及頂點數(shù)均有關(guān) V0 V4 V3 V1 V22 2三、有向圖的十字鏈表存儲表示三、有向圖的十字鏈表存儲表示 弧的結(jié)點構(gòu)造弧的結(jié)點構(gòu)造弧尾頂點位置弧尾頂點位置 弧頭頂點位置弧頭頂點位置 弧的相關(guān)信息弧的相關(guān)信息指向下一個有一指向下一個有一樣弧尾的結(jié)點樣弧尾的結(jié)點指向下一個有一指向下一個有一樣弧頭的結(jié)點樣弧頭的結(jié)點typedef struct ArcBox / 弧的構(gòu)造表示弧的構(gòu)造表示 int tailvex,

35、headvex; InfoType *info; struct ArcBox *tlink, *hlink; ArcBox;頂點的結(jié)點構(gòu)造頂點的結(jié)點構(gòu)造 頂點數(shù)據(jù)頂點數(shù)據(jù) 指向該頂點的指向該頂點的第一條入弧第一條入弧指向該頂點的指向該頂點的第一條出弧第一條出弧typedef struct VexNode / 頂點的構(gòu)造表示頂點的構(gòu)造表示 VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; / 頂點結(jié)點表頭向量頂點結(jié)點表頭向量 int vexnum, ar

36、cnum; /有向圖的當(dāng)前頂點數(shù)和弧數(shù)有向圖的當(dāng)前頂點數(shù)和弧數(shù) OLGraph;有向圖的構(gòu)造表示有向圖的構(gòu)造表示(十字鏈表十字鏈表) V1 V2 V3 V4v1v2v3v401232 3 3 2 2 03 13 00 10 2有向圖的十字鏈表有向圖的十字鏈表(圖示圖示 假設(shè)將有向圖的鄰接矩陣看成假設(shè)將有向圖的鄰接矩陣看成是稀疏矩陣的話，那么十字鏈表也是稀疏矩陣的話，那么十字鏈表也可以看成是鄰接矩陣的鏈表存儲構(gòu)可以看成是鄰接矩陣的鏈表存儲構(gòu)造。造。四、無向圖的鄰接多重表存儲表示四、無向圖的鄰接多重表存儲表示typedef struct Ebox VisitIf mark; / 訪問標(biāo)志訪問標(biāo)志

37、int ivex, jvex; / 該邊依靠的兩個頂點的位置該邊依靠的兩個頂點的位置 struct EBox *ilink, *jlink; / 分別依靠于這兩個頂點的下一條邊分別依靠于這兩個頂點的下一條邊 InfoType *info; / 該邊信息指針該邊信息指針 EBox;邊的構(gòu)造表示邊的構(gòu)造表示訪問訪問標(biāo)記標(biāo)記端點端點i i位置位置依附依附i i的的下一條邊下一條邊端點端點j j位置位置依附依附j(luò) j的的下一條邊下一條邊信息信息指針指針頂點的構(gòu)造表示頂點的構(gòu)造表示typedef struct VexBox VertexType data; EBox *firstedge; /第一條依靠

38、該頂點的第一條依靠該頂點的邊的指針邊的指針 VexBox;頂點的數(shù)據(jù)頂點的數(shù)據(jù) 第一條依靠該頂點的邊的指針第一條依靠該頂點的邊的指針 typedef struct / 鄰接多重表鄰接多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;無向圖的構(gòu)造表示無向圖的構(gòu)造表示 V1 V2 V4 V5 V3v1v2v3v4v5012340 10 3 2 12 34 1 2 4 2 4 在不同的存儲構(gòu)造下在不同的存儲構(gòu)造下，實現(xiàn)各種操作的效率，實現(xiàn)各種操作的效率能夠是不同的。所以在能夠是不同的。所以在求解實踐問題時，要根求解實踐

39、問題時，要根據(jù)求解問題所需操作，據(jù)求解問題所需操作，選擇適宜的存儲構(gòu)造。選擇適宜的存儲構(gòu)造。 在圖中，訪問某個頂點后，能夠沿著某在圖中，訪問某個頂點后，能夠沿著某條途徑又回到該頂點。為保證每一個頂點只被條途徑又回到該頂點。為保證每一個頂點只被訪問一次，必需記下已被訪問頂點，訪問一次，必需記下已被訪問頂點， 有兩種遍歷方法：有兩種遍歷方法： 深度優(yōu)先遍歷和廣度優(yōu)先遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷圖的遍歷算法是圖的許多算法的根底。圖的遍歷算法是圖的許多算法的根底。一一 深度優(yōu)先遍歷深度優(yōu)先遍歷1從中某頂點從中某頂點v起始點出發(fā)，訪問該頂點；起始點出發(fā)，訪問該頂點；2依次從依次從v的未被訪問的鄰接點出

40、發(fā)，繼續(xù)對圖的未被訪問的鄰接點出發(fā)，繼續(xù)對圖 進展深度優(yōu)先遍歷。直至圖中一切和進展深度優(yōu)先遍歷。直至圖中一切和v有途徑有途徑 相通的頂點都被訪問到；相通的頂點都被訪問到； 3假設(shè)圖中尚有頂點未被訪問，那么另選一個未假設(shè)圖中尚有頂點未被訪問，那么另選一個未被訪被訪 問頂點作起始點，反復(fù)問頂點作起始點，反復(fù)1、 2，直至圖中，直至圖中 一切頂點都被訪問到為止。一切頂點都被訪問到為止。 V0 V7 V6 V5 V4 V3 V2 V1圖圖G步驟：步驟：闡明：闡明：( (強強) )連通圖連通圖的遍歷只須執(zhí)行的遍歷只須執(zhí)行1 1和和 2 2兩步。兩步。Vw1SG1SG2SG3W1、W2和和W3 均為均為

41、V 的鄰接點，的鄰接點，SG1、SG2 和和 SG3 分別為含頂點分別為含頂點W1、W2和和W3 的子圖。的子圖。訪問頂點訪問頂點 V ;for (W1、W2、W3 ) 假設(shè)該鄰接點假設(shè)該鄰接點Wi未被訪問，未被訪問， 那么從它出發(fā)進展深度優(yōu)先搜索遍那么從它出發(fā)進展深度優(yōu)先搜索遍歷。歷。w2w3w2 V0 V7 V6 V5 V4 V3 V2 V1,V6例求圖求圖G以以V0起始點的的深度優(yōu)先序列起始點的的深度優(yōu)先序列V0V1V3V2V7V5 V4V0 ,V1 ,V4 ,V7 ,V3 ,V2 ,V5 ,V6 V0 ,V1,V3 ,V7 ,V4 ,V2,V5圖圖GV6由于沒有規(guī)定訪問鄰接點的由于沒有

42、規(guī)定訪問鄰接點的順序，深度優(yōu)先序列不獨一順序，深度優(yōu)先序列不獨一 為保證每一個頂點只被訪問一次，必為保證每一個頂點只被訪問一次，必 須對頂點進展標(biāo)志。普通用一個輔須對頂點進展標(biāo)志。普通用一個輔助數(shù)組助數(shù)組 visited作為對頂點的標(biāo)志，當(dāng)頂作為對頂點的標(biāo)志，當(dāng)頂點點vi未被訪問，未被訪問，visitedi值為值為FALSE；當(dāng)當(dāng)vi已被訪問，那么已被訪問，那么visitedi值為值為TRUE或被訪問時的次序號?；虮辉L問時的次序號。闡明： 從深度優(yōu)先搜索遍歷連通圖的過程類從深度優(yōu)先搜索遍歷連通圖的過程類 似于樹的先根遍歷似于樹的先根遍歷;假設(shè)將圖的頂點的未被假設(shè)將圖的頂點的未被訪問鄰接點看作樹

43、結(jié)點的孩子，訪問鄰接點看作樹結(jié)點的孩子，圖的深度優(yōu)先遍歷與樹的圖的深度優(yōu)先遍歷與樹的先根遍歷是類似的。先根遍歷是類似的。 圖的深度優(yōu)先遍歷圖的深度優(yōu)先遍歷 從圖中某頂點從圖中某頂點v v出發(fā)：出發(fā)： 1 1訪問頂點訪問頂點v v； 2 2依次從依次從v v的未被訪問的鄰接點的未被訪問的鄰接點 出發(fā)，對圖進展深度優(yōu)先遍歷出發(fā)，對圖進展深度優(yōu)先遍歷。樹的先根遍歷樹的先根遍歷 假設(shè)樹非空假設(shè)樹非空 1 1訪問根結(jié)點訪問根結(jié)點； 2 2依次先根遍依次先根遍歷各歷各 棵子樹。棵子樹。比較比較類似類似void DFSTraverse(Graph G, Status (*Visit)(int v) / 對圖

44、對圖 G 作深度優(yōu)先遍歷作深度優(yōu)先遍歷 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問標(biāo)志數(shù)組初始化訪問標(biāo)志數(shù)組初始化 for (v=0; vw1, V-w2, V-w8 V-w1, V-w2, V-w8 的途徑長度為的途徑長度為1;1;V-w7, V-w3, V-w5的途徑長度為的途徑長度為2 ;V-w6, V-w4 的途徑長度為的途徑長度為3。w1Vw2w7w6w3w8w5w4闡明：在廣度優(yōu)先遍歷圖時， “先被訪問的頂點的鄰接點 先于“后被訪問的頂點的鄰 接點被訪問。即以V為起 始點，由近至遠(yuǎn)，依次訪問

45、和V有途徑相通且途徑長度 為1，2，的頂點。Q 在廣度優(yōu)先遍歷中在廣度優(yōu)先遍歷中, ,為使為使“先被訪問的頂點先被訪問的頂點, ,其鄰接其鄰接點亦先被訪問點亦先被訪問 , ,需附設(shè)隊列需附設(shè)隊列Q Q保管被訪問過的頂點，保管被訪問過的頂點，并控制遍歷頂點的順序。并控制遍歷頂點的順序。V0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7 V0 V7 V6 V5 V4 V3 V2 V1 算法開場時算法開場時, ,將起始點訪問后將起始點訪問后插入插入Q Q中中, , 以后以后, ,當(dāng)當(dāng)Q Q不空時就從不空時就從Q Q中刪除一個頂點中刪除一個頂點, ,每刪每刪除一個頂點除一個頂點, ,就依

46、次訪問它的每一個未被訪問過的鄰接就依次訪問它的每一個未被訪問過的鄰接點點, ,并令其進隊。這樣并令其進隊。這樣, ,當(dāng)當(dāng)Q Q為空時為空時, ,闡明一切與起始點闡明一切與起始點有途徑相通的頂點都已訪問終了。有途徑相通的頂點都已訪問終了。 V0 V7 V6 V5 V4 V3 V2 V1 V2void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化訪問標(biāo)志初始化訪問標(biāo)志 InitQueue(Q); / 置空的輔助隊列置空的輔助隊列Q for ( v=0; vG.v

47、exnum; +v ) if ( !visitedv) / v 尚未訪問尚未訪問 visitedv = TRUE; Visit(v); EnQueue(Q, v);/ v入入隊列隊列 while (!QueueEmpty(Q) DeQueue(Q, u); / 隊頭元素出隊并置為隊頭元素出隊并置為u for(w=FirstAdjVex(G, u); w ; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / BFSTraverse 圖的廣度優(yōu)先遍歷算法圖的廣度優(yōu)先遍歷算法求一條從頂點求一條

48、從頂點 i 到頂點到頂點 s 的簡單途徑的簡單途徑abchdekfg 求從頂點求從頂點 b 到頂點到頂點 k 的的 一條簡單途徑。一條簡單途徑。 從頂點從頂點 b 出發(fā)進展出發(fā)進展深度優(yōu)先搜索遍歷深度優(yōu)先搜索遍歷例如例如: 假設(shè)找到的第一個鄰接點是假設(shè)找到的第一個鄰接點是a, 那么得到的結(jié)點訪問序列為那么得到的結(jié)點訪問序列為: b a d h c e k f g 假設(shè)找到的第一個鄰假設(shè)找到的第一個鄰接點是接點是c,那么得到的結(jié)那么得到的結(jié)點訪問序列為點訪問序列為: b c h d a e k f g遍歷運用的一個例子遍歷運用的一個例子無向連通圖無向連通圖G的生成樹的生成樹 生成樹是一個圖生成樹

49、是一個圖G 的一個極小的連通子圖的一個極小的連通子圖，包含圖，包含圖G 的一切頂點，但只需的一切頂點，但只需n-1 條邊。生條邊。生成樹可由遍歷過程中所經(jīng)過的邊組成。深度優(yōu)成樹可由遍歷過程中所經(jīng)過的邊組成。深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；廣先遍歷得到的生成樹稱為深度優(yōu)先生成樹；廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。 V0 V7 V6 V5 V4 V3 V2 V1 V3 V0 V7 V6 V5 V4 V2 V1深度優(yōu)先生成樹深度優(yōu)先生成樹(連通網(wǎng)的)最小生成樹廣度優(yōu)先生成樹廣度優(yōu)先生成樹 在在n個城市間建立通訊個城市間建立通訊聯(lián)絡(luò)網(wǎng)，要思

50、索的問題是聯(lián)絡(luò)網(wǎng)，要思索的問題是:如何在保證如何在保證n點連通的前提點連通的前提下最節(jié)省經(jīng)費下最節(jié)省經(jīng)費3 36 65 52 21 16 65 55 5V5V4V2V0V3V14 46 6例例即要構(gòu)造連通網(wǎng)N的最小生成樹。這應(yīng)在 N的一切帶權(quán)的邊中選取 n1 條邊不構(gòu)成回路，使權(quán)值之和為最小。最小生成樹最小支撐樹最小生成樹最小支撐樹最小生成樹是無向連通網(wǎng)的一切生成樹中最小生成樹是無向連通網(wǎng)的一切生成樹中邊的權(quán)值之和最小的一棵生成樹。邊的權(quán)值之和最小的一棵生成樹。最小生成樹的構(gòu)造算法最小生成樹的構(gòu)造算法nMST性質(zhì)：性質(zhì)：多數(shù)最小生成樹的構(gòu)造算法都利用了下述性質(zhì)。多數(shù)最小生成樹的構(gòu)造算法都利用了

51、下述性質(zhì)。 設(shè)設(shè)N=V，E是一個連通網(wǎng)，是一個連通網(wǎng)，U V，U。假設(shè)。假設(shè)u , v是一條具最是一條具最小有權(quán)值的邊，其中小有權(quán)值的邊，其中u U，v VU，那么必存在一棵包含邊那么必存在一棵包含邊u , v的最小的最小生成樹。生成樹?？捎梅醋C法證之可用反證法證之 普里姆普里姆(Prim)算法和克魯斯卡爾算法和克魯斯卡爾(Kruskal )算法是利用算法是利用MST性質(zhì)的兩種構(gòu)造性質(zhì)的兩種構(gòu)造最小生成樹的算法。最小生成樹的算法。1. 普里姆算法普里姆算法普里姆算法的根本思想普里姆算法的根本思想:貪婪算法貪婪算法 任取一圖N中頂點v 作為生成樹的根，之后不斷往“生成樹的頂點集U上添加頂點 w

52、(VU ) 。新添的頂點 w 和已在U的頂點v 之間必定存在一條邊(v , w) ： (v , w) 權(quán)值在一切連通頂點 v (U )和 w (VU ) 之間的邊中權(quán)值最小的，并將(v , w)并入“生成樹的邊集TE中。直至U =V TE中有 n-1條邊為止。V3V1V4V6V5V26665551324V3V1V4V6V5V2普里姆算法構(gòu)造最小生成樹的過程普里姆算法構(gòu)造最小生成樹的過程V3V1V4V6V5V2V3V1V4V6V5V2UV-UTEV3V1V4V6V5V2(v1,v3),(v3,v6),(v6,v4),(v3,v2),(v2,v5) 為實現(xiàn)此算法需設(shè)置輔助數(shù)組為實現(xiàn)此算法需設(shè)置輔助

53、數(shù)組closedge ，對當(dāng)前對當(dāng)前VU中每個頂點，記錄從中每個頂點，記錄從U到到VU的代價最小的邊：的代價最小的邊：struct VertexType adjvex; / U集中的頂點序號集中的頂點序號 VRType lowcost; / 邊的權(quán)值邊的權(quán)值 closedgeMAX_VERTEX_NUM; 顯然，對顯然，對vi VU有有closedge i-1. lowcost =Mincost(u, vi)| u Uclosedge0123456AdjvexLowcostiabcdegf195141827168213127aaa19141814例如:e12ee8168d3dd7213c5 5

54、16e21edcbagfa b c d e f g所得生成樹權(quán)值和所得生成樹權(quán)值和= 14+8+3+5+16+21 = 67 a b c d e f g 0 1 2 3 4 5 6 19 14 1819 5 7 12 5 3 7 3 8 12 8 16 21 2718 16 27 構(gòu)造最小生成樹的普里姆算法構(gòu)造最小生成樹的普里姆算法void MiniSpantree_PRIM( mgraph G, VertexType u ) 輔助數(shù)組輔助數(shù)組closedge的定義的定義 k=LocateVex(G,u); for (j=0; jG.vexnum; +j) /輔助數(shù)組初始化輔助數(shù)組初始化 if

55、(j!=k) closedgej= u,G.arcskj.arj ; closedgek.lowcost=0; / 起始點起始點u并入并入U(=u)for (i=1; iG.vexnum; +i) /k=mininum(closedge); /求下一個頂點：第求下一個頂點：第k頂點頂點printf(closedgek.adjvex, G. vexsk) / 輸出生成樹輸出生成樹的邊的邊closedgek.lowcost=0; /第第k頂點并入頂點并入Ufor (j=0; jG.vexnum; +j) / 重新選擇最小邊重新選擇最小邊 if(G.arcskj.arj closedgej.lowc

56、ost) closedgej=G.vexsk,G.arcskj.arj 詳細(xì)做法詳細(xì)做法: 先構(gòu)造一個只含先構(gòu)造一個只含 n 個頂點的個頂點的子圖子圖 SG，然后從權(quán)值最小的邊開場，然后從權(quán)值最小的邊開場，假設(shè)它的添加不使假設(shè)它的添加不使SG 中產(chǎn)生回路，那中產(chǎn)生回路，那么在么在 SG 上加上這條邊，如此反復(fù)，直上加上這條邊，如此反復(fù)，直至加上至加上 n-1 條邊為止。條邊為止。思索問題的出發(fā)點思索問題的出發(fā)點: 為使生成樹上邊的為使生成樹上邊的權(quán)值之和到達(dá)最小，那么應(yīng)使生成樹中權(quán)值之和到達(dá)最小，那么應(yīng)使生成樹中每一條邊的權(quán)值盡能夠地小。每一條邊的權(quán)值盡能夠地小?？唆斔箍査惴ǖ母舅枷耄嚎唆?/p>

57、斯卡爾算法的根本思想：abcdegf195141816821312727148531621例如例如: :7121819cdbaegf27一、從某個源點到各頂點的最短途徑一、從某個源點到各頂點的最短途徑V5 V4 1006053010V1 V2 V0 V3102050始始 終終 途徑途徑點點 點點 長度長度最短途徑最短途徑v0 v1 無無 v2 (v0,v2) 10v5 (v0,v4 ,v3,v5) 60v4 (v0, v4) 30v3 (v0,v4 ,v3) 50迪杰斯特拉迪杰斯特拉( Dijkstra )算法算法 迪杰斯特拉提出一個求按途徑長度遞增次迪杰斯特拉提出一個求按途徑長度遞增次序產(chǎn)生

58、的最短途徑算法。其根本思想為序產(chǎn)生的最短途徑算法。其根本思想為: 設(shè)置設(shè)置S為已求得最短途徑的終點的集合，并為已求得最短途徑的終點的集合，并用數(shù)組用數(shù)組D記錄當(dāng)前所找到的從源點記錄當(dāng)前所找到的從源點v到每個終點到每個終點的最短特殊途徑長度特殊途徑或是弧，或是的最短特殊途徑長度特殊途徑或是弧，或是中間只經(jīng)過中間只經(jīng)過S中頂點的途徑。初始時，中頂點的途徑。初始時， S為空；為空；Di值為源值為源v到每個頂點到每個頂點vi的權(quán)值。按以下方法的權(quán)值。按以下方法不斷擴展不斷擴展S：每次從：每次從V S中取出具有最短特殊中取出具有最短特殊途徑長度的頂點添加到途徑長度的頂點添加到S中，同時對中，同時對D作必要的作必要的修正修正(假設(shè)假設(shè)