1、第7章 圖本章主題：圖的基本概念、圖的存儲結(jié)構(gòu)和圖的常用算法 教學目的：教學重點：圖的各種存儲方式及其運算 教學難點：圖結(jié)構(gòu)存儲方式的選擇，幾種經(jīng)典圖算法的實現(xiàn) 本章內(nèi)容：圖的基本概念 圖的存儲結(jié)構(gòu) 圖的遍歷 最小生成樹 最短路徑 2022/8/181 本章主要介紹圖的基本概念、圖的存儲結(jié)構(gòu)和有關(guān)圖的一些常用算法。通過本章學習，讀者應該： 1) 了解圖的定義和術(shù)語 2) 掌握圖的各種存儲結(jié)構(gòu) 3) 掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷算法 4) 理解最小生成樹、最短路徑、拓撲排序、關(guān)鍵路徑等圖的常用算法 本章學習導讀 2022/8/182 圖（Graph）是一種較線性表和樹更為復雜的非線性結(jié)

2、構(gòu)。是對結(jié)點的前趨和后繼個數(shù)不加限制的數(shù)據(jù)結(jié)構(gòu)，用來描述元素之間“多對多”的關(guān)系。 在線性結(jié)構(gòu)中，結(jié)點之間的關(guān)系是線性關(guān)系，除開始結(jié)點和 終端結(jié)點外，每個結(jié)點只有一個直接前趨和直接后繼。 在樹形結(jié)構(gòu)中，結(jié)點之間的關(guān)系實質(zhì)上是層次關(guān)系，同層上的每個結(jié)點可以和下一層的零個或多個結(jié)點（即孩子）相關(guān)，但只能和上一層的一個結(jié)點（即雙親）相關(guān)（根結(jié)點除外）。 在圖結(jié)構(gòu)中，對結(jié)點（圖中常稱為頂點）的前趨和后繼個數(shù)不加限制的，即結(jié)點之間的關(guān)系是任意的。 由此，圖的應用極為廣泛，特別是近年來的迅速發(fā)展，已滲透到諸如語言學、邏輯學、物理、化學、電訊工程、計算機科學以及數(shù)學的其它分支中。2022/8/183 7.

3、1 .1 圖的定義 圖是由一個頂點集 V 和一個弧集 R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V, R ) V = x | x 某個數(shù)據(jù)對象 ， 是頂點的有窮非空集合； R邊的有限集合 R = (x, y) | x, y V 無向圖 或 R = | x, y V & Path (x, y)有向圖 是頂點之間關(guān)系的有窮集合，也叫做邊(edge)集合。Path (x, y)表示從 x 到 y 的一條單向通路, 它是有方向的。x弧尾，y弧頭。7.1 圖及其基本運算 2022/8/184有向圖與無向圖 有向圖中：邊用表示，且x與y是有序的。 a. 有向圖中的邊稱為“弧” b. x弧尾或初始點 y弧頭或終

4、端點無向圖：邊用(x, y) 表示，且頂x與 y是無序的。完全圖 在具有n 個頂點的有向圖中，最大弧數(shù)為 n(n-1) 在具有n 個頂點的無向圖中，最大邊數(shù)為 n(n-1)/2頂點的度無向圖：與該頂點相關(guān)的邊的數(shù)目有向圖： 入度ID(v) ：以該頂點為頭的弧的數(shù)目 出度OD(v) ：以該頂點為尾頭的弧的數(shù)目 在有向圖中, 頂點的度等于該頂點的入度與出度之和。2022/8/185圖7-1 無向圖和有向圖 2022/8/186 在圖7-1中，圖(a)為無向圖，其中G1的頂點集合和邊集合分別為：V(G1)=1，2，3，4，5，6，7，E(G1)=(1，2)，(l，3)，(2，3)，(3，4)，(3，

5、5)，(5，6)，(5，7)。 圖(c)為有向圖，其中G3的頂點集合和弧集合分別為V(G3)=1，2，3，4，5，6，E(G3)=， 2022/8/1877.1.2 圖的基本術(shù)語1 頂點的度 與頂點v相關(guān)的邊或弧的數(shù)目稱作頂點v的度。在有向圖中，一個頂點依附的弧頭數(shù)目，稱為該頂點的入度。一個頂點依附的弧尾數(shù)目，稱為該頂點的出度，某個頂點的入度和出度之和稱為該頂點的度。 例如圖7-1中，無向圖G1中頂點3的度為4，頂點5的度為3。 例如在圖7-1中，有向圖G3中頂點1的出度OD (1)=3，入度ID (1)=1，其度TD (1)=4。 2022/8/1882路徑和回路 在無向圖G中，若存在一個頂

