1、第七章第七章 圖圖多對多的關系多對多的關系學習要點：學習要點：v圖的基本概念與相關有向圖、無向圖、網(wǎng)和連通圖概念。圖的基本概念與相關有向圖、無向圖、網(wǎng)和連通圖概念。v圖的鄰接矩陣與鄰接表存儲結構及其特性。圖的鄰接矩陣與鄰接表存儲結構及其特性。v圖的深度優(yōu)先和廣度優(yōu)先遍歷方法及其在鄰接表存儲結構中的圖的深度優(yōu)先和廣度優(yōu)先遍歷方法及其在鄰接表存儲結構中的實現(xiàn)算法。實現(xiàn)算法。v圖與樹的聯(lián)系與區(qū)別，圖的生成樹與最小生成樹。圖與樹的聯(lián)系與區(qū)別，圖的生成樹與最小生成樹。v圖的最短路徑。圖的最短路徑。v圖的應用：最短路徑、拓撲排序與關鍵路徑。圖的應用：最短路徑、拓撲排序與關鍵路徑。27.1 基本概念與相關描

2、述基本概念與相關描述7.1.1 圖的基本概念圖的基本概念v“圖圖”（Graph）也稱為網(wǎng)狀結構，它由一個非空的也稱為網(wǎng)狀結構，它由一個非空的頂點（頂點（vertex）集合）集合V和一個描述頂點之間鄰接關系的和一個描述頂點之間鄰接關系的邊（邊（edge）集合集合E組成，而組成，而E中每條邊連接的兩個頂點都屬于集合中每條邊連接的兩個頂點都屬于集合V。一。一個圖個圖G可以記為：可以記為：G =（V，E）。v多對多的關系，非線性結構多對多的關系，非線性結構vV(G)：頂點的非空有限集合：頂點的非空有限集合vE(G)：圖中邊的有限集合：圖中邊的有限集合37.1.1 圖的基本概念圖的基本概念2v有向圖：弧

3、（有向邊），有向圖：?。ㄓ邢蜻叄?，v :xy,x鄰接到鄰接到y(tǒng)，y鄰接自鄰接自xv 與與x、y相關聯(lián)相關聯(lián)v 4v無向圖：邊（無向邊），無向圖：邊（無向邊），v (x,y):xy,x與與y相鄰接相鄰接v (x,y) 與與x、y相關聯(lián)相關聯(lián)v (x,y) = (y,x)7.1.1 圖的基本概念圖的基本概念3子圖子圖：V(B)V(B)屬于屬于V(A)V(A)，且，且E(B)E(B)屬于屬于E(A)E(A)，則則B B是是A A的子圖。的子圖。 （B B是是A A中的一部分）中的一部分）57.1.2 圖的相關概念圖的相關概念1.頂點鄰接與頂點的度頂點鄰接與頂點的度 頂點的度頂點的度 相鄰接頂點的個數(shù)

4、，相鄰接頂點的個數(shù)，頂點頂點vi的度記的度記為為D(vi)。 有向圖頂點的度有向圖頂點的度 v出度出度：以頂點以頂點vi為弧尾的弧的個數(shù)，記為為弧尾的弧的個數(shù)，記為OD(vi)；v入度入度：以頂點以頂點vi為弧頭的弧的個數(shù)，記為為弧頭的弧的個數(shù)，記為ID(vi)。D(vi)=ID(vi)+OD(vi) 邊數(shù)與頂點度關系邊數(shù)與頂點度關系 在圖的頂點數(shù)在圖的頂點數(shù)n、邊數(shù)、邊數(shù)e以及各頂點的度以及各頂點的度D(vi)（1in）三者之間存在如下關系：）三者之間存在如下關系：62e= D(vi)ni 17.1.2 圖的相關概念圖的相關概念21.路徑與路徑長度路徑與路徑長度7 無向圖的路徑無向圖的路徑

5、在頂點在頂點vi與頂點與頂點vj之間存在一個邊的序列：（之間存在一個邊的序列：（vi, vi1），），（vi1, vi2），），（，（vim, vj）。）。 有向圖的路徑有向圖的路徑 頂點頂點vi與頂點與頂點vj之間存在一個弧的序列：之間存在一個弧的序列：， 。 路徑長度路徑長度 由頂點由頂點vi到頂點到頂點vj路徑上擁有的邊的個數(shù)。路徑上擁有的邊的個數(shù)。 簡單路徑與回路簡單路徑與回路 若在一條路徑上出現(xiàn)的頂點都不同，則稱其為若在一條路徑上出現(xiàn)的頂點都不同，則稱其為“簡單路徑簡單路徑”或或“簡單回路簡單回路（環(huán)環(huán)cycle）”。7.1.2 圖的相關概念圖的相關概念33.無向完全圖與有向完全圖無

6、向完全圖與有向完全圖v有向完全圖有向完全圖：每個頂點都與其它任意頂點有弧。：每個頂點都與其它任意頂點有弧。v 共共 條邊。條邊。n*(n-1)n*(n-1)/28v無向完全圖無向完全圖：每個頂點都與其它任意頂點有邊。：每個頂點都與其它任意頂點有邊。v 共共 條邊。條邊。7.1.2 圖的相關概念圖的相關概念44.連通圖與連通分量連通圖與連通分量 連通分量連通分量 在無向圖在無向圖G中，盡可能多地從集合中，盡可能多地從集合V及及E里收集頂點里收集頂點和邊，使它們成為該圖的一個和邊，使它們成為該圖的一個極大的連通子圖極大的連通子圖，這個子圖就被，這個子圖就被稱為是無向圖稱為是無向圖G的一個的一個“連

