1、1 引言引言 圖論起源于圖論起源于1818世紀。第一篇圖論論文是瑞士世紀。第一篇圖論論文是瑞士數學家歐拉于數學家歐拉于1736 1736 年發表的年發表的“哥尼斯堡的七座哥尼斯堡的七座橋橋”。 圖論中所謂的圖論中所謂的“圖圖”是指是指某類具體事物和這某類具體事物和這些事物之間的聯系些事物之間的聯系。如果我們用。如果我們用點點表示這些表示這些具體具體事物事物，用連接兩點的，用連接兩點的線段線段（直的或曲的）表示兩（直的或曲的）表示兩個個事物的特定的聯系事物的特定的聯系，就得到了描述這個，就得到了描述這個“圖圖”的幾何形象。圖論為任何一個包含了一種二元關的幾何形象。圖論為任何一個包含了一種二元關系

2、的離散系統提供了一個數學模型，借助于圖論系的離散系統提供了一個數學模型，借助于圖論的概念、理論和方法，可以對該模型求解。的概念、理論和方法，可以對該模型求解。 哥尼斯堡七橋問題就是一個典型的例子。在哥尼斯堡七橋問題就是一個典型的例子。在哥尼斯堡有七座橋將普萊格爾河中的兩個島及島哥尼斯堡有七座橋將普萊格爾河中的兩個島及島與河岸聯結起來。問題是與河岸聯結起來。問題是要從這四塊陸地中的任要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點。何一塊開始通過每一座橋正好一次，再回到起點。 12 當然可以通過試驗去嘗試解決這個問題，但當然可以通過試驗去嘗試解決這個問題，但該城居民的任何嘗試均未成

3、功。該城居民的任何嘗試均未成功。 歐拉為了解決這個問題，采用了建立數學模歐拉為了解決這個問題，采用了建立數學模型的方法。他將每一塊陸地用一個點來代替，將型的方法。他將每一塊陸地用一個點來代替，將每一座橋用連接相應兩點的一條線來代替，從而每一座橋用連接相應兩點的一條線來代替，從而得到一個有得到一個有四個四個“點點”，七條，七條“線線”的的“圖圖”。問題成為問題成為從任一點出發一筆畫出七條線再回到起從任一點出發一筆畫出七條線再回到起點點。歐拉考察了一般一筆畫的結構特點，給出了。歐拉考察了一般一筆畫的結構特點，給出了一筆畫的一個判定法則一筆畫的一個判定法則：這個圖是連通的，且每這個圖是連通的，且每個

4、點都與偶數線相關聯，個點都與偶數線相關聯，將這個判定法則應用于將這個判定法則應用于七橋問題，得到了七橋問題，得到了“不可能走通不可能走通”的結果，不但的結果，不但徹底解決了這個問題，而且開創了圖論研究的先徹底解決了這個問題，而且開創了圖論研究的先河。河。3 我們首先通過一些例子來了解網絡優化問題。我們首先通過一些例子來了解網絡優化問題。例例1 1 最短路問題最短路問題（SPPSPPshortest path problemshortest path problem） 一名貨柜車司機奉命在最短的時間內將一車貨物一名貨柜車司機奉命在最短的時間內將一車貨物從甲地運往乙地。從甲地到乙地的公路網縱橫交從

5、甲地運往乙地。從甲地到乙地的公路網縱橫交錯，因此有多種行車路線，這名司機應選擇哪條錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨柜車的運行速度是恒定的，那么線路呢？假設貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條從甲地到乙地的最這一問題相當于需要找到一條從甲地到乙地的最短路。短路。例例2 2 公路連接問題公路連接問題 某一地區有若干個主要城市，現準備修建高速公某一地區有若干個主要城市，現準備修建高速公路把這些城市連接起來，使得從其中任何一個城路把這些城市連接起來，使得從其中任何一個城市都可以經高速公路直接或間接到達另一個城市。市都可以經高速公路直接或間接到達另一個城市。假