6、點序列Vp ,Vi1，Vi2，Vin，Vq, 使得（Vp,Vi1）,(Vi1,Vi2),.，(Vin,Vq)均屬于E（G），則稱頂點Vp到Vq存在一條路徑。 若一條路徑上除起點和終點可以相同外，其余頂點均不相同，則稱此路徑為簡單路徑。 起點和終點相同的路徑稱為回路； 簡單路徑組成的回路稱為簡單回路。 路徑長度 路徑上經(jīng)過的邊的數(shù)目稱為該路徑的路徑長度。非帶權(quán)圖的路徑長度是指此路徑上邊/弧的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊/弧的權(quán)之和。2022/8/1892022/8/18103.邊和弧邊: 無向圖中頂點的偶對，寫成（Vx，Vy）或（Vy，Vx）?；? 有向圖中頂點的偶對,Vx,Vy表示從V

7、x到Vy。弧頭: 弧的終點弧尾: 弧的起點弧 Vx，Vy 弧尾Vx 弧頭Vy2022/8/18114子圖 設(shè)有兩個圖 G(V, E) 和 G(V, E)。若 V V 且 EE, 則稱 圖G 是 圖G 的子圖。2022/8/181212345(a)12345(b)1245(c)145(d)22022/8/18135連通性 在無向圖中, 若從頂點v1到頂點v2有路徑, 則稱頂點v1與v2是連通的。如果圖中任意一對頂點vi和vj（vi，vjV）都是連通的, 則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。 6 強連通圖與強連通分量 在有向圖中, 若對于每一對頂點vi和vj, 都存在一條從vi到

8、vj和從vj到vi的路徑, 則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。 2022/8/18147網(wǎng)絡(luò)權(quán) 某些圖的邊或弧具有與它相關(guān)的數(shù), 稱之為權(quán)。權(quán)可以代表一個頂點到另一個頂點的距離，耗費等。網(wǎng)絡(luò) 這種帶權(quán)連通圖一般稱為網(wǎng)絡(luò)。如圖7-4所示。 2022/8/18158生成樹、生成森林生成樹 一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-1條邊。 生成樹是對連通圖而言的 是連同圖的極小連同子圖 包含圖中的所有頂點 有且僅有n-1條邊 非連通圖的生成樹則組成一個生成森林。若圖中有n個頂點，m個連通分量，則生成森林中有n-m條邊。2022/8/18169鄰接點

9、頂點: 圖中的結(jié)點 鄰接點:無向圖中，若邊(x,y)E，兩頂點之間有條邊，則兩頂點互 為鄰接點。 x y ( x ,y )有向圖中，若弧(x,y)E，從x到y(tǒng)有一條弧，則y是x的鄰接點， 但x不是y的鄰接點。 x y VxVyx、y互為鄰接點VxVyy是x的鄰接點2022/8/18177.1.3 圖的基本運算 圖的基本運算:見P1562022/8/18187.2.1 鄰接矩陣 鄰接矩陣(Adjacency Matrix)是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣。7.2 圖的存儲結(jié)構(gòu) 無向圖的鄰接矩陣是以主對角線對稱的，有向圖的鄰接矩

10、陣可能是不對稱的。 在有向圖中： 第 i 行 1 的個數(shù)就是頂點 i 的出度， 第 j 列 1 的個數(shù)就是頂點 j 的入度。 在無向圖中, 第 i 行 (列) 1 的個數(shù)就是頂點i 的度。2022/8/1819圖7-6 有向圖及其鄰接矩陣 圖7-5 無向圖及其鄰接矩陣 2022/8/1820 對于無向圖，（vi，vj）和（vj，vi）表示同一條邊，因此，在鄰接矩陣中Aij=Aji。 無向圖的鄰接矩陣是（關(guān)于主對角線）對稱矩陣，可用主對角線以上（或以下）的部分表示。 對有向圖，弧和表示方向不同的兩條弧，Aij和Aji表示不同的弧，所以有向圖的鄰接矩陣一般不具有對稱性。 鄰接矩陣表示法適合于以頂點

