1、數據結構數據結構 第七章 圖圖 第七章 圖主要內容主要內容圖的基本概念圖的基本概念1圖的存儲結構圖的存儲結構2圖的遍歷圖的遍歷3圖的常見應用圖的常見應用4教學要求教學要求教學重點教學難點目標要求1理解圖的基本概念及其術語；2.掌握圖的兩種存儲結構(鄰接矩陣和鄰接表)的表示方法3.熟練掌握圖的兩種遍歷算法、思想，步驟，能列出遍歷序列4.理解最小生成樹的概念，能按 Prim 算法構造最小生成樹；5.領會并掌握最短路徑、拓撲排序的算法思想1理解圖的定義、術語及其含義；2.掌握各種圖的鄰接矩陣表示法及其類型說明3.理解并掌握圖遍歷方法4.領會生成樹和最小生成樹的概念，掌握 Prim 算法思想；5.理解

2、并掌握最短路徑和Dijkstra方法算法思想1.正確理解與區別圖的常用術語2.區別圖的兩種存儲結構的不同點及其應用場合3. Prim 算法思想4. Dijkstra算法思想7.1圖的基本概念圖的基本概念圖圖是一種數據元素間可具有任意關系的一種數據結構是一種數據元素間可具有任意關系的一種數據結構 圖的特點圖的特點 頂點的前驅和后繼個數無限制頂點的前驅和后繼個數無限制 頂點之間的關系是任意的頂點之間的關系是任意的 圖中任意兩個頂點之間可能有關系圖中任意兩個頂點之間可能有關系 例例 .集成電路的布線集成電路的布線 城市之間的交通圖城市之間的交通圖 電路網絡的鋪設電路網絡的鋪設 圖的應用圖的應用 工程

3、進度的安排工程進度的安排數據庫系統的設計數據庫系統的設計 課程表的制定課程表的制定 西安西安北京北京南京南京杭州杭州上海上海 南京南京 西安西安 北京北京 上海上海杭州杭州7.1圖的基本概念圖的基本概念7.1.1 圖的定義圖的定義圖是由頂點集合圖是由頂點集合V V以及相關的邊集合以及相關的邊集合E E構成的一種非構成的一種非線性數據結構，記為：線性數據結構，記為：G =(V，E) V4 V1 V2 V5V3無向圖無向圖G1 V4 V1 V2 V3有向圖有向圖G2G1（V1，E1）,其中其中V1 = V（G1）= v1，v2，v3，v4，v5 E1 = E（G1) = (v1，v2),(v1，v

4、4),(v2，v3),(v3，v4）,(v3，v5), (v4，v5) G2（V2，E2），其中），其中 V2 = V（G2）=v1，v2，v3，v4 E2 = E（G2) =, , 頂點對代表邊，（）頂點對代表弧，有向圖有向圖G2 V4 V1 V2 V37.1.2關于圖的若干術語關于圖的若干術語頂點vi，vj之間有邊(vi,vj)或弧，則vi，vj互稱為鄰接頂點弧頭：弧尾：相關聯：對于有向圖，頂點v的入度是指以頂點v為弧頭的弧的數目稱為頂點的入度；記為ID(v)以頂點v為弧尾的弧的數目稱為頂點的出度，記為OD(v)。與頂點v相關聯的邊的數目稱為頂點的度；記為TD(v)對有向圖，是頂點的入度和

5、出度之和從頂點v出發，如果能順沿邊（對有向圖為弧）到達頂點u；則稱v到u之間有一條路徑.表示為一個頂點的序列.路徑長度：除路徑的第一個頂點和最后一個頂點外，在路徑頂點序列中同一頂點不重復出現的路徑稱為簡單路徑圖圖的若干的若干術語術語入度和出度頂頂點的度路路徑徑簡單簡單路徑徑鄰鄰接頂頂點 V4 V1 V2 V5V3無向圖無向圖G1ID(V1)=1ID(V1)=1ID(V3)=2ID(V3)=1TD(V3)=3TD(V1)=2(vi, vj)=(vj,vi)?=(v1 ， v2 ， v3 ， v5 ， v4 ， v3 )，路徑長度，路徑長度=5(v4 ， v3 ， v1 ， v2)，路徑長度，路徑