6、定已經知道了任意兩個城市之間修建高速公路假定已經知道了任意兩個城市之間修建高速公路的成本，那么應如何決定在哪些城市間修建高速的成本，那么應如何決定在哪些城市間修建高速公路，使得總成本最小？公路，使得總成本最小？4例例3 3 指派問題指派問題（assignment problemassignment problem） 一家公司經理準備安排名員工去完成項任務，一家公司經理準備安排名員工去完成項任務， 每人一項。由于各員工的特點不同，不同的員每人一項。由于各員工的特點不同，不同的員 工去完成同一項任務時所獲得的回報是不同的。工去完成同一項任務時所獲得的回報是不同的。 如何分配工作方案可以使總回報最大

7、？如何分配工作方案可以使總回報最大？例例4 4 中國郵遞員問題中國郵遞員問題（CPPCPPchinese postman chinese postman problem problem） 一名郵遞員負責投遞某個街區的郵件。如何為他一名郵遞員負責投遞某個街區的郵件。如何為他 （她）設計一條最短的投遞路線（從郵局出發，（她）設計一條最短的投遞路線（從郵局出發， 經過投遞區內每條街道至少一次，最后返回郵局）經過投遞區內每條街道至少一次，最后返回郵局） ？由于這一問題是我國管梅谷教授？由于這一問題是我國管梅谷教授19601960年首先年首先 提的，所以國際上稱之為中國郵遞員問題。提的，所以國際上稱之為

8、中國郵遞員問題。5 例例5 5 運輸問題運輸問題（transportation problemtransportation problem） 某種原材料有個產地，現在需要將原材料從產地某種原材料有個產地，現在需要將原材料從產地運往個使用這些原材料的工廠。假定個產地的產運往個使用這些原材料的工廠。假定個產地的產量和家工廠的需要量已知，單位產品從任一產地量和家工廠的需要量已知，單位產品從任一產地到任一工廠的運費已知，那么如何安排運輸方案到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？可以使總運輸成本最低？ 上述問題有兩個共同的特點：上述問題有兩個共同的特點：一是一是它們的目的都它們

9、的目的都是從若干可能的安排或方案中尋求某種意義下的是從若干可能的安排或方案中尋求某種意義下的最優安排或方案，數學上把這種問題稱為最優化最優安排或方案，數學上把這種問題稱為最優化或優化（或優化（optimizationoptimization）問題；）問題；二是二是它們都易于它們都易于用圖形的形式直觀地描述和表達，數學上把這種用圖形的形式直觀地描述和表達，數學上把這種與圖相關的結構稱為網絡（與圖相關的結構稱為網絡（networknetwork）。與圖和網）。與圖和網絡相關的最優化問題就是網絡最優化或稱網絡優絡相關的最優化問題就是網絡最優化或稱網絡優化化 （netwok optimizationn

10、etwok optimization）問題。）問題。 62 圖與網絡的基本概念圖與網絡的基本概念 2.1 2.1 無向圖無向圖 一個無向圖一個無向圖(undirected graph)(undirected graph)是由一個非空有限是由一個非空有限集合集合 和和 中某些元素的無序對集合中某些元素的無序對集合 構構成的二元組，記為成的二元組，記為 。 其中其中 稱為稱為圖的頂點集圖的頂點集（vertex vertex setset）或節點集（）或節點集（node setnode set），）， 中的每一個元素中的每一個元素 稱為該圖的一個頂點（稱為該圖的一個頂點（vertexvertex）或