11、為主的運算。 2022/8/1821 對于有向圖，頂點vi的出度OD (vi)等于鄰接矩陣第i行元素之和；頂點vi的入度ID (vi)等于鄰接矩陣第i列元素之和，即 ： 對于無向圖，頂點vi的度等于鄰接矩陣第i行的元素之和，即： OD (vi)= ID (vi)= TD（vi）= 對于帶權(quán)圖的鄰接矩陣，定義為：2022/8/1822 頂點表: 一個記錄各個頂點信息的一維數(shù)組， 鄰接矩陣：一個表示各個頂點之間的關(guān)系（邊或?。┑亩S數(shù)組。 使用鄰接矩陣存儲結(jié)構(gòu)，可用一維數(shù)組表示圖的頂點集合，用二維數(shù)組表示圖的頂點之間關(guān)系（邊或?。┑募希瑪?shù)據(jù)類型定義如下： #define MAX_VERTEX_N

12、UM 20 /最大頂點數(shù)typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /鄰接矩陣類型typedef struct VertexType vexsMAX_VERTEX_NUM; /頂點表AdjMatrix arcs; /鄰接矩陣int vexnum,arcnum; /圖的頂點數(shù)和弧數(shù) MGraph; 由于一般圖的邊或弧較少，其鄰接矩陣的非零元素較少，屬稀疏矩陣，因此會造成一定存儲空間的浪費。 2022/8/18237.2.2 鄰接表 圖的鏈式存儲結(jié)構(gòu) 1) 為每個頂點建立一個單鏈表， 2) 第i個單鏈表中包含頂點Vi的所有鄰接頂點。 鄰接表

13、是圖的一種鏈式存儲結(jié)構(gòu)。類似于樹的孩子鏈表表示法。在鄰接表中為圖中每個頂點建立一個單鏈表，用單鏈表中的一個結(jié)點表示依附于該頂點的一條邊（或表示以該頂點為弧尾的一條弧），稱為邊（或?。┙Y(jié)點。 2022/8/1824 把同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，鏈表的每一個結(jié)點代表一條邊，叫做表結(jié)點（邊結(jié)點），鄰接點域adjvex保存與該邊相關(guān)聯(lián)的另一頂點的頂點下標 ， 鏈域nextarc存放指向同一鏈表中下一個表結(jié)點的指針 ，數(shù)據(jù)域info存放邊的權(quán)。邊鏈表的表頭指針存放在頭結(jié)點中。頭結(jié)點以順序結(jié)構(gòu)存儲，其數(shù)據(jù)域data存放頂點信息，鏈域firstarc指向鏈表中第一個頂點。2022/8/1825

14、 帶權(quán)圖的邊結(jié)點中info保存該邊上的權(quán)值 。 頂點 Vi 的邊鏈表的頭結(jié)點存放在下標為 i 的頂點數(shù)組中。 在鄰接表的邊鏈表中，各個邊結(jié)點的鏈入順序任意，視邊結(jié)點輸入次序而定。 2022/8/1826有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第 i 個鏈表中結(jié)點的個數(shù)是頂點Vi的出度。在有向圖的逆鄰接表中，第 i 個鏈表中結(jié)點的個數(shù)是頂點Vi 的入度。2022/8/1827 圖7-7 為圖7-6 (a)的的鄰接表和逆鄰接表圖7-7 有向圖的鄰接表和逆鄰接表7-6 (a)(b)41320212310123(c)143213003201232022/8/1828網(wǎng)絡(luò) (帶權(quán)圖) 的鄰接表202

15、2/8/1829存儲表示typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;int info;ArcNode; /邊結(jié)點類型typedef struct VNodeVertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM; typedef structAdjList vertices; /鄰接表int vexnum,arcnum;ALGraph;2022/8/18307.2.3 十字鏈表 十字鏈表 (Orthogonal List)是有向圖的另一種鏈式存儲結(jié)構(gòu)?？煽醋?/p>

16、是將有向圖的鄰接表和逆鄰接表結(jié)合的一種鏈表。 在十字鏈表中，為每個頂點vi設(shè)置一個結(jié)點，它包含數(shù)據(jù)域data和兩個鏈域firstout、firstin，稱為頂點結(jié)點。數(shù)據(jù)域data用于存放頂點vi的有關(guān)信息；鏈域firstin指向以頂點vi為弧頭的第一個弧結(jié)點；鏈域firstout指向以頂點vi為弧尾的第一個弧結(jié)點。 弧結(jié)點包括四個域：尾域tailvex、頭域headvex，鏈域hlink和tlink。 hlink指向弧頭相同的下一條弧，tlink指向弧尾相同的下一條弧；data頂點信息，firstin以該頂點為頭的第一個弧結(jié)點，firstout以該結(jié)點為尾的第一個弧結(jié)點headvextail