6、長度=3不是簡單路徑不是簡單路徑是簡單路徑是簡單路徑7.1.2關于圖的若干術語關于圖的若干術語子圖圖設G =(V,E)和G=(V,E)是兩個圖，若V是V的子集 ，且E是E的子集 ， 則圖G稱為圖G的子圖 V4 V1 V2 V5 V4 V1 V2 V5V3V1 V2 V5V3V1 V4 V1 V2 V5V3無向圖無向圖G1V1 V2V3 V4 V5V3V1 V2V3 V4 V1 V2 V5 V4 V2 V5V3哪些是G1的子圖？7.1.2關于圖的若干術語關于圖的若干術語有向圖有向圖G2 V4 V1 V2 V3 V4 V2 V3V1 V2 V3V1 V2 V3 V4 V1 V2 V3V1 V3 V

7、2 V3子圖圖設G =(V,E)和G=(V,E)是兩個圖，若V是V的子集 ，且E是E的子集 ， 則圖G稱為圖G的子圖如果一條路徑的第一個頂點和最后一個頂點為同一個頂點，則稱該路徑為回路，或稱環第一個頂點和最后一個頂點為同一個頂點的簡單路徑；或稱簡單環從頂點 vi到頂點vj有路徑，則說 vi和vj是連通的若圖中任意兩頂點之間都是連通（對于無向圖）對有向圖，如果任意一對頂點v ,u之間均有從v到u和從u到v的路徑存在圖圖的若干的若干術語術語入簡單簡單回路連連通連連通通圖圖強連連通圖圖回路 V4 V1 V2 V5V3無向圖無向圖G1有向圖有向圖G2 V4 V1 V2 V3回路回路(v1 ， v2 ，

8、 v3 ， v5 ， v4 ， v1 )回路回路:(v2 ， v3 ， v1 ， v2)回路回路(v1 ， v2 ， v3 ， v5 ， v4 ， v3 ， v2 ， v1 )7.1.2關于圖的若干術語關于圖的若干術語連通連通圖圖非強連通圖非強連通圖7.1.2關于圖的若干術語關于圖的若干術語無向圖的極大連通子圖無向圖的極大連通子圖（不存在包含它更大的連通子圖）（不存在包含它更大的連通子圖）連通分量連通分量任何連通圖的連通分量只有一個，即是其自身。非連通圖有多個連通分量（非連通圖的每一個連通部分）。無向圖無向圖( (非連通非連通) V2 V1 V3 V5 V9 V6 V8V7 V4 V2 V1

9、V3 V5 V4 V9 V6 V8V7無向圖無向圖3 3個連通分量個連通分量7.1.2關于圖的若干術語關于圖的若干術語有向圖中的極大強連通子圖有向圖中的極大強連通子圖。強連通分量強連通分量強連通圖只有一個強連通分量，即是其自身；非強連通的有向圖有多個強連通分量）。有向圖有向圖( (非強連通非強連通) ) V4 V1 V2 V3有向圖的有向圖的2 2個強連通分量個強連通分量 V4 V1 V2 V37.1.2關于圖的若干術語關于圖的若干術語與邊或弧相關聯的數稱為與邊或弧相關聯的數稱為“權權”帶有權的圖稱為帶權圖帶有權的圖稱為帶權圖，又稱為網，又稱為網權權帶權圖帶權圖權反應相關邊或弧的某種數量特征。

10、如表示從一個頂點到另一個頂點的距離、時間、電流、電壓、耗費、代價等 又分為無向網和有向網 V5 V1 V2V4 V6 V3 V5 V1 V2V4 V6 V315251930402515501525193040251550無向圖無向圖有向圖有向圖無向網無向網有向網有向網7.1.3 圖的基本性質圖的基本性質性質性質1.1. n n 個頂點的無向圖最多有個頂點的無向圖最多有 n(n-1)/2 n(n-1)/2 條邊，條邊，n n 個頂點的有向圖最多有個頂點的有向圖最多有n(n-1) n(n-1) 條弧條弧 。如果如果n n 個頂點的無向圖有個頂點的無向圖有 n(n-1)/2 n(n-1)/2 條邊，

11、則稱之為條邊，則稱之為無向完全圖無向完全圖如果如果n n 個頂點的有向圖有個頂點的有向圖有 n(n-1)n(n-1)條邊，則稱之為條邊，則稱之為有向完全圖有向完全圖 V2 V1V3V4 V5 有向圖中弧的取值范圍：0en(n-1)。（即：每兩個頂點之間都存在著一條邊) V2 V1 V3 V4 若圖中邊或弧的數目很少，則稱為稀疏圖。反之，若邊或弧的數目接近完全圖，則稱為稠密圖 無向完全圖無向完全圖有向完全圖有向完全圖7.1.3 圖的基本性質圖的基本性質性質性質2. 2. n n 個頂點的無向連通圖最少有個頂點的無向連通圖最少有(n-1)(n-1)條邊條邊。如果如果n n 個頂點的無向連通圖只有個