11、節）或節點（點（nodenode）；）； 稱為稱為圖的邊集圖的邊集 （edge setedge set），）， 中的每一個元素中的每一個元素 記為記為 或或 ，被稱為，被稱為該圖的一條從該圖的一條從 到到 的邊（的邊（edgeedge）)(GV)(GV)(GE)(),(GEGVG ,)(21nvvvGV)(GV), 2 , 1(nivi,)(21meeeGE)(GEke),(jikvve ijjikvvvve), 2 , 1(mkivjv7 一個圖稱為一個圖稱為有限圖有限圖，如果它的頂點集和邊集都有，如果它的頂點集和邊集都有 限。圖的頂點數用符號限。圖的頂點數用符號 或或 表示，邊數用表示，邊

12、數用 或或 表示。表示。 當討論的圖只有一個時，總是用當討論的圖只有一個時，總是用G G來表示這個圖。來表示這個圖。從而在圖論符號中我們常略去字母從而在圖論符號中我們常略去字母G G，例如，例如: :分別分別用用 代替代替 。 端點重合為一點的邊稱為端點重合為一點的邊稱為環環(loop)(loop)。 一個圖稱為一個圖稱為簡單圖簡單圖(simple graph)(simple graph)，如果它既沒，如果它既沒有環也沒有兩條邊連接同一對頂點。有環也沒有兩條邊連接同一對頂點。|V)(G| E)(G,EV)(),(),(GGEGV8 2.2 2.2 有向圖有向圖 定義定義 一個有向圖（一個有向圖

13、（directed graphdirected graph或或 digraphdigraph）G G是由一個非空有限集合是由一個非空有限集合V V和和V V中某些元素的有序對中某些元素的有序對集合構成的二元組，記為集合構成的二元組，記為 其中其中 稱為圖的稱為圖的頂點集或節點集頂點集或節點集 . . 稱為圖的稱為圖的弧集弧集（arc setarc set），），A A中中的每一個元素的每一個元素( (即中某兩個元素的有序對即中某兩個元素的有序對) ) 記為記為 或或 ， 當弧當弧 時，時， 稱為尾（稱為尾（tailtail），）， 為頭為頭（headhead）. .),(AVG ,21nvvv

14、V,21maaaA),(jikvva ), 2 , 1(nkvvajikjikvva ivjv9 2.3 2.3 完全圖、二分圖完全圖、二分圖 每一對不同的頂點都有一條邊相連的簡單圖稱為每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖完全圖(complete graph)(complete graph)。n n個頂點的完全圖記個頂點的完全圖記為為 。 若若 ， ， （這里（這里 表示集合表示集合X X中的元素個數），中的元素個數），X X中無相鄰頂點對，中無相鄰頂點對，Y Y中亦然，則稱中亦然，則稱G G為為二分圖二分圖(bipartite graph)(bipartite graph)；特；

15、特別地，若別地，若 ，則，則 ，則，則稱稱G G為為完全二分圖完全二分圖，記成，記成 。 nKYXGV)(YX 0|YX| XYyXx,)(GExy | |,|YXK102.4 2.4 子圖子圖 如果如果 , , ,圖圖H H叫做圖叫做圖G G的子的子圖（圖（subgraphsubgraph），記作），記作 。若。若H H是是G G的子圖，的子圖，則則G G稱為稱為H H的母圖。的母圖。2.5 2.5 頂點的度頂點的度 設設 ，G G中與中與v v關聯的邊數（每個環算作兩關聯的邊數（每個環算作兩條邊）稱為條邊）稱為v v的度的度(degree)(degree)，記作，記作 。若。若 是奇數，稱

16、是奇數，稱v v是奇頂點是奇頂點(odd point)(odd point)；若是偶數，；若是偶數，稱稱v v是偶頂點是偶頂點(even point)(even point)。關于頂點的度，我們。關于頂點的度，我們有如下結果：有如下結果：(i) (i) (ii) (ii) 任意一個圖的奇頂點的個數是偶數任意一個圖的奇頂點的個數是偶數。)()(GVHV)()(GEHEGH )(GVv)(vd)(vdVvvd2)(112.6 2.6 圖與網絡的數據結構圖與網絡的數據結構 網絡優化研究的是網絡上的各種優化模型與算網絡優化研究的是網絡上的各種優化模型與算法為了在計算機上實現網絡優化的算法，首先法為了在

17、計算機上實現網絡優化的算法，首先我們必須有一種方法（即數據結構）在計算機上我們必須有一種方法（即數據結構）在計算機上來描述圖與網絡。來描述圖與網絡。 這里我們介紹計算機上用來描述圖與網絡的這里我們介紹計算機上用來描述圖與網絡的5 5種常種常用表示方法：用表示方法：鄰接矩陣表示法、關聯矩陣表示法、鄰接矩陣表示法、關聯矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。弧表表示法、鄰接表表示法和星形表示法。 在下面數據結構的討論中，我們首先假設在下面數據結構的討論中，我們首先假設 是一個簡單有向圖是一個簡單有向圖 ， ，并假設，并假設V中的中的頂點用自然數頂點用自然數1,2,n表示或編號，表示或編號

18、，A中的弧用自中的弧用自然數然數1,2,m表示或編號。表示或編號。 ),(AVG mAnV| ,|12（i）鄰接矩陣表示法）鄰接矩陣表示法 鄰接矩陣表示法是將圖以鄰接矩陣（鄰接矩陣表示法是將圖以鄰接矩陣（adjacency adjacency matrixmatrix）的形式存儲在計算機中。圖）的形式存儲在計算機中。圖 的的鄰接矩陣是如下定義的：鄰接矩陣是如下定義的：C C是一個是一個n n* *n n的的0-10-1矩陣，矩陣，即即 也就是說，如果兩節點之間有一條弧，則鄰接矩也就是說，如果兩節點之間有一條弧，則鄰接矩陣中對應的元素為陣中對應的元素為1 1；否則為；否則為0 0。 ),(AVG

19、 nnnnijcC1 , 0)(.),(, 0,),(, 1AjiAjicij13 例例1 1 對于所示的圖，可以用鄰接矩陣表示為對于所示的圖，可以用鄰接矩陣表示為 同樣，對于網絡中的權，也可以用類似鄰接矩陣同樣，對于網絡中的權，也可以用類似鄰接矩陣的矩陣表示。只是此時一條弧所對應的元素不再的矩陣表示。只是此時一條弧所對應的元素不再是是1 1，而是，而是相應的權相應的權而已。如果網絡中每條弧賦有而已。如果網絡中每條弧賦有多種權，則可以用多個矩陣表示這些權。多種權，則可以用多個矩陣表示這些權。011001010000010010000011014（iiii）關聯矩陣表示法）關聯矩陣表示法 關聯矩

20、陣表示法是將圖以關聯矩陣（關聯矩陣表示法是將圖以關聯矩陣（incidence incidence matrixmatrix）的形式存儲在計算機中）的形式存儲在計算機中 圖圖 的關聯矩陣的關聯矩陣B B是如下定義的：是如下定義的：B B是一是一個個n n* *m m的矩陣，即的矩陣，即),(AVG mnmnikbB1 , 0 , 1)(., 0,),(, , 1,),(, 1其它AijkVjAjikVjbik15 如果一個節點是一條弧的如果一個節點是一條弧的起點起點，則關聯矩陣中對，則關聯矩陣中對應的元素為應的元素為1 1；如果一個節點是一條弧的；如果一個節點是一條弧的終點終點，則，則關聯矩陣中

21、對應的元素為關聯矩陣中對應的元素為-1-1；如果一個節點與一；如果一個節點與一條弧條弧不關聯不關聯，則關聯矩陣中對應的元素為，則關聯矩陣中對應的元素為0 0。 例例2 2 對于例對于例1 1所示的圖，如果關聯矩陣中每列對應所示的圖，如果關聯矩陣中每列對應弧的順序為弧的順序為(1,2)(1,2)，(1,3)(1,3)，(2,4)(2,4)，(3,2)(3,2)，(4,3)(4,3)，(4,5)(4,5)，(5,3)(5,3)和和(5,4)(5,4)，則關聯矩陣表示，則關聯矩陣表示為為（列單位為弧）（列單位為弧） 111000001011010001011010000011010000001116

22、（iiiiii）弧表示法）弧表示法 弧表表示法將圖以弧表（弧表表示法將圖以弧表（arc listarc list）的形式存儲）的形式存儲在計算機中。所謂圖的弧表，也就是圖的弧集合在計算機中。所謂圖的弧表，也就是圖的弧集合中的所有有序對。中的所有有序對。 例例3 3，假設弧，假設弧(1,2)(1,2)，(1,3)(1,3)，(2,4)(2,4)，(3,2)(3,2)，(4,3)(4,3)，(4,5)(4,5)，(5,3)(5,3)和和(5,4)(5,4)上的權分別為上的權分別為8 8，9 9，6 6，4 4，0 0，3 3，6 6和和7 7，則弧表表示如下：，則弧表表示如下： 起點起點11234

23、455終點終點23423534權權8964036717（iviv）鄰接表表示法）鄰接表表示法 鄰接表表示法將圖以鄰接表（鄰接表表示法將圖以鄰接表（adjacency listsadjacency lists）的形式存儲在計算機中。的形式存儲在計算機中。 所謂圖的鄰接表，也就是圖的所有節點的鄰接表所謂圖的鄰接表，也就是圖的所有節點的鄰接表的集合；的集合；而對每個節點，它的鄰接表就是它的所而對每個節點，它的鄰接表就是它的所有出弧有出弧。鄰接表表示法就是對圖的每個節點，用。鄰接表表示法就是對圖的每個節點，用一個單向鏈表列出從該節點出發的所有弧，鏈表一個單向鏈表列出從該節點出發的所有弧，鏈表中每個單元

24、對應于一條出弧。中每個單元對應于一條出弧。為了記錄弧上的權，為了記錄弧上的權，鏈表中每個單元除列出弧的另一個端點外，還可鏈表中每個單元除列出弧的另一個端點外，還可以包含弧上的權等作為數據域以包含弧上的權等作為數據域。圖的整個鄰接表。圖的整個鄰接表可以用一個指針數組表示。可以用一個指針數組表示。 18 對于有向圖對于有向圖 ，一般用，一般用 表示節表示節點的鄰接表，即節點的所有出弧構成的集合或鏈點的鄰接表，即節點的所有出弧構成的集合或鏈表（實際上只需要列出弧的另一個端點，即弧的表（實際上只需要列出弧的另一個端點，即弧的頭）。例如上面例子，頭）。例如上面例子， ， 等。等。),(AVG )(iA3

25、 , 2) 1 (A4 , 3)5(A19（v v）星形表示法）星形表示法 星形（星形（starstar）表示法的思想與鄰接表表示法的思）表示法的思想與鄰接表表示法的思想有一定的相似之處。對每個節點，它也是記錄想有一定的相似之處。對每個節點，它也是記錄從該節點出發的所有弧，但它不是采用單向鏈表從該節點出發的所有弧，但它不是采用單向鏈表而是采用一個單一的數組表示。而是采用一個單一的數組表示。 記錄弧信息的數組弧編號12345678起點11234455終點23423534權89640367203 應用應用最短路問題最短路問題 3.1 3.1 兩個指定頂點之間的最短路徑兩個指定頂點之間的最短路徑 問

26、題如下：給出了一個連接若干個城鎮的鐵路網問題如下：給出了一個連接若干個城鎮的鐵路網絡，在這個網絡的兩個指定城鎮間，找一條最短絡，在這個網絡的兩個指定城鎮間，找一條最短鐵路線。鐵路線。 以各城鎮為圖以各城鎮為圖G G的頂點，兩城鎮間的直通鐵路為圖的頂點，兩城鎮間的直通鐵路為圖G G相應兩頂點間的邊，得圖相應兩頂點間的邊，得圖G G。對。對G G的每一邊的每一邊e e，賦，賦以一個實數以一個實數 直通鐵路的長度，稱為直通鐵路的長度，稱為e e的權，的權，得到賦權圖得到賦權圖G G。G G的子圖的權是指子圖的子圖的權是指子圖G G的各邊的權的各邊的權和。和。 問題就是求賦權圖中指定的兩個頂點問題就是

27、求賦權圖中指定的兩個頂點 間的具間的具最小權的軌。這條軌叫做最小權的軌。這條軌叫做 間的最短路，它間的最短路，它的權叫做的權叫做 間的距離，亦記作間的距離，亦記作 。)(ew00,vu00,vu00,vu),(00vud21求最短路已有成熟的算法：求最短路已有成熟的算法：迪克斯特拉迪克斯特拉（DijkstraDijkstra）算法，其基本思想是按距算法，其基本思想是按距 從近到遠為順序，依次從近到遠為順序，依次求得求得 到的到的G G各頂點的最短路和距離，直至（或直各頂點的最短路和距離，直至（或直至的所有頂點），算法結束。為避免重復并保留每至的所有頂點），算法結束。為避免重復并保留每一步的計算

28、信息，采用了標號算法。下面是該算法一步的計算信息，采用了標號算法。下面是該算法。(i)(i) 令令 ，對，對 令令 ， ， 。(ii) (ii) 對每個對每個 , ,用用 代替代替 計算計算 ，把達到這個最小值的一個頂點，把達到這個最小值的一個頂點 記為記為 ，令，令 。(iii)(iii)若若 ，停止；若，停止；若 ，用，用i+1i+1代替代替 i i，轉，轉(ii)(ii)。0u0u0)(0ul0uv )(vl00uS 0iiSv)()(),(minuvwulvliSu)(vl)(minvliSv1iu11iiiuSS1| Vi1| Vi22找出找出u0u0到其他各點的最短路徑到其他各點的

29、最短路徑23243.2 每對頂點之間的最短路徑每對頂點之間的最短路徑 計算賦權圖中各對頂點之間最短路徑，顯然可以計算賦權圖中各對頂點之間最短路徑，顯然可以調用調用DijkstraDijkstra算法。具體方法是：算法。具體方法是：每次以不同的每次以不同的頂點作為起點頂點作為起點，用，用DijkstraDijkstra算法求出從該起點到算法求出從該起點到其余頂點的最短路徑，反復執行次這樣的操作，其余頂點的最短路徑，反復執行次這樣的操作，就可得到從每一個頂點到其它頂點的最短路徑。就可得到從每一個頂點到其它頂點的最短路徑。 第二種解決這一問題的方法是由第二種解決這一問題的方法是由Floyd R WF

30、loyd R W提出的提出的算法，稱之為算法，稱之為FloydFloyd算法。算法。 25假設圖權的鄰接矩陣為，假設圖權的鄰接矩陣為，來存放各邊長度，其中：來存放各邊長度，其中： ； 之間沒有邊，在程序中以各邊都不之間沒有邊，在程序中以各邊都不 可能達到的充分大的數代替；可能達到的充分大的數代替； 是是 i,ji,j之間邊的長度，之間邊的長度， 。nnnnnnaaaaaaaaaA21222211121100iiani, 2 , 1ijaji,ijijwa nji, 2 , 1,26 FloydFloyd算法的基本思想是：遞推產生一個矩陣序算法的基本思想是：遞推產生一個矩陣序列列 ，其中，其中

31、表示從頂點表示從頂點 到頂點到頂點 的路徑上所經過的頂點序號不大于的路徑上所經過的頂點序號不大于k k 的最短路徑長度。的最短路徑長度。 計算時用迭代公式：計算時用迭代公式： k k是迭代次數，是迭代次數， 。 最后，當最后，當k=nk=n時，時， 即是各頂點之間的最短通路值。即是各頂點之間的最短通路值。 ( (例題見附件例題見附件) )nkAAAA,10),(jiAkivjv),(),(),(min(),(111jkAkiAjiAjiAkkkknkji, 2 , 1,nA274 樹樹4.1 4.1 基本概念基本概念連通的無圈圖叫做樹，記之為連通的無圈圖叫做樹，記之為T T。4.2 4.2 應

32、用應用連線問題連線問題 欲修筑連接欲修筑連接n n個城市的鐵路，已知城與城之間的鐵個城市的鐵路，已知城與城之間的鐵路造價為路造價為 ，設計一個線路圖，使總造價最低。，設計一個線路圖，使總造價最低。 連線問題的數學模型是在連通賦權圖上求權最小連線問題的數學模型是在連通賦權圖上求權最小的生成樹。賦權圖的具有最小權的生成樹叫做最小生的生成樹。賦權圖的具有最小權的生成樹叫做最小生成樹。成樹。 ijC28定理定理 設設G是具有是具有n個頂點的圖，則下述命題等價：個頂點的圖，則下述命題等價：1) G是樹（是樹（ G無圈且連通）；無圈且連通）；2) G無圈，且有無圈，且有n-1條邊；條邊；3) G連通，且有