7、通分量連通分量”。9 連通圖連通圖 在無向圖在無向圖G中，任意一對頂點之間都是連通的。中，任意一對頂點之間都是連通的。7.1.2 圖的相關概念圖的相關概念44.連通圖與連通分量連通圖與連通分量210 強連通圖和弱連通圖強連通圖和弱連通圖 在有向圖在有向圖G中，若對其中任意兩個頂點中，若對其中任意兩個頂點vi和和vj互有互有路徑路徑可達可達，則稱，則稱G強連通圖；如果任意兩個頂點都至少存在強連通圖；如果任意兩個頂點都至少存在單向路徑，則稱單向路徑，則稱G是弱連通圖。是弱連通圖。n個頂點的強連通圖應當個頂點的強連通圖應當至少有至少有n條弧條弧。 強連通分量和弱連通分量強連通分量和弱連通分量 有向圖

8、有向圖G中的極大強連通子圖稱為中的極大強連通子圖稱為G的的強連通分量，而其中的極大弱連通子圖稱為強連通分量，而其中的極大弱連通子圖稱為G的弱連通分量。的弱連通分量。7.1.2 圖的相關概念圖的相關概念55.邊的權值與網(wǎng)絡邊的權值與網(wǎng)絡11 邊的權值邊的權值 圖的邊或弧依附上圖的邊或弧依附上的的某種數(shù)值稱為某種數(shù)值稱為“權值權值”或或“權（權（weight）”。例如地圖上連接兩個城市的鐵路線在其例如地圖上連接兩個城市的鐵路線在其上附有該鐵路線的里程數(shù)等。上附有該鐵路線的里程數(shù)等。 網(wǎng)絡網(wǎng)絡 邊或弧上帶有權的圖稱為邊或弧上帶有權的圖稱為“網(wǎng)絡網(wǎng)絡”或或“網(wǎng)圖網(wǎng)圖”。7.2 圖的存儲圖的存儲7.2.

9、1基于鄰接矩陣存儲基于鄰接矩陣存儲v用二維數(shù)組表示頂點的鄰接關系用二維數(shù)組表示頂點的鄰接關系 1、圖的鄰接矩陣（、圖的鄰接矩陣（n頂點用頂點用n階方陣）階方陣）12A = 0011010010101100111000010110001011001、圖的鄰接矩陣、圖的鄰接矩陣2鄰接矩陣特點：鄰接矩陣特點： 無向圖鄰接矩陣無向圖鄰接矩陣對稱對稱，有向圖不對稱，有向圖不對稱 無向圖第無向圖第i行行(列列)非零元素個數(shù)非零元素個數(shù)即為結點即為結點i的的度度 有向圖第有向圖第i行行(列列)非零元素個數(shù)即為結點非零元素個數(shù)即為結點i的出的出(入入)度度 容易確認任兩點之間是否有邊，但掃描邊數(shù)代價大容易確認

10、任兩點之間是否有邊，但掃描邊數(shù)代價大 （對每個結點進行檢測）（對每個結點進行檢測）132、網(wǎng)絡的鄰接矩陣、網(wǎng)絡的鄰接矩陣143、鄰接矩陣存儲算法、鄰接矩陣存儲算法算法算法7-1 有向圖有向圖G鄰接矩陣算法。鄰接矩陣算法。設置一個一維數(shù)組設置一個一維數(shù)組Gv，用于存放，用于存放G的頂點數(shù)據(jù)信息；設置一個二維數(shù)組的頂點數(shù)據(jù)信息；設置一個二維數(shù)組Ge，用于存放，用于存放G中有關弧的信息；設置變量中有關弧的信息；設置變量n和和e，記錄圖的頂點個，記錄圖的頂點個數(shù)和弧的個數(shù)信息。數(shù)和弧的個數(shù)信息。1500 Create_Gm(MGraph *Gm)01 02 scanf(%d,%d, &Gm-n, &G

11、m-e); /* 輸入頂點和弧的個數(shù)信息輸入頂點和弧的個數(shù)信息 */03 for (i=1; in; i+)04 scanf(%d, Gm-Gvi);05 for (i=1; in; i+) /* 鄰接矩陣初始化鄰接矩陣初始化 */06 for (j=1; jn; j+)07 if (i = j)08 Gm-Geij = 0;09 else10 Gm-Geij = ;11 for (k=1; ke; k+) /* 輸入輸入e條弧條弧 */12 13 scanf (%d%d, &i, &j);14 Gm-Geij = 1;15 16 7.2.2 基于鄰接表存儲基于鄰接表存儲00 struct e

12、node /* 定義邊結點結構定義邊結點結構 */01 02 int adjvex;03 struct enode *next;04 ;16 vertex fadj （a）單鏈表單鏈表頭（頂點）頭（頂點）結點結點 （b）單鏈表單鏈表邊邊結點結點 adjvex next 05 struct vnode /* 定義頂點結點結構定義頂點結點結構 */06 07 vertextype vertex; /* 頂點類型為頂點類型為vertextype */08 struct enode *fadj;09 ;10 typedef struct /* 定義一個圖鄰接表類型定義一個圖鄰接表類型 */11 12

13、struct vnode GvMAX; /* 圖的鄰接表圖的鄰接表 */13 int n, e; /* 圖的頂點數(shù)、邊數(shù)信息圖的頂點數(shù)、邊數(shù)信息 */14 RGraph;7.2.2 基于鄰接表存儲基于鄰接表存儲217 1 3 2 3 4 5 4 1 1 2 4 5 vertex next fadj adjvex 6 1 6 2 4 3 5 6 4 6 圖圖7-12 圖圖7-5（5）所示無向圖鄰接表存儲結構）所示無向圖鄰接表存儲結構7.2.2 基于鄰接表存儲基于鄰接表存儲3網(wǎng)絡的鄰接表：網(wǎng)絡的鄰接表：18單鏈表單鏈表邊邊結點結構結點結構 adjvex next vertex fadj 單鏈表單鏈