12、頂點的無向連通圖只有(n-1)(n-1)條邊，則該圖條邊，則該圖不存在回路不存在回路 如果如果n n個頂點而變數少于個頂點而變數少于n-1n-1，則一定是，則一定是非連通的非連通的如果如果n n 個頂點的無向連通圖的邊數大于個頂點的無向連通圖的邊數大于(n-1)(n-1)，則，則必存在回路必存在回路 樹樹生成樹：所有頂點均由邊連接在一起但不存在回路生成樹：所有頂點均由邊連接在一起但不存在回路的圖。的圖。 V4 V1 V2 V5V3無向圖無向圖 V4 V1 V2 V5V3 V4 V1 V2 V5V3無向圖的生成樹無向圖的生成樹一個圖可以有許多棵不同的生成樹7.1.4 圖的基本操作圖的基本操作每種

13、操作會因為圖的存儲結構不同而有所區別每種操作會因為圖的存儲結構不同而有所區別圖的基本操作深度優先遍歷深度優先遍歷刪除邊或弧刪除邊或弧插入頂點插入頂點頂點賦值頂點賦值創建圖創建圖讀取頂點讀取頂點查圖的頂點查圖的頂點讀取鄰接頂點讀取鄰接頂點刪除頂點刪除頂點插入邊或弧插入邊或弧廣度優先遍歷廣度優先遍歷7.2 圖的存儲結構圖的存儲結構7.2.1 鄰接矩陣表示法鄰接矩陣表示法鄰接矩陣表示法也稱數組表示法，采用兩個數組表示圖鄰接矩陣表示法也稱數組表示法，采用兩個數組表示圖 用一個一維數存儲頂點用一個一維數存儲頂點 用一個二維數組存儲頂點對之間的邊用一個二維數組存儲頂點對之間的邊 鄰接矩陣鄰接矩陣 V4 V

14、1 V2 V5V3無向圖無向圖矩陣矩陣元素元素定義：定義：Ai,jAi,j=1 1 對無向圖存在對無向圖存在( (vi,vjvi,vj) )邊邊, ,對有向圖存在對有向圖存在 邊邊 0 0 其他情況其他情況0110010101110100010101010V V1 1 V V2 2 V V3 3 V V4 4 V V5 5V V1 1 V V2 2 V V3 3 V V4 4 V V5 5鄰接矩陣鄰接矩陣7.2 圖的存儲結構圖的存儲結構7.2.1 鄰接矩陣表示法鄰接矩陣表示法 V4 V1 V2 V3有向圖有向圖0100000101000010V V1 1 V V2 2 V V3 3 V V4