33、連通，且有n-1條邊；條邊；4) G無圈，但添加任一條新邊恰好產生一個圈無圈，但添加任一條新邊恰好產生一個圈; 5) G連通，且刪去一條邊就不連通了（即連通，且刪去一條邊就不連通了（即G為為最最最小連通圖最小連通圖）；）；6) G中任意兩頂點間有唯一一條路中任意兩頂點間有唯一一條路.29找圖中生成樹的方法找圖中生成樹的方法可分為兩種：避圈法和破圈法可分為兩種：避圈法和破圈法 A 避圈法避圈法 : 深探法和廣探法深探法和廣探法 B 破圈法破圈法 30A 避圈法 這種方法就是在已給的圖這種方法就是在已給的圖G中，每步選出一中，每步選出一條邊使它與已選邊不構成圈，直到選夠條邊使它與已選邊不構成圈，直

34、到選夠n-1條邊為條邊為止止. 這種方法可稱為這種方法可稱為“避圈法避圈法”或或“加邊法加邊法” 在避圈法中，按照邊的選法不同，找圖中生在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種：成樹的方法可分為兩種：深探法深探法和和廣探法廣探法.31a) 深探法深探法 若這樣的邊的另一端均已有標號，就退到標號為若這樣的邊的另一端均已有標號，就退到標號為步驟如下：步驟如下：i) 在點集在點集V中任取一點中任取一點u,ii) 若某點若某點v已得標號，檢已得標號，檢端是否均已標號端是否均已標號. 若有邊若有邊vw之之w未標號未標號,則給則給w代代v，重復，重復ii).i-1的的r點點,以以r代代v

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