14、表頭頭結點結構結點結構 weight 1 2 3 4 1 1 76 3 53 3 23 weight fadj adjvex 23 2 34 3 23 4 53 next 2 76 vertex 7.2.2 基于鄰接表存儲基于鄰接表存儲4算法算法7-2 有向圖鄰接表存儲算法。有向圖鄰接表存儲算法。設置由單鏈表表頭結點組成的一維數(shù)組設置由單鏈表表頭結點組成的一維數(shù)組Gv，用于存放圖的頂點序號（，用于存放圖的頂點序號（vertex）以及指向頂點單鏈表的指針（）以及指向頂點單鏈表的指針（fadj）；設置變量）；設置變量n和和e，記錄，記錄圖的頂點個數(shù)和弧的個數(shù)信息。圖的頂點個數(shù)和弧的個數(shù)信息。190

15、0 Create_Gr(RGraph *Gr)01 02 struct enode *ptr;03 scanf(%d,%d, &Gr-n, &Gr-e);/* 輸入頂點和弧的個數(shù)信息輸入頂點和弧的個數(shù)信息 */04 for (i=1; in; i+) /* 對一維數(shù)組對一維數(shù)組Gv進行初始化進行初始化 */05 06 Gr-Gvi.vertex = i;07 Gr-Gvi.fadj = NULL;08 09 for (k=1; ke; k+) /* 構造各頂點的單鏈表構造各頂點的單鏈表 */10 11 scanf (%d,%d, &i, &j);12 ptr = (struct enode *

16、)malloc(sizeof(enode); /* 申請新結點申請新結點 */13 ptr-adjvex = j;14 ptr-next = Gr-Gvi.fadj; /* 新結點鏈入鄰接表新結點鏈入鄰接表 */15 Gr-Gvi.fadj = ptr;16 17 問題：如何求有向圖頂點的入度？問題：如何求有向圖頂點的入度？v解：可建立有向圖的逆鄰接表解：可建立有向圖的逆鄰接表20 正正鄰接表：方便求頂點的鄰接表：方便求頂點的出出度度 逆逆鄰接表：方便求頂點的鄰接表：方便求頂點的入入度度7.3 圖的遍歷圖的遍歷從圖的某一個頂點出發(fā)訪問圖中的所有頂點，且每個頂點從圖的某一個頂點出發(fā)訪問圖中的所有

17、頂點，且每個頂點只被訪問一次的過程。只被訪問一次的過程。21步驟如下：步驟如下：v 在圖在圖G中指定一個頂點中指定一個頂點v0作為遍歷開始頂點，先訪問作為遍歷開始頂點，先訪問v0并將其并將其進行適當標記表明已被訪問。進行適當標記表明已被訪問。v 依次從依次從v0的還未被訪問的各個鄰接頂點的還未被訪問的各個鄰接頂點w出發(fā)遞歸地進行深度出發(fā)遞歸地進行深度優(yōu)先搜索優(yōu)先搜索。v 如果圖中還存在未訪問過的頂點，則選其中之一由其出發(fā)重復如果圖中還存在未訪問過的頂點，則選其中之一由其出發(fā)重復上述步驟上述步驟“”“”“”，直到圖中所有頂點都被訪問。，直到圖中所有頂點都被訪問。7.3.1 深度優(yōu)先遍歷深度優(yōu)先遍

18、歷過程（利用棧結構）：過程（利用棧結構）：v 指定起點指定起點qv 訪問訪問qv q進棧進棧v ?？辗?？?？辗瘢縱 a：不空，轉：不空，轉 v b：空，轉：空，轉 找棧頂元素未訪問鄰接點找棧頂元素未訪問鄰接點q a：找到，轉：找到，轉 b：找不到，出棧，轉：找不到，出棧，轉 結束結束遍歷結果遍歷結果：n結點，（結點，（n1）條邊，無回路）條邊，無回路按遍歷過程經(jīng)過的邊為一棵深度優(yōu)先生成樹。按遍歷過程經(jīng)過的邊為一棵深度優(yōu)先生成樹。22例子：例子：求下圖從頂點求下圖從頂點v0出發(fā)的深度遍歷序列。出發(fā)的深度遍歷序列。23解：解： v v0 0 v v1 1 v v3 3 v v4 4 v v5 5

19、v v2 2算法算法7-3 基于鄰接表的無向圖深度優(yōu)先搜索算法基于鄰接表的無向圖深度優(yōu)先搜索算法 00 Depth_Gr(RGraph *Gr, int n)01 02 for (i=1; i=n; i+) /* 記錄頂點是否被訪問的一維數(shù)組記錄頂點是否被訪問的一維數(shù)組flag初始化初始化 */03 flagi = 0;04 for (i=1; inext) /* 沿著沿著vi的鏈表前進的鏈表前進 */15 16 k = ptr-adjvex;17 if (flagk = 0)/* 對未訪問的頂點繼續(xù)深度優(yōu)先搜索對未訪問的頂點繼續(xù)深度優(yōu)先搜索 */18 DFS(Gr, k, flag);19

20、20 25上機：上機： 使用鄰接表存儲圖，編寫其深度優(yōu)先遍歷的非遞歸算法。使用鄰接表存儲圖，編寫其深度優(yōu)先遍歷的非遞歸算法。26 過程：過程：v 訪問地點；起點進棧；訪問地點；起點進棧；v while （棧不空）（棧不空）v 找棧頂未訪問鄰接點找棧頂未訪問鄰接點p；v if 找到找到v 訪問；進棧；訪問；進棧；v elsev 出棧；出棧； 7.3.2 廣度優(yōu)先遍歷廣度優(yōu)先遍歷步驟如下：步驟如下：v 在圖中指定一個頂點在圖中指定一個頂點v0為遍歷起始點，訪問頂點為遍歷起始點，訪問頂點v0并將其進行并將其進行標記以表明被訪問；標記以表明被訪問；v 依次訪問依次訪問 v0 的所有相鄰頂點的所有相鄰頂

21、點 w1, w2, , wx ，此時需要為，此時需要為 v 的的鄰接頂點規(guī)定一種順序，然后依次訪問與鄰接頂點規(guī)定一種順序，然后依次訪問與 w1, w2, , wx 鄰接的鄰接的所有未訪問頂點直到所有已訪問頂點的相鄰頂點都已訪問。所有未訪問頂點直到所有已訪問頂點的相鄰頂點都已訪問。v 如果圖中還有未訪問頂點，則選擇其中之一作為新的遍歷起始如果圖中還有未訪問頂點，則選擇其中之一作為新的遍歷起始頂點，由其出發(fā)進行廣度優(yōu)先搜索直到所有頂點都已訪問。頂點，由其出發(fā)進行廣度優(yōu)先搜索直到所有頂點都已訪問。27算法算法7-4 基于鄰接表的無向圖廣度優(yōu)先搜索算法基于鄰接表的無向圖廣度優(yōu)先搜索算法00 Bread

22、th_Gr(RGraph *Gr, int n)01 02 for (i=0; in; i+) /* 記錄頂點是否被訪問的一維數(shù)組記錄頂點是否被訪問的一維數(shù)組flag初始化初始化 */03 flagi = 0;04 for (i=0; in; i+) /* 對整個圖進行廣度優(yōu)先搜索遍歷對整個圖進行廣度優(yōu)先搜索遍歷 */05 if (flagi = 0) 06 BFS(Gr, i, flag); /* 從頂點從頂點vi開始對圖進行廣度優(yōu)先遍歷開始對圖進行廣度優(yōu)先遍歷 */07 28算法算法7-4 基于鄰接表的無向圖廣度優(yōu)先搜索算法基于鄰接表的無向圖廣度優(yōu)先搜索算法2 08 BFS(RGraph

23、*Gr, int i, int flag )09 10 Qs_front=0; /* 隊首、隊尾指針初始化隊首、隊尾指針初始化 */11 Qs_rear=0;12 Qs_rear + ;13 QsQs_rear = i ;/* 讓頂點讓頂點vi的序號進隊列的序號進隊列 */14 flagi = 1;15 printf (%d, i);/* 訪問頂點訪問頂點vi */16 while (front adjvex;24 if (flagk = 0)25 26 flagk = 1;27 pringf (%d, k);28 Qs_rear + ;29 QsQs_rear = k ; 30 31 ptr

24、 = ptr-next;32 33 34 30過程（利用隊列結構）：過程（利用隊列結構）：v 訪問指定起點訪問指定起點qv q所有未訪問鄰接點依次訪問、入隊列所有未訪問鄰接點依次訪問、入隊列v 隊列空否：隊列空否：v a：不空，出隊列賦為：不空，出隊列賦為q，轉，轉 v b：空，轉：空，轉v 結束結束遍歷結果：遍歷結果：n結點，（結點，（n1）條邊，無回路）條邊，無回路按遍歷過程經(jīng)過的邊為一棵廣度優(yōu)先生成樹。按遍歷過程經(jīng)過的邊為一棵廣度優(yōu)先生成樹。31例子：例子：求下圖從頂點求下圖從頂點v0出發(fā)的廣度遍歷序列。出發(fā)的廣度遍歷序列。32解：解： v v0 0 v v1 1 v v2 2 v v3

25、 3 v v4 4 v v5 5注意：注意：v深度優(yōu)先遍歷或者廣度優(yōu)先遍歷能遍歷到指深度優(yōu)先遍歷或者廣度優(yōu)先遍歷能遍歷到指定起點所在的連通分量中的所有頂點。定起點所在的連通分量中的所有頂點。337.3.3簡單路徑與路徑長度最小路徑簡單路徑與路徑長度最小路徑 給定一個圖給定一個圖G和其中兩個頂點和其中兩個頂點vi和和vj，通常存在著，通常存在著vi和和vj連接多連接多條簡單路徑，其中必有一條路徑長度最短的路徑。條簡單路徑，其中必有一條路徑長度最短的路徑。具體做法具體做法如下：如下：34v1) 將鏈隊列結點改為將鏈隊列結點改為“雙鏈雙鏈”結點結點 即結點中包含即結點中包含next 和和prior兩

26、兩個指針；個指針；v2) 修改進入隊列操作修改進入隊列操作 插入新的隊尾結點時，令其插入新的隊尾結點時，令其prior域的指針域的指針指向剛剛出隊列的結點，即當前的隊頭指針所指結點；指向剛剛出隊列的結點，即當前的隊頭指針所指結點；v3) 修改出隊列的操作修改出隊列的操作 出隊列時，僅移動隊頭指針，而不將隊頭結出隊列時，僅移動隊頭指針，而不將隊頭結點從鏈表中刪除。點從鏈表中刪除。7.3.3簡單路徑與路徑長度最小路徑簡單路徑與路徑長度最小路徑算法算法7-5 路徑長度最短路徑算法路徑長度最短路徑算法3500 typedef DuLinkList QueuePtr; 01 void InitQueue