17、vexhlinktlinkinfofirstindatafirstout頂點結(jié)點弧結(jié)點2022/8/1831圖7-8 十字鏈表 圖7-8為圖7-6 (a)有向圖的十字鏈表。 采用十字鏈表表示有向圖，很容易找到以頂點vi為弧尾的弧和以頂點vi為弧頭的弧，因此頂點的出度、入度都很容易求得。 2022/8/1832十字鏈表的數(shù)據(jù)類型定義如下： #define MAXV typedef struct /弧結(jié)點 int tailvex,headvex; /弧尾和弧頭頂點位置 struct ArcNode *hlink,*tlink; /弧頭相同和弧尾相同的弧的鏈域ArcNode;typedef stru

18、ct /頂點結(jié)點 VertexType data; /頂點信息 ArcNode *firstin,*firstout; /分別指向該頂點的第一條入弧和出弧VexNode;2022/8/18337.2.4 鄰接多重表 鄰接多重表是無向圖的另一種鏈式存儲結(jié)構(gòu)。在鄰接多重表中設(shè)置一個邊結(jié)點表示圖中的一條邊。邊結(jié)點包含五個域，結(jié)構(gòu)如下所示： 其中：mark 域 標志域，用于對該邊進行標記； ivex 域 存放該邊依附的一個頂點vi的位置信息； ilink 域 該鏈域指向依附于頂點vi的另一條邊的邊結(jié)點； jvex 域 存放該邊依附的另一個頂點vj的位置信息； jlink 域 該鏈域指向依附于頂點vj的

19、另一條邊的邊結(jié)點。 鄰接多重表為每個頂點設(shè)置一個結(jié)點，其結(jié)構(gòu)如下： 2022/8/1834圖7-9 鄰接多重表 圖7-9為圖7-5 (a)無向圖的鄰接多重表。 由鄰接多重表可以看出，表示邊（vi，vj）的邊結(jié)點通過鏈域ilink和jlink鏈入了頂點vi和頂點vj的兩個鏈表中，實現(xiàn)了用一個邊結(jié)點表示一個邊的目的，克服了在鄰接表中用兩個邊結(jié)點表示一個邊的缺點。因此鄰接多重表是無向圖的一種很有效的存儲結(jié)構(gòu)。 2022/8/1835鄰接多重表的結(jié)點數(shù)據(jù)類型定義如下： #define MAXV typedef struct /邊結(jié)點類型 int mark; /訪問標識 int ivex,jvex; /

20、該邊的兩個頂點位置信息 struct Enode *ilink,*jlink; /分別指向依附這兩個頂點的下一條邊Enode;typedef struct /頂點結(jié)點類型 VertexType data; /頂點數(shù)據(jù)域 ENode *firstedge; /指向第一條依附該頂點的邊Vnode; 2022/8/18367.3 圖的遍歷 和樹的遍歷相似，若從圖中某頂點出發(fā)訪遍圖中每個頂點，且每個頂點僅訪問一次，此過程稱為圖的遍歷。 (Traversing Graph)。 但是，在圖中有回路，從圖中某一頂點出發(fā)訪問圖中其它頂點時，可能又會回到出發(fā)點，而圖中或許還有頂點沒有訪問到，因此，圖的遍歷較樹的

21、遍歷更復雜。 圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關(guān)鍵路徑等算法的基礎(chǔ)。 圖的遍歷順序有兩種：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。對每種搜索順序，訪問各頂點的順序也不是唯一的。 2022/8/18377.3.1 深度優(yōu)先搜索（DFS）1 深度優(yōu)先搜索思想 深度優(yōu)先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點均未被訪問過，在G中任選一個頂點i作為遍歷的初始點，則深度優(yōu)先搜索遞歸調(diào)用包含以下操作：（1）訪問搜索到的未被訪問的鄰接點；（2）將此頂點的visited數(shù)組元素值置1；（3）搜索該頂點的未被訪問的鄰接點，若該鄰接點存在，則從此鄰接點開始進行同樣的訪問和搜索

22、。 深度優(yōu)先搜索DFS可描述為：（1）訪問v0頂點；（2）置 visitedv0=1；（3）搜索v0未被訪問的鄰接點w，若存在鄰接點w，則DFS(w)。 2022/8/1838 遍歷過程： DFS 在訪問圖中某一起始頂點 v 后，由 v 出發(fā)，訪問它的任一鄰接頂點 w1；再從 w1 出發(fā)，訪問與 w1鄰 接但還沒有訪問過的頂點 w2；然后再從 w2 出發(fā)，進行類似的訪問， 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。 接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退