15、4V V1 1 V V2 2 V V3 3 V V4 4 鄰接矩陣鄰接矩陣我們來觀察下圖的鄰接矩陣具有哪些特點？（1 1）無向圖或帶權無向圖的鄰接矩陣是一個對稱矩陣。可以采用下三角矩陣壓縮存儲）無向圖或帶權無向圖的鄰接矩陣是一個對稱矩陣。可以采用下三角矩陣壓縮存儲 （2 2）對無向圖，頂點）對無向圖，頂點vivi的度的度TD(viTD(vi) )是其鄰接矩陣中第是其鄰接矩陣中第i i行（或第行（或第i i列）中列）中“1”1”的個數的個數 （3 3）對有向圖，其鄰接矩陣中第）對有向圖，其鄰接矩陣中第i i行中行中“1”1”的個數是第的個數是第i i個頂點的出度個頂點的出度OD(viOD(vi)

16、 )。而第。而第i i列中列中“1”1”的個數的個數是第是第i i個頂點的入度個頂點的入度ID(viID(vi) ) （4 4）很容易確定圖或網中任意兩個頂點之間是否有邊或弧相連。對計算頂點的度比較方便有多少條邊或）很容易確定圖或網中任意兩個頂點之間是否有邊或弧相連。對計算頂點的度比較方便有多少條邊或弧則需要逐行逐列掃描矩陣弧則需要逐行逐列掃描矩陣 （5 5）所占存儲空間只與頂點個數有關，與邊數無關，在邊數較少時，空間浪費較大。因此，對稀疏圖而）所占存儲空間只與頂點個數有關，與邊數無關，在邊數較少時，空間浪費較大。因此，對稀疏圖而言，不適于用鄰接矩陣存儲。言，不適于用鄰接矩陣存儲。 7.2.1

17、 鄰接矩陣表示法鄰接矩陣表示法帶權圖的鄰接矩陣帶權圖的鄰接矩陣矩陣矩陣元素元素定義：定義：Ai,j=w wijij 對無向圖存在對無向圖存在( (vi,vjvi,vj) )邊邊, ,對有向圖存在對有向圖存在 邊邊 其他情況其他情況鄰接矩陣鄰接矩陣8471245398V V1 1 V V2 2 V V3 3 V V4 4 V V5 5V V1 1 V V2 2 V V3 3 V V4 4 V V5 5 V3 V1 V5V4 V2有向帶權圖有向帶權圖83478412957.2.1 鄰接矩陣表示法鄰接矩陣表示法3.3.鄰接矩陣的類型描述鄰接矩陣的類型描述#define Vmax 20 #define