27、(LinkQueue& Q) 02 03 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);04 Q.front-next = Q.rear-next = NULL05 06 void EnQueue( LinkQueue& Q, QelemType e )07 08 p = (QueuePtr) malloc (sizeof(QNode);09 p-data = e; p-next = NULL;10 p-priou = Q.front11 Q.rear-next = p; Q.rear = p;12 15 void DeQueue( LinkQue

28、ue& Q, QelemType& e )16 17 Q.front = Q.front-next; e = Q.front-data18 例子：例子：設有如圖所示無向圖，需要計算出從設有如圖所示無向圖，需要計算出從v0到到v5的路的路徑長度最短的路徑。徑長度最短的路徑。36解：鏈隊列結構：解：鏈隊列結構： 3 0 2 4 1 5 例子（續(xù)）：例子（續(xù)）：計算過程：計算過程：37狀狀 態(tài)態(tài) Qs Flag 訪問頂點訪問頂點 入隊頂點入隊頂點 出隊頂點出隊頂點 初始初始 v0 flag0=1 v0 v0 01 v0 v0 02 v0,v1 flag1=1 v1 v1 03 v0,v1,v2 fl

29、ag2=1 v2 v2 04 v0,v1,v2 v1 05 v0,v1,v2 v2 06 v0,v1,v2, v3 flag3=1 v3 v3 07 v0,v1,v2, v3, v4 flag4=1 v4 v4 08 v0,v1,v2, v3, v4 v3 09 v0,v1,v2, v3, v4 , v5 flag5=1 v5 v5 10 v0,v1,v2, v3, v4, v5 v4 7.4 生成樹與最小生成樹生成樹與最小生成樹7.4.1 圖的生成樹圖的生成樹v 生成樹極小連通子圖（生成樹極小連通子圖（n-1）條邊）條邊“極小極小”的含義包括兩個方面含義：的含義包括兩個方面含義： 如果在生成

30、樹中去掉任何一條邊，生成樹將會不再連通；如果在生成樹中去掉任何一條邊，生成樹將會不再連通； 如果在生成樹中添加任何一條邊，生成樹將會出現(xiàn)回路。如果在生成樹中添加任何一條邊，生成樹將會出現(xiàn)回路。387.4.1 圖的生成樹圖的生成樹21、深度和廣度優(yōu)先生成樹、深度和廣度優(yōu)先生成樹v從從連通圖連通圖G任一頂點出發(fā)對任一頂點出發(fā)對G進行遍歷可訪問進行遍歷可訪問G的所有頂點。遍歷的所有頂點。遍歷時經(jīng)過的邊加上所有頂點就構成時經(jīng)過的邊加上所有頂點就構成G的一個連通子圖，這樣的連通的一個連通子圖，這樣的連通子圖就是子圖就是G的一棵生成樹。的一棵生成樹。 生成樹不唯一生成樹不唯一：深度優(yōu)先生成樹（：深度優(yōu)先生

31、成樹（DFS） 廣度優(yōu)先生成樹（廣度優(yōu)先生成樹（BFS） 39例子：例子：設有如圖所示無向設有如圖所示無向圖，畫出其深度優(yōu)先和圖，畫出其深度優(yōu)先和廣度優(yōu)先生成樹。廣度優(yōu)先生成樹。40解：解：例子：例子：設有如圖所示有向設有如圖所示有向圖，畫出其深度優(yōu)先和圖，畫出其深度優(yōu)先和廣度優(yōu)先生成樹。廣度優(yōu)先生成樹。41解：解：7.4.2 最小生成樹最小生成樹1、圖的最小生成樹、圖的最小生成樹v 網(wǎng)絡中所有生成樹中代價最小的樹。網(wǎng)絡中所有生成樹中代價最小的樹。復習：網(wǎng)絡的鄰接矩陣：復習：網(wǎng)絡的鄰接矩陣：427.4.2 最小生成樹最小生成樹22、普里姆、普里姆(Prim)算法算法原理：原理：選取一個頂點作為

32、起點，每次通過代價最小的邊選擇一個頂選取一個頂點作為起點，每次通過代價最小的邊選擇一個頂點并入生成樹中，直到包含所有頂點。點并入生成樹中，直到包含所有頂點。建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于prim算法求最小生成樹算法詳見算法求最小生成樹算法詳見7.4.2節(jié)算法節(jié)算法7-6。 基本思想：基本思想： 將把圖將把圖G中的頂點分成兩部分：已在中的頂點分成兩部分：已在MST中的頂點集合中的頂點集合U，還未，還未在在MST的頂點集合的頂點集合VU。 在在VU里挑選出與里挑選出與U中某個頂點相距最近（即權值最?。┑哪莻€中某個頂點相距最近（即權值最小）的那個頂點，把這個頂點從頂點，把這個頂點從VU移到移到

33、U中。由此使得集合中。由此使得集合U不斷擴大，不斷擴大，VU不斷縮小，當不斷縮小，當U=V，VU=時，算法結束。時，算法結束。432、普里姆、普里姆(Prim)算法算法算法算法7-6 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于prim算法求最小生成樹。算法求最小生成樹。00 #include 01 #define MAX_INT 10000 /* 正無窮正無窮 */02 #define M MAX_INT 03 #define N 4 /* 頂點數(shù)頂點數(shù) */04 void print(int treeNN-1) 05 06 int i; 07 for(i=0;i N;i+) 08 printf(

34、%-8d%-8d%-8dn,treei0,treei1,treei2);09 getchar(); 10 442、普里姆、普里姆(Prim)算法算法算法算法7-6 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于prim算法求最小生成樹。算法求最小生成樹。11 int prim(int wNN,int v,int treeNN-1)12 13 int i,j,k,p,min,c;14 int lowcostN,closetN;15 for(i=0;i N;i+)16 17 closeti=v;18 lowcosti=wvi;19 20 c=0;21 p=0;452、普里姆、普里姆(Prim)算法算法算法算