23、回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。2022/8/1839 深度優(yōu)先搜索的示例 圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。 為了避免重復訪問，可設(shè)置一個標志頂點是否被訪問過的輔助數(shù)組 visited ，它的初始狀態(tài)為 0，在圖的遍歷過程中，一旦某一個頂點 i 被訪問，就立即讓 visited i 為 1，防止它被多次訪問。2022/8/1840 對上圖，深度優(yōu)先搜索遍歷的順序（之一）為： v1 v2v4 v8 v5v6v3v7。 圖7-10 深度優(yōu)先搜索 2022/8/1841深度優(yōu)先搜索算

24、法：int visitedMAX_VERTEX_NUM; void DFS(ALGraph G, int v) ArcNode *p; printf(%c,G.verticesv.data); visitedv=1; p=G.verticesv.firstarc; while (p) if (!visitedp-adjvex) DFS(G,p-adjvex); p=p-nextarc; /從第v個頂點出發(fā)DFS2022/8/1842整個圖的DFS遍歷void DFSTraverse(ALGraph G) for (int v=0;vG.vexnum;+v) visitedv=0; for (v

25、=0;vG.vexnum;+v) if (!visitedv) DFS(G,v); 對于連通圖，從一個頂點出發(fā)，調(diào)用DFS函數(shù)即可將所有頂點都遍歷到。2022/8/18437.3.2 廣度優(yōu)先搜索（BFS）1 廣度優(yōu)先搜索思想 廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷。 對于無向連通圖，廣度優(yōu)先搜索是從圖的某個頂點v0出發(fā)，在訪問v0之后，依次搜索訪問v0的各個未被訪問過的鄰接點w1，w2，。然后順序搜索訪問w1的各未被訪問過的鄰接點，w2的各未被訪問過的鄰接點，。即從v0開始，由近至遠，按層次依次訪問與v0有路徑相通且路徑長度分別為1，2，的頂點，直至連通圖中所有頂點都被訪問一次。 廣度優(yōu)先搜索

26、的順序不是唯一的，例如圖7-10 (a) 連通圖的廣度優(yōu)先搜索遍歷順序可為v1，v2，v3，v4，v5，v6，v7，v8 也可為v1，v3，v2，v7，v6，v5，v4，v8。 2022/8/18441 廣度優(yōu)先搜索思想 設(shè)圖G的初態(tài)是所有頂點均未訪問，在G 中任選一頂點i作為初始點，則廣度優(yōu)先搜索的基本思想是： （1）從圖中的某個頂點V出發(fā)，訪問之；并將其訪問標志置為已被訪問，即visitedi=1；（2）依次訪問頂點V的各個未被訪問過的鄰接 點，將V的全部鄰接點都訪問到；（3）分別從這些鄰接點出發(fā)，依次訪問它們的未被訪問過的鄰接點，并使“先被訪問的頂 點的鄰接點”先于“后被訪問的頂點的鄰接

27、 點”被訪問，直到圖中所有已被訪問過的頂 點的鄰接點都被訪問到。 依此類推，直到圖中所有頂點都被訪問完為止 。2022/8/1845 廣度優(yōu)先搜索在搜索訪問一層時，需要記住已被訪問的頂點，以便在訪問下層頂點時，從已被訪問的頂點出發(fā)搜索訪問其鄰接點。所以在廣度優(yōu)先搜索中需要設(shè)置一個隊列Queue，使已被訪問的頂點順序由隊尾進入隊列。在搜索訪問下層頂點時，先從隊首取出一個已被訪問的上層頂點，再從該頂點出發(fā)搜索訪問它的各個鄰接點。 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先搜索的示例2022/8/18467.4 最小生成樹 1. 生成樹 在一個無向連通圖G中，其所有頂點和遍歷該圖經(jīng)過的所有邊所構(gòu)成的子