18、 INFINITY 32768typedef char VType; typedef int EType; typedef struct VType vexsVmax; EType edgesVmaxVmax; int Vnum,Enum; MGRAGH; 最大頂點數設為20表示一個最大值 用于存儲頂點的數組，頂點表 用于存儲邊信息的矩陣，邊表 MGRAPH CREATMG(MGRAPH G) int i,j; char vi,vj; printf(please input the elemnts of vexs:n); for(i=0;(G.vexsi=getchar()!=#&iVmax;

19、i+); G.Vnum=i; for(i=0;iG.Vnum;i+) for(j=0;jG.Vnum;j+) G.edgesij=0; G.Enum=0; printf(please input the %d arc such as ab :,G.Enum+1); scanf(%c%c,&vi,&vj); while(vi!=#&vj!=#&G.EnumG.Vnum*(G.Vnum)-1) if(vi=vj) printf(input errorn); else i=LOC(G.vexs,vi); j=LOC(G.vexs,vj); if(i=-1|j=-1) printf(no vexsn)

20、; else if(G.edgesij=1) printf(input repetitiousn); else G.edgesij = 1; G.edgesji = 1; G.Enum+; printf(please input the %d arc :,G.Enum+1); scanf(%c%c,&vi,&vj); return（G）; 7.2.2 有關鄰接矩陣的算法有關鄰接矩陣的算法1.1.建立無向圖建立無向圖定義定義2 2個數組；個數組；初始化頂點數組初始化頂點數組vexsvexs。將矩陣的每個元素都初始化成將矩陣的每個元素都初始化成0 0。再讀入頂點對再讀入頂點對 ( (vi,vjvi

21、,vj),),將邊將邊 ( (vi,vjvi,vj) )置置1 1對等邊對等邊( (vj,vivj,vi) )也置成也置成1 17.2.3 鄰接表表示法鄰接表表示法基本思想：基本思想：再把所有單鏈表鄰接成一個表再把所有單鏈表鄰接成一個表 V4 V1 V2 V5V3無向圖無向圖對每個頂點建立一條單鏈表，每一條鏈存儲頂點數據及其與相關聯頂點的邊或弧對每個頂點建立一條單鏈表，每一條鏈存儲頂點數據及其與相關聯頂點的邊或弧鄰接點的位置號用一維數組存儲鏈頭結點，即頂點本身信息鄰接表：由若干個單鏈表構成n個頂點就建n個單鏈表一種順序分配與鏈一種順序分配與鏈式分配相結合的存式分配相結合的存儲方法儲方法7.2.

22、3 鄰接表表示法鄰接表表示法鏈頭結點結構：鏈頭結點結構：指針指針其他其他數據數據頂點位置號頂點位置號adjvex weight next比如權值比如權值鏈結點結構：鏈結點結構：指針指針頂點數據頂點數據vertex link指針指針頂點位置號頂點位置號adjvex next帶其他信息的鏈結點結構帶其他信息的鏈結點結構#define Vmax 20#define INFINITY 32768typedef char VertexType; typedef int EdgeType;typedef struct EnodeVertexType adjvex; EdgeType weight; str

23、uct arcnode *next;EDGENODE;typedef struct Vnode VertexType vertex; EDGENODE *link; HNODE;typedef struct HNODE hlistVmax;int vexnum,arcnum; LGRAPH;每個單鏈表由鏈頭結點和鏈結點構成每個單鏈表由鏈頭結點和鏈結點構成 定義鏈結點定義鏈結點定義鏈頭結點定義鏈頭結點定義圖定義圖指示第一條邊或弧指示第一條邊或弧存放與存放與 vi vi 鄰接的頂點在表鄰接的頂點在表頭數組中的位置頭數組中的位置指示下一條邊或弧指示下一條邊或弧鄰接表的類型描述：鄰接表的類型描述：7.

24、2.3 鄰接表表示法鄰接表表示法有向圖鄰接表的特點：有向圖鄰接表的特點：（1 1）第）第i i 個鏈表中結點數目為頂點個鏈表中結點數目為頂點i i的出度的出度；（2 2）所有鏈表中結點數目為圖中弧數；）所有鏈表中結點數目為圖中弧數；（3 3）占用的存儲單元數目為）占用的存儲單元數目為n+en+e 。不能直接求出頂點的入度不能直接求出頂點的入度無向圖鄰接表的特點：無向圖鄰接表的特點：（1 1）第）第i i 個鏈表中結點數目為頂點個鏈表中結點數目為頂點i i的度；的度；（2 2）所有鏈表中結點數目的一半為圖中邊數；）所有鏈表中結點數目的一半為圖中邊數；（3 3）占用的存儲單元數目為）占用的存儲單元

25、數目為n+2e n+2e 。有向圖的鄰接表：有向圖的鄰接表：1. 1. 聯系：聯系：鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結點個數等于一鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結點個數等于一行中非零元素的個數。行中非零元素的個數。2. 2. 區別：區別：對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。致），但鄰接表不唯一（鏈接次序與頂點編號無關）。3. 3. 用途：用途：鄰接矩陣多用于稠密圖的存儲（鄰接矩陣多用于稠密圖的存儲（e e接近接近n(n-1)/2)n(n-

26、1)/2)；而鄰接表多用于稀而鄰接表多用于稀疏圖的存儲（疏圖的存儲（enen2 2) )討論：鄰接表與鄰接矩陣有什么異同之處？討論：鄰接表與鄰接矩陣有什么異同之處？7.3 圖的遍歷圖的遍歷常見的圖遍歷方式有兩種：深度優先遍歷和廣度優先遍歷常見的圖遍歷方式有兩種：深度優先遍歷和廣度優先遍歷 從圖的某個頂點出發，訪問圖中每個頂點且每個頂點只訪問一次，稱為從圖的某個頂點出發，訪問圖中每個頂點且每個頂點只訪問一次，稱為圖的遍歷。圖的遍歷。 7.3.1 深度優先遍歷深度優先遍歷1首先訪問頂點首先訪問頂點i i2若當前訪問的頂點的若當前訪問的頂點的鄰接頂點有未被訪問鄰接頂點有未被訪問的，則任選一個訪問的，