35、法7-6 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于prim算法求最小生成樹。算法求最小生成樹。22 for(c=i=0;i N-1;i+)23 24 min=MAX_INT;25 for(j=0;j N;j+) /* 找連接生成樹所有邊的代價最小值找連接生成樹所有邊的代價最小值min */26 if(lowcostj!=0)&(lowcostj min)27 28 min=lowcostj;29 k=j;30 31 treep0=closetk; /* 對新加入生成樹的邊進行賦值對新加入生成樹的邊進行賦值 */32 treep1=k;33 treep2=min;34 p+;35 c=c+min;

36、/* 更新最小生成樹的代價更新最小生成樹的代價 */36 lowcostk=0;37 wkclosetk=0;462、普里姆、普里姆(Prim)算法算法算法算法7-6 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于prim算法求最小生成樹。算法求最小生成樹。38 for(j=0;j N;j+) /* 更新新加入生成樹頂點到生成樹外頂點的權值更新新加入生成樹頂點到生成樹外頂點的權值 */39 if(wkj!=0&wkj lowcostj)40 41 lowcostj=wkj;42 closetj=k;43 44 print(tree);45 46 return c; 47 472、普里姆、普里姆(Prim

37、)算法算法算法算法7-6 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于prim算法求最小生成樹。算法求最小生成樹。48 main()49 50 int M1NN=M,3,5,6, /* 4頂點的圖鄰接矩陣頂點的圖鄰接矩陣 */51 3,M,M,4, 52 5,M,M,7, 53 6,4,7,M; 54 int v=0,treeNN-1,weighttree,i; 55 for(i=0;iN;i+) 56 treei0=treei1=treei2=0; 57 weighttree=prim(M1,v,tree); 58 printf( nweighttree result = %dn,weighttre

38、e);59 print(tree);60 return;61 48練習：練習：v用普里姆算法（用普里姆算法（Prim）的思想，畫出該圖生成最小生成樹的過程。）的思想，畫出該圖生成最小生成樹的過程。49v適合：與頂點數(shù)有關，適合邊稠密的網(wǎng)絡。適合：與頂點數(shù)有關，適合邊稠密的網(wǎng)絡。v總的總的時間復雜度：時間復雜度：O(n2)7.4.2 最小生成樹最小生成樹33、克魯斯卡爾、克魯斯卡爾(Kruscal)算法算法原理：原理：所有邊按權排序，每次取最短邊，如不構成回路，則并入生所有邊按權排序，每次取最短邊，如不構成回路，則并入生成樹中，否則舍棄。直到并入了（成樹中，否則舍棄。直到并入了（n-1）條邊。）