28、圖G 稱做圖G的生成樹。一個圖可以有多個生成樹，從不同的頂點出發(fā)，采用不同的遍歷順序，遍歷時所經(jīng)過的邊也就不同，例如圖7-12的(b) 和(c) 為圖7-12 (a) 的兩棵生成樹。其中 (b) 是通過DFS得到的，稱為深度優(yōu)先生成樹；(c) 是通過BFS得到的，稱為廣度優(yōu)先生成樹。 圖7-12 生成樹 2022/8/1847 按照生成樹的定義，n 個頂點的連通網(wǎng)絡(luò)的生成樹有 n 個頂點、n-1 條邊。而所有包含n-1 條邊及n個頂點的連通圖都是無回路的樹，所以生成樹是連通圖中的極小連通子圖. 由于使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。如深度優(yōu)

29、先生成樹、廣度優(yōu)先生成樹 在圖論中，常常將樹定義為一個無回路連通圖。 對于一個帶權(quán)的無向連通圖，其每個生成樹所有邊上的權(quán)值之和可能不同，我們把所有邊上權(quán)值之和最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹有很多實際應用。例如，通訊線路鋪設(shè)造價最優(yōu)問題就是一個最小生成樹問題。2022/8/1848 假設(shè)把n個城市看作圖的n個頂點，邊表示兩個城市之間的線路，每條邊上的權(quán)值表示鋪設(shè)該線路所需造價。鋪設(shè)線路連接n個城市，但不形成回路，這實際上就是圖的生成樹，而以最少的線路鋪設(shè)造價連接各個城市，即求線路鋪設(shè)造價最優(yōu)問題，實際上就是在圖的生成樹中選擇權(quán)值之和最小的生成樹。構(gòu)造最小生成樹的算法有很多，下面

30、分別介紹克魯斯卡爾(Kruskal)算法和普里姆(Prim)算法。 7.4.1 克魯斯卡爾(Kruskal)算法 克魯斯卡爾算法是一種按權(quán)值遞增的次序選擇合適的邊來構(gòu)造最小生成樹的方法。2022/8/1849算法的基本思想： 在圖中任取一個頂點K作為開始點，令U=k，W=V-U，其中V為圖中所有頂點集，然后找一個頂點在U中，另一個頂點在W中的邊中最短的一條，找到后，將該邊作為最小生成樹的樹邊保存起來，并將該邊頂點全部加入U集合中，并從W中刪去這些頂點，然后重新調(diào)整U中頂點到W中頂點的距離, 使之保持最小，再重復此過程，直到W為空集止。 假設(shè)G=（V，E）是一個具有n個頂點的帶權(quán)無向連通圖，T=

31、 (U，TE)是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，則構(gòu)造最小生成樹的過程如下：(1) 置U的初值等于V，TE的初值為空集；(2) 按權(quán)值從小到大的順序依次選取圖G中的邊，若選取的邊未使生成樹T形成回路，則加入TE；若選取的邊使生成樹T形成回路，則將其舍棄。循環(huán)執(zhí)行(2)，直到TE中包含(n-1)條邊為止。 2022/8/1850應用克魯斯卡爾算法構(gòu)造最小生成樹的過程:2022/8/18517.5 最短路徑 交通網(wǎng)絡(luò)中常常提出這樣的問題：從甲地到乙地之間是否有公路連通? 在有多條通路的情況下，哪一條路最短? 交通網(wǎng)絡(luò)可用帶權(quán)圖來表示。頂點表示城市名稱，邊表示兩個城市有路連通，邊

32、上權(quán)值可表示兩城市之間的距離、交通費或途中所花費的時間等。求兩個頂點之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。 另外，若兩個頂點之間沒有邊，但有可能有間接通路(從其它頂點達到)。 路徑上的開始頂點(出發(fā)點)稱為源點，路徑上的最后一個頂點稱為終點，并假定討論的權(quán)值不能為負數(shù)。2022/8/1852最短路徑： 如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。 對于帶權(quán)的圖，通常把一條路徑上所經(jīng)過邊或弧上的權(quán)值之和定義為該路徑的路徑長度。從一個頂點到另一個頂點可能存在著多條路徑，把路徑長

33、度最短的那條路徑稱為最短路徑，其路徑長度稱為最短路徑長度。無權(quán)圖實際上是有權(quán)圖的一種特例，我們可以把無權(quán)圖的每條邊或弧的權(quán)值看成是l，每條路徑上所經(jīng)過的邊或弧數(shù)即為路徑長度。本章討論兩種最常見的最短路徑問題。 2022/8/1853問題解法 邊上權(quán)值非負情形的單源最短路徑問題 Dijkstra算法所有頂點之間的最短路徑 Floyd算法邊上權(quán)值非負情形的單源最短路徑問題 問題的提法： 給定一個帶權(quán)有向圖D與源點v，求從v到D中其它頂點的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v