27、則任選一個訪問之；之；反之，退回到最近訪反之，退回到最近訪問過的頂點；直到與問過的頂點；直到與起始頂點相通的全部起始頂點相通的全部頂點都訪問完畢；頂點都訪問完畢；3若此時圖中尚有頂點若此時圖中尚有頂點未被訪問，則再選其未被訪問，則再選其中一個頂點作為起始中一個頂點作為起始頂點并訪問之，重復頂點并訪問之，重復上述過程；上述過程； 反之，反之，遍歷結束遍歷結束為了避免重復訪為了避免重復訪問而造成死循環，問而造成死循環，我們要設定一個我們要設定一個訪問標識訪問標識出現這種情況的出現這種情況的是非連通圖我們是非連通圖我們這里不討論這里不討論訪問該結點后，訪問該結點后，將其訪問標記置將其訪問標記置為訪問

28、過，即為訪問過，即visitedivisitedi=1=1；7.3.1 深度優先遍歷深度優先遍歷 D A B E CGHF深度優先遍歷過程：深度優先遍歷過程： EB C FDAGHADGEBCFH起始訪問點起始訪問點深度優先遍歷序列：深度優先遍歷序列：這個序列并不是這個序列并不是唯一的唯一的7.3.1 深度優先遍歷深度優先遍歷深度優先遍歷算法：深度優先遍歷算法：void DFSTMG(MGRAPH G) int visitedM=0; int i,j; SEQSTACK S; S = INISTACK(); Visited0=1; printf(%c ,G.vexs0); S = PUSSTA