36、給給u以標號以標號0.Vi,檢查檢查Vi,VVi中的邊端點中的邊端點邊邊.例例用廣探法求出下圖用廣探法求出下圖10的一棵生成樹的一棵生成樹 標號為止標號為止.圖103101221321223433B 破圈法破圈法 相對于避圈法，還有一種求生成樹的方法叫做相對于避圈法，還有一種求生成樹的方法叫做“破圈法破圈法”. . 這種方法就是在圖這種方法就是在圖G G中任取一個圈，任中任取一個圈，任意舍棄一條邊，將這個圈破掉，重復這個步驟直到圖意舍棄一條邊，將這個圈破掉，重復這個步驟直到圖G G中沒有圈為止中沒有圈為止. .例例 用破圈法求出用破圈法求出 下圖的一棵生成樹下圖的一棵生成樹.圖的生成樹不是唯一

37、的圖的生成樹不是唯一的 .34A A Kruskal Kruskal算法（或避圈法）算法（或避圈法）步驟如下：步驟如下： 1) 選擇邊選擇邊e1，使得，使得w(e1)盡可能小；盡可能小；2) 若已選定邊若已選定邊 ，則從，則從ieee,.,21,.,21ieeeE中選取中選取 ，使得，使得:1iei) 為無圈圖，為無圈圖，,.,121ieeeG ii) 是滿足是滿足i)的盡可能小的權，的盡可能小的權，)(1iew 3) 當第當第2)步不能繼續執行時，則停止步不能繼續執行時，則停止.定理定理4 由由Kruskal算法構作的任何生成樹算法構作的任何生成樹,.,121*eeeGT都是最小樹都是最小樹