39、條邊。具體步驟：具體步驟： 以圖以圖G的的E為基礎，按照各邊的權值，由小到大對它們進行挑選；為基礎，按照各邊的權值，由小到大對它們進行挑選； 如果挑選出來的邊的兩個頂點分屬如果挑選出來的邊的兩個頂點分屬S中的兩個不同的連通分量，中的兩個不同的連通分量，那么就將此邊從那么就將此邊從E中去除，并用此邊將中去除，并用此邊將S中的那兩個連通分量連接中的那兩個連通分量連接成一個連通分量，成為最小生成樹成一個連通分量，成為最小生成樹S中的一個新連通分量；中的一個新連通分量； 如果挑選出來的邊的兩個頂點屬于如果挑選出來的邊的兩個頂點屬于S中的同一個連通分量，那么中的同一個連通分量，那么就將其從就將其從E中舍

40、棄，重新再挑選中舍棄，重新再挑選； 不斷地實行（不斷地實行（1）（）（3）步，當）步，當S里只剩下一個連通分量時，算里只剩下一個連通分量時，算法終止。法終止。503、克魯斯卡爾、克魯斯卡爾(Kruscal)算法算法算法算法7-7 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于Kruscal算法求最小生成樹。算法求最小生成樹。00 #include01 #include02 #define M 2003 #define MAX 2004 typedef struct 05 06 int begin;07 int end;08 int weight;09 edge;10 typedef struct11 1