29、CK(S,0); S = PUSSTACK(S,0); while(!EMPSTACK(S) i = GETSTACK(S); for(j=0;j= G.Vnum) S = POPSTACK(S);7.3.2 廣度優先遍歷廣度優先遍歷廣度優先遍歷方法：廣度優先遍歷方法：1首先訪問頂點首先訪問頂點i i，并，并將其訪問標志置為已將其訪問標志置為已被訪問，即被訪問，即visitedivisitedi=1=1；2接著依次訪問與頂點接著依次訪問與頂點i i有邊相連的所有頂有邊相連的所有頂點點W1W1，W2W2，WtWt3然后再按順序訪問與然后再按順序訪問與W1W1，W2W2，WtWt有邊有邊相連又未曾

30、訪問過的相連又未曾訪問過的頂點；頂點；依此類推，直到圖中依此類推，直到圖中所有頂點都被訪問完所有頂點都被訪問完為止為止 7.3.2 廣度優先遍歷廣度優先遍歷 D A B E CGHF廣度優先遍歷過程：廣度優先遍歷過程： EB C FDAGHADEBGCHF起始訪問點起始訪問點廣度優先遍歷序列：廣度優先遍歷序列：這個序列也不是這個序列也不是唯一的唯一的7.3.2 廣度優先遍歷廣度優先遍歷廣度優先遍歷算法：廣度優先遍歷算法：void BFSTMG(MGRAPH G) int visitedM; int i=0,j; SEQUEUE Q; Q=INIQUEUE(Q); visited0=1; pri

31、ntf(%c ,G.vexs0); Q=INCQUEUE(Q,0); doi = GETQUEUE(Q); Q = OUTCQUEUE(Q); for(j=0;jG.Vnum;j+) if(G.edgesij=1 & visitedj!=1) visitj=1; printf(%c ,G.vexsj); Q=INCQUEUE(Q,j); while(!EMQUEUE（Q)）;7.4 圖的常見應用圖的常見應用圖的常見圖的常見應用應用關鍵路徑關鍵路徑，外排序，外排序等等拓撲排序拓撲排序問題問題最短路徑最短路徑問題問題最小生成最小生成樹問題樹問題是是圖圖的比的比較較典型的典型的應應用用7.4.1 最

32、短路徑問題最短路徑問題1.單源點最短路徑問題：單源點最短路徑問題：從某個源點到其余各頂點的最短路徑從某個源點到其余各頂點的最短路徑所謂最短路徑問題是指，如果從圖中某一頂點（源點）到達另一頂點（終點）所謂最短路徑問題是指，如果從圖中某一頂點（源點）到達另一頂點（終點）的路徑的路徑 ，沿此路徑上各邊的權值總和（稱為路徑長度）達到最小，沿此路徑上各邊的權值總和（稱為路徑長度）達到最小 在有多條通路的情況下，哪一條路最短在有多條通路的情況下，哪一條路最短 2個頂點之間沒個頂點之間沒有邊，但有可有邊，但有可能有間接通路能有間接通路2 2、迪杰斯特拉（、迪杰斯特拉（DijkstraDijkstra）算法：

33、）算法：按按路徑長度遞增路徑長度遞增次序產生各頂點的最短路徑。次序產生各頂點的最短路徑。 1、將源點到終點的所有路徑都列出來，然后在其中選最短的一條。、將源點到終點的所有路徑都列出來，然后在其中選最短的一條。 缺點：缺點：當路徑特別多時，特別麻煩；沒有規律可循。當路徑特別多時，特別麻煩；沒有規律可循。 V4 V1 V2 V5V3202510812183157.4.1 最短路徑問題最短路徑問題理解路徑長度遞增：理解路徑長度遞增： V4 V1 V2 V5V320251081218315選定源點：選定源點：v v1 1到其他各點的路徑中，必定只含一條弧到其他各點的路徑中，必定只含一條弧 v ，且其權

34、值最小。，且其權值最小。 由此，只要在所有從源點出發的弧中查找權值最小者。由此，只要在所有從源點出發的弧中查找權值最小者。 (18) (18)它只可能有兩種情況：它只可能有兩種情況： 1)1)、直接從源點到、直接從源點到 v vi i （只含一條弧只含一條弧）；）； 下一條下一條路徑長度次短路徑長度次短的最短路徑的最短路徑： (20) (20)2)2)、從源點經過頂點、從源點經過頂點 v v4 4，再到達，再到達 v vi i , , （由兩條弧組成由兩條弧組成）。）。v v4 4 必為已求得必為已求得的最短路徑上的最短路徑上的頂點的頂點V4V27.4.1 最短路徑問題最短路徑問題 可能有四種

35、情況：可能有四種情況： 1)1)、直接從源點到、直接從源點到 v vi i （由一條弧組成由一條弧組成）；）； 2)2)、從源點經過頂點、從源點經過頂點 v v4 4，再到達，再到達 v vi i , , （由兩條弧組成由兩條弧組成）；）； 3)3)、從源點經過頂點、從源點經過頂點 v v2 2，再到達，再到達 v vi i , , （由兩條弧組成由兩條弧組成）；）； 4)4)、從源點經過頂點、從源點經過頂點 v v4 4, , v v2 2，再到達，再到達 v vi i , , , , （由三條弧組成由三條弧組成）；）； 再下一條再下一條路徑長度次短路徑長度次短的最短路徑的特點：的最短路徑的