38、.最小生成樹與算法最小生成樹與算法35例例 用用Kruskal算法求下圖的最小樹算法求下圖的最小樹.在左圖中在左圖中 權值權值,.,821eee最小的邊有最小的邊有 任取一條任取一條 ,51ee,1e 在在 中選取權值中選取權值,.,832eee,5e最小的邊最小的邊 中權值最小邊有中權值最小邊有 , 從中選從中選：73,ee;3e任取一條邊任取一條邊會與已選邊構成圈會與已選邊構成圈,故停止故停止,得得中選取在中選取中選取在中選取,7e 中選取中選取 . 但但 與與 都都,86ee84,ee4e8e,876432eeeeee,87642eeeee,42ee在36B破圈法破圈法算法算法2 步驟如

39、下：步驟如下： 1) 1) 從圖從圖G G中任選一棵樹中任選一棵樹T T1 1. .2) 2) 加上一條弦加上一條弦e e1 1，T T1 1+e+e1 1中中 立即生成一個圈立即生成一個圈. . 去掉此去掉此 圈中最大權邊，得到新圈中最大權邊，得到新樹樹T T2 2, ,以以T T2 2代代T T1 1, ,重復重復2)2)再再檢查剩余的弦，直到全檢查剩余的弦，直到全部弦檢查完畢為止部弦檢查完畢為止. .例例 用破圈法求下圖的最小樹用破圈法求下圖的最小樹.37 prim prim算法構造最小生成樹算法構造最小生成樹 設置兩個集合設置兩個集合P P和和Q,Q,其中其中P P用于存放的最小生成用