41、2 int adj;13 int weight;14 AdjMatrixMAXMAX;513、克魯斯卡爾、克魯斯卡爾(Kruscal)算法算法算法算法7-7 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于Kruscal算法求最小生成樹。算法求最小生成樹。15 typedef struct /* 定義一個圖類型定義一個圖類型 */16 17 AdjMatrix arc;18 int vexnum, arcnum;19 MGraph;20 MGraph *CreatGraph() /* 創(chuàng)建一個圖創(chuàng)建一個圖 */21 22 int i,j,n,m,w;23 MGraph *G;24 G = (MGraph*

42、)malloc(sizeof(MGraph);25 printf(Input vertex nember:); /* 輸入點數(shù)輸入點數(shù) */26 scanf(%d,&G-vexnum);27 printf(Input edges number:); /* 輸入邊數(shù)輸入邊數(shù) */28 scanf(%d,&G-arcnum);523、克魯斯卡爾、克魯斯卡爾(Kruscal)算法算法算法算法7-7 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于Kruscal算法求最小生成樹。算法求最小生成樹。29 for (i = 1; i vexnum; i+) /* 初始化圖初始化圖 */30 for ( j = 1;

43、j vexnum; j+)31 G-arcij.adj = G-arcji.adj = 0;32 for ( i = 1; i arcnum; i+) /* 輸入邊和權值輸入邊和權值 */33 34 printf(nInput edge(i j weight):);35 scanf(%d %d %d,&n,&m,&w);36 G-arcnm.weight=w;37 G-arcnm.adj = G-arcmn.adj = 1;38 533、克魯斯卡爾、克魯斯卡爾(Kruscal)算法算法算法算法7-7 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于Kruscal算法求最小生成樹。算法求最小生成樹。39 p

44、rintf(Adjacency Matrix :n);40 for ( i = 1; i vexnum; i+)41 42 for ( j = 1; j vexnum; j+)43 printf(%d ,G-arcij.weight);44 printf(n);45 46 return G;47 543、克魯斯卡爾、克魯斯卡爾(Kruscal)算法算法算法算法7-7 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于Kruscal算法求最小生成樹。算法求最小生成樹。48 void sort(edge edges,MGraph *G) /* 對權值進行排序對權值進行排序 */49 50 int i,j,tem

45、p;51 for ( i = 1; i arcnum; i+)52 53 for ( j = i + 1; j arcnum; j+)54 55 if (edgesi.weight edgesj.weight) /* 交換邊信息交換邊信息 */56 57 temp = edgesi.begin;58 edgesi.begin = edgesj.begin;59 edgesj.begin = temp;60 temp = edgesi.end;61 edgesi.end = edgesj.end;62 edgesj.end = temp;553、克魯斯卡爾、克魯斯卡爾(Kruscal)算法算法算

46、法算法7-7 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于Kruscal算法求最小生成樹。算法求最小生成樹。63 temp = edgesi.weight;64 edgesi.weight = edgesj.weight;65 edgesj.weight = temp;66 67 68 69 printf( Edges after sort:n);70 for (i = 1; i arcnum; i+)71 printf( weight: %dn, edgesi.begin, edgesi.end, edgesi.weight);72 printf(n);73 563、克魯斯卡爾、克魯斯卡爾(Krus

47、cal)算法算法算法算法7-7 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于Kruscal算法求最小生成樹。算法求最小生成樹。74 void MiniSpanTree(MGraph *G) /* 生成最小生成樹生成最小生成樹 */75 76 int i, j, n, m;77 int k = 1;78 int ringM;79 edge edgesM;80 for ( i = 1; i vexnum; i+)81 82 for (j = i + 1; j vexnum; j+)83 84 if (G-arcij.adj = 1)85 86 edgesk.begin = i;87 edgesk.end

48、= j;88 edgesk.weight = G-arcij.weight;89 k+;90 573、克魯斯卡爾、克魯斯卡爾(Kruscal)算法算法算法算法7-7 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于Kruscal算法求最小生成樹。算法求最小生成樹。93 sort(edges, G);94 for (i = 1; i arcnum; i+) /* 初始化每個頂點的連通分量編號初始化每個頂點的連通分量編號 */95 ringi = i;96 printf(Kruscal mintree:n);97 for (i = 1,k=1; k vexnum;i+) /* 核心部分核心部分 */98 99

49、 n = ringedgesi.begin; /* 取得起點連通分量編號取得起點連通分量編號 */100 m = ringedgesi.end; /* 取得終點連通分量編號取得終點連通分量編號 */101 if (n != m)102 103 for (j = 1; j arcnum; j+) /* 修改連通分量編號修改連通分量編號 */104 if (ringj = n)105 ringm = m;106 printf( weihet: %dn, edgesi.begin, edgesi.end, edgesi.weight);107 k=k+1;108 583、克魯斯卡爾、克魯斯卡爾(Kr

50、uscal)算法算法算法算法7-7 建立無向網(wǎng)絡并基于建立無向網(wǎng)絡并基于Kruscal算法求最小生成樹。算法求最小生成樹。111 void main()112 113 MGraph *G;114 G = CreatGraph(G);115 MiniSpanTree(G);116 59練習：練習：v用克魯斯卡爾算法（用克魯斯卡爾算法（Kruskal）的思想，畫出該圖生成最小生成）的思想，畫出該圖生成最小生成樹的過程。樹的過程。60v總的時間復雜度：總的時間復雜度：與邊排序算法有關與邊排序算法有關v適合：適合：與邊有關，適合邊稀疏的網(wǎng)絡。與邊有關，適合邊稀疏的網(wǎng)絡。3、克魯斯卡爾、克魯斯卡爾(Kr

51、uskal)算法算法2問題：如何判斷是否構成回路？問題：如何判斷是否構成回路？ 定義連通分量數(shù)組定義連通分量數(shù)組ringn，初始時各個，初始時各個ringi各不相同，找各不相同，找到邊（到邊（i，j）時，判斷）時，判斷ringi與與ringj是否相等：是否相等：相等：相等：說明說明i，j在同一個連通分量，舍棄；在同一個連通分量，舍棄；不相等：不相等： i，j在不同連通分量，邊（在不同連通分量，邊（i，j）并入生成樹中，并把所有）并入生成樹中，并把所有與與ringi相等的相等的ring值改為值改為ringj。617.5 最短路徑最短路徑v問題的提出：問題的提出： A、B有若干路徑相通，如何找尋一

52、代價最小的路徑？有若干路徑相通，如何找尋一代價最小的路徑？ v例子：例子：627.5 最短路徑最短路徑21、單源最短路徑、單源最短路徑63Dijkstra算法具體步驟：算法具體步驟： 初始時，集合初始時，集合U里只含一個源點里只含一個源點u，集合，集合VU里是圖中除里是圖中除u以外的以外的所有頂點，所有頂點，u到其它頂點的距離是它們間弧的權值；到其它頂點的距離是它們間弧的權值； 從從VU里挑選出一個與源點里挑選出一個與源點u的距離為最小的頂點的距離為最小的頂點v，把它從，把它從VU移到移到U里，然后對里，然后對VU里剩下的頂點（比如里剩下的頂點（比如k）到源點）到源點u的距離進的距離進行修改，

53、方法是若圖中存在?。ㄐ行薷?，方法是若圖中存在?。╲, k），且該弧的權值加上），且該弧的權值加上u到到v的距離之和小于原先的距離之和小于原先u到到k的距離時，就用此的距離時，就用此“和和”取代原先取代原先u到到k的距離，否則原先的距離，否則原先u到到k的距離保持不變；的距離保持不變； 逐次對集合逐次對集合VU實行操作（實行操作（2），當），當VU為空時，算法結束，所求為空時，算法結束，所求得的得的u到各頂點的距離即是源點到其它頂點的最短路徑長度到各頂點的距離即是源點到其它頂點的最短路徑長度。1、單源最短路徑、單源最短路徑算法算法7-8求單源最短路徑的求單源最短路徑的Dijkstra算法算法64

54、00 #include01 #include02 #define MAX 10000 /* 正無窮正無窮 */03 #define n 6 /* 頂點數(shù)頂點數(shù) */04 void Dijkstra(int v,int costn+1n+1,int distn+1,int prevn+1)05 06 int i,j,k,temp=MAX;07 int u,newdist,min;08 int sn+1=0 ; /* 作為標記定義具有最短路徑的頂點子集作為標記定義具有最短路徑的頂點子集s */09 sv = 1; /* 源頂點標記為已具有最短路徑源頂點標記為已具有最短路徑 */10 prevv=v

55、; /* 源頂點的前驅即為本身源頂點的前驅即為本身 */1、單源最短路徑、單源最短路徑算法算法7-8求單源最短路徑的求單源最短路徑的Dijkstra算法算法6511 for (i = 1; i = n; i+) /* 初始化最小路徑代價初始化最小路徑代價 */12 13 disti = costvi; 14 previ=v;15 16 u=v; /* u為中轉頂點為中轉頂點 */17 for (i = 1; i n; i+)18 19 for (j = 1; j distu+costuj)22 23 distj=distu+costuj;24 prevj=u;25 26 1、單源最短路徑、單源

56、最短路徑算法算法7-8求單源最短路徑的求單源最短路徑的Dijkstra算法算法6627 min=MAX;28 for (j = 1; j = n; j+)29 30 if (sj=0) & (distj = 0; j-) /* 逆向輸出路徑數(shù)組逆向輸出路徑數(shù)組way */52 printf(%d - ,wayj);53 printf(%dn,u);54 1、單源最短路徑、單源最短路徑算法算法7-8求單源最短路徑的求單源最短路徑的Dijkstra算法算法6855 void main()56 57 int i,j,k,w;58 int v,u,arcnum;59 int costn+1n+1=0,

57、0,0,0,0,0,0,60 0,0,10,MAX,5,MAX,MAX, /* 6頂點的網(wǎng)絡鄰接矩陣頂點的網(wǎng)絡鄰接矩陣 */61 0,10,0,1,7,MAX,MAX,62 0,MAX,1,0,MAX,MAX,5,63 0,5,7,MAX,0,2,6,64 0,MAX,MAX,MAX,2,0,3,65 0,MAX,MAX,5,6,3,0; 66 int prevn+1; /* 定義頂點路徑的前驅頂點定義頂點路徑的前驅頂點 */67 int distn+1; /* 最短路徑代價最短路徑代價 */68 printf( The number of vertexes is %d!n,n);1、單源最短

58、路徑、單源最短路徑算法算法7-8求單源最短路徑的求單源最短路徑的Dijkstra算法算法6969 printf(please input the source node: );70 scanf(%d,&v);71 Dijkstra(v, cost,dist,prev);72 printf(n*have confirm the best path*n);73 for(i = 1; i = n ; i+)74 75 if(i!=v)76 77 printf(nThe lowest cost is %d, ,v,i,disti);78 ShowPath(v,i, prev);79 80 81 例子：

59、例子：v利用利用Dijkstra算法，求算法，求下下圖源點圖源點v1到其它頂點的最短路徑到其它頂點的最短路徑。70例子（續(xù)）：例子（續(xù)）：v基于基于Dijkstra算法最短路徑計算算法最短路徑計算過程：過程：717.5 最短路徑最短路徑32、頂點對間最短路徑、頂點對間最短路徑72已知有向網(wǎng)圖已知有向網(wǎng)圖G=（V，E），求其中任意一對頂點之間的最短路徑。），求其中任意一對頂點之間的最短路徑。Floyd算法具體步驟：算法具體步驟： 初始時，把鄰接矩陣記為初始時，把鄰接矩陣記為D(0)，它的元素記錄了圖中各弧的權值；，它的元素記錄了圖中各弧的權值； 逐次把頂點逐次把頂點vk(1kn)插入到矩陣所有元

60、素中去進行探測，如果矩插入到矩陣所有元素中去進行探測，如果矩陣原先有路徑（陣原先有路徑（vi, vj）(i j)，現(xiàn)在插入，現(xiàn)在插入vk后，有路徑（后，有路徑（vi, vk）和）和（vk, vj），且：），且：D (vi, vk) + D (vk, vj) D (vi, vj)那么，就用那么，就用D (vi, vk) + D (vk, vj)代替代替D (vi, vj)，于是形成一個新的矩，于是形成一個新的矩陣陣D(k)； 在完成在完成n次探測后，矩陣次探測后，矩陣D(n)里記錄了各頂點對之間的最短路徑。里記錄了各頂點對之間的最短路徑。例子：例子：v利用利用Floyd算法，求下圖中各頂點對的最