36、特點： , , (30) (30) V4 V1 V2 V5V320251081218315v v4 4 v v2 2必為已求必為已求得的最短路徑得的最短路徑上的頂點上的頂點其余最短路徑：其余最短路徑： 2)2)、從源點、從源點，再到達再到達（含有多條弧含有多條弧） V4V1 V2 V5V3202510812183151)1)、直接從源點到、直接從源點到 v vi i （只含一條弧只含一條弧）；）；V3V5 , , (33) (33)7.4.1 最短路徑問題最短路徑問題2.迪杰斯特拉算法思路：迪杰斯特拉算法思路： V4 V1 V2 V5V320251081218315步驟：步驟：（1）初始時，）

37、初始時，S只包含源點，只包含源點，S=v，v的距離為的距離為0。T包含除包含除v外的其他頂點，外的其他頂點，T中頂點的距離為頂點的權或中頂點的距離為頂點的權或 。（2）從）從T中選取一個距離最小的頂點中選取一個距離最小的頂點vi，把，把vi加入到加入到S中中（3）以）以k 作為新考慮的中間點，修改作為新考慮的中間點，修改T中各頂點的距離。中各頂點的距離。（4）重復步驟（）重復步驟（2）、（）、（3）直到所有頂點都包含在）直到所有頂點都包含在S中。中。終點終點從從 v v1 1 到各終點的最短路徑及長度到各終點的最短路徑及長度i i =1 =1i i =2 =2i i =3 =3i i =4 =

38、4v v1 1v v2 2v v3 3v v4 4v v5 5v vj j S S02018V1v418V40201833V2v220020301833V3v320+10020301833V5v518+157.4.2 最小代價生成樹問題最小代價生成樹問題1.最小代價生成樹的概念最小代價生成樹的概念生成樹：是一個極小連通子圖，它含有圖中全部頂點，但只有生成樹：是一個極小連通子圖，它含有圖中全部頂點，但只有n-1條邊。條邊。所有頂點均由邊連接在一起，但不存在回路的圖所有頂點均由邊連接在一起，但不存在回路的圖最小生代價成樹：給定一個無向網，在該網的所有生成樹中，使得各邊權數之和最小最小生代價成樹：給

39、定一個無向網，在該網的所有生成樹中，使得各邊權數之和最小的那棵生成樹稱為該網的最小代價生成樹，也叫最小生成樹。的那棵生成樹稱為該網的最小代價生成樹，也叫最小生成樹。 普里姆算法普里姆算法MST（Minimum cost Spanning Tree）性質）性質如何獲得圖的生成樹如何獲得圖的生成樹 如何獲得圖的最小代價生成樹如何獲得圖的最小代價生成樹 由深度優先遍歷得到的生成樹，獲得由深度優先遍歷得到的生成樹，獲得深度優先生成樹深度優先生成樹由廣度優先遍歷得到的生成樹，獲得廣度度優先生成樹由廣度優先遍歷得到的生成樹，獲得廣度度優先生成樹 7.4.2 最小代價生成樹問題最小代價生成樹問題2.普里姆算法：普里姆算法：E A FDG C B171912AEG14168D21615BC5F13Prim算法是從連通網中的某一個頂點開始，以此作為生成樹的初始狀態，然后不斷地將算法是從連通網中的某一個頂點開始，以此作為生成樹的初始狀態，然后不斷地將網中的網中的其它頂點其它頂點添加到生成樹上，直到最后一個頂點添加到生成樹上時得到最小生成樹添加到生成樹上，直到最后一個頂點添加到生成樹上時得到最小生成樹一端在生成樹中另一端在生成樹外的所以一端在生