40、于存放的最小生成樹樹G G中的頂點，集合中的頂點，集合Q Q存放的最小生成樹存放的最小生成樹G G中的邊。令中的邊。令集合集合P P的初值為的初值為 （假設構造最小生成樹時，（假設構造最小生成樹時，從從頂點頂點 出發），集合出發），集合Q Q的初值為的初值為 。primprim算法的思想是算法的思想是，從所有，從所有 ， 的邊的邊中，選取具有最小權值的邊中，選取具有最小權值的邊 ，將頂點，將頂點v v加入加入集合集合P P中，將邊中，將邊pvpv加入集合加入集合Q Q中，如此不斷重復，直中，如此不斷重復，直到到 P=V P=V 時，最小生成樹構造完畢，這時集合時，最小生成樹構造完畢，這時集合Q

41、 Q中包中包含了最小生成樹的所有邊。含了最小生成樹的所有邊。1vP 1vQPpPVvpv38例例11 用用prim算法求右圖的最小生成樹。算法求右圖的最小生成樹。我們用的第一、二、三行分別表示生成樹邊的起點、終點、權集合。我們用的第一、二、三行分別表示生成樹邊的起點、終點、權集合。MatlabMatlab程序如下：程序如下：clc;clear;clc;clear;M=1000;M=1000;a(1,2)=50; a(1,3)=60;a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(3,4)=52;a(3,7)=45;a(4,5)=50; a(4,6)=30;a(4,7)=42;