圖的常見應用

1、本節(jié)主要內(nèi)容： 1、最小生成樹算法 2、最短路徑 3、拓撲排序 4、關鍵路徑19.5 最小生成樹1.基本概念 一個有n個頂點的連通圖的生成樹是原圖的極小連通子圖，它包含原圖中的所有n個頂點，并且有保持圖連通的最少的邊。 （1）若在生成樹中刪除一條邊就會使該生成樹因變成非連通圖而不再滿足生成樹的定義；（2）若在生成樹中增加一條邊就會使該生成樹中因存在回路而不再滿足生成樹的定義；（3）一個連通圖的生成樹可能有許多；（4）有n個頂點的無向連通圖，無論它的生成樹的形狀如何，一定有且只有n-1條邊。 21V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V(a)(b)(c)無向圖和它的

2、不同的生成樹 3 如果無向連通圖是一個帶權圖，那么它的所有生成樹中必有一棵邊的權值總和最小的生成樹，我們稱這棵生成樹為最小代價生成樹，簡稱最小生成樹。 構造有n個頂點的無向連通帶權圖的最小生成樹必須滿足以下三條：（1）構造的最小生成樹必須包括n個頂點；（2）構造的最小生成樹中有且只有n-1條邊；（3）構造的最小生成樹中不存在回路。 典型的構造方法有兩種，一種稱作普里姆（Prim）算法，另一種稱作克魯斯卡爾（Kruskal）算法。 42.普里姆算法 一、算法思想 假設G=(V,E)為一個帶權圖，其中V為帶權圖中頂點的集合，E為帶權圖中邊的權值集合。設置兩個新的集合U和T，其中U用于存放帶權圖G的

3、最小生成樹的頂點的集合，T用于存放帶權圖G的最小生成樹的權值的集合。 普里姆算法思想是：令集合U的初值為U=u0（即假設構造最小生成樹時從頂點u0開始），集合T的初值為T=。從所有頂點uU和頂點vV-U的帶權邊中選出具有最小權值的邊(u,v)，將頂點v加入集合U中，將邊(u,v) 加入集合T中。如此不斷重復，當U=V時則最小生成樹構造完畢。此時集合U中存放著最小生成樹頂點的集合，集合T中存放著最小生成樹邊的權值集合。 56圖9-10 普里姆算法構造最小生成樹的過程 7圖9-10 普里姆算法構造最小生成樹的過程 8圖9-10 普里姆算法構造最小生成樹的過程 93.克魯斯卡爾算法 克魯斯卡爾算法是

4、一種按照帶權圖中邊的權值的遞增順序構造最小生成樹的方法。設無向連通帶權圖G=(V,E)，其中V為頂點的集合，E為邊的集合。 克魯斯卡爾算法思想是：設帶權圖G的最小生成樹T由頂點集合和邊的集合構成，其初值為T=(V,)，即初始時最小生成樹T只由帶權圖G中的頂點集合組成，各頂點之間沒有一條邊。這樣，最小生成樹T中的各個頂點各自構成一個連通分量。然后，按照邊的權值遞增的順序考察帶權圖G中的邊集合E中的各條邊，若被考察的邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊加入到最小生成樹T，同時把兩個連通分量連接為一個連通分量；若被考察的邊的兩個頂點屬于T的同一個連通分量，則將此邊舍去。如此下去，當T中的

5、連通分量個數(shù)為1時，T中的該連通分量即為帶權圖G的一棵最小生成樹 10克魯斯卡爾算法構造最小生成樹的過程 11克魯斯卡爾算法構造最小生成樹的過程 12139.6 最短路徑 1.基本概念 路徑長度:一條路徑上所經(jīng)過的邊的數(shù)目 帶權路徑長度:路徑上所經(jīng)過邊的權值之和最短路徑:(帶權)路徑長度(值)最小的那條路徑圖9-13 （a）有向帶權圖； （b）鄰接矩陣 14152.從一個頂點到其余各頂點的最短路徑 一、狄克斯特拉算法思想 按路徑長度遞增的順序逐步產(chǎn)生最短路徑。 狄克斯特拉算法的思想是：設置兩個頂點的集合S和T，集合S中存放已找到最短路徑的頂點，集合T中存放當前還未找到最短路徑的頂點。初始狀態(tài)時

6、，集合S中只包含源點，設為v0，然后從集合T中選擇到源點v0路徑長度最短的頂點u加入到集合S中，集合S中每加入一個新的頂點u都要修改源點v0到集合T中剩余頂點的當前最短路徑長度值，集合T中各頂點的新的當前最短路徑長度值，為原來的當前最短路徑長度值與從源點過頂點u到達該頂點的路徑長度中的較小者。此過程不斷重復，直到集合T中的頂點全部加入到集合S中為止。 16EFDBCA51810715EFDBCA530(a)EFDBCA530715EFDBCA5301810715EFDBCA851810715EFDBCA8510715(b)(c)(d)(e)(f)狄克斯特拉算法求從頂點A到其余各頂點最短路徑的過

7、程 173.每對頂點之間的最短路徑 帶權有向圖，每對頂點之間的最短路徑可通過調(diào)用狄克斯特拉算法實現(xiàn)。具體方法是：每次以不同的頂點作為源點，調(diào)用狄克斯特拉算法求出從該源點到其余頂點的最短路徑。重復n次就可求出每對頂點之間的最短路徑。由于狄克斯特拉算法的時間復雜度為O(n2)，所以這種算法的時間復雜度為O(n3)。 弗洛伊德算法的思想是：設矩陣cost用來存放帶權有向圖G的權值，即矩陣元素costij中存放著下標為i的頂點到下標為j的頂點之間的權值，可以通過遞推構造一個矩陣序列A0,A1,A2,AN來求每對頂點之間的最短路徑。其中，Akij（0kn）表示從頂點vi到頂點vj的路徑上所經(jīng)過的頂點下標

8、不大于k的最短路徑長度。初始時有，A0ij=costij。18有向無環(huán)圖及其應用 1 有向無環(huán)圖的概念 2 AOV網(wǎng)與拓撲排序 3 AOE圖與關鍵路徑191 有向無環(huán)圖的概念 一個無環(huán)的有向圖稱做有向無環(huán)圖（directed acycline praph）。簡稱DAG圖。DAG圖是一類較特殊的有向圖，下圖給出了有向樹、DAG圖和有向圖的例子。20(1) 有向無環(huán)圖是描述含有公共子式的表達式的有效工具： 例如下述表達式： (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 可以用第六章討論的二叉樹來表示，如下圖所示。21 仔細觀察該表達式，可發(fā)現(xiàn)有一些相同的子表達式，如(c+d)和

9、(c+d)*e等，在二叉樹中，它們也重復出現(xiàn)。若利用有向無環(huán)圖，則可實現(xiàn)對相同子式的共享，從而節(jié)省存儲空間。例如下圖所示為表示同一表達式的有向無環(huán)圖。22(2)無環(huán)圖是描述一項工程或系統(tǒng)的進行過程的有效工具： 除最簡單的情況之外，幾乎所有的工程（project）都可分為若干個稱作活動（activity）的子工程，而這些子工程之間，通常受著一定條件的約束，如其中某些子工程的開始必須在另一些子工程完成之后。 對整個工程和系統(tǒng)，人們關心的是兩個方面的問題：一是工程能否順利進行：二是估算整個工程完成所必須的最短時間。我們也在這一節(jié)討論這一問題。232 AOV網(wǎng)與拓撲排序1AOV網(wǎng) (頂點表示活動的網(wǎng))

10、(1) AOV概念：頂點表示活動，弧表示活動之間存在的制約關系網(wǎng)稱為AOV。(2) 用AOV表示一個工程： 概念所有的工程或者某種流程可以分為若干個小的工程或階段，這些小的工程或階段就稱為活動。若以圖中的頂點來表示活動，有向邊表示活動之間的優(yōu)先關系，則這樣活動在頂點上的有向圖稱為AOV網(wǎng)。在AOV網(wǎng)中，若從頂點i到頂點j之間存在一條有向路徑，稱頂點i是頂點j的前驅(qū)，或者稱頂點j是頂點i 的后繼。若是圖中的弧，則稱頂點i是頂點j的直接前驅(qū)，頂點j 是頂點i的直接后驅(qū)。249.7 拓撲排序 1偏序關系和全序關系 拓撲排序就是要由某個集合上的偏序關系得到該集合上的全序關系。 若集合X上的關系R是自反

11、的、反對稱的和傳遞的，則稱關系R是集合X上的偏序關系（或稱半序關系）。 設關系R為定義在集合X上的二元關系，若對于每一個xX，都有(x,x)R，則稱R是自反的。 設關系R為定義在集合X上的二元關系，如果對于任意的x,y,zX，若當(x,y)R且(y,z)R時，有(x,z)R，則稱關系R是傳遞的。25偏序關系的實質(zhì) 是在集合X的元素之間建立層次結構。這種層次結構是依賴于偏序關系的可比性建立起來的。但是，偏序關系不能保證集合X中的任意兩個元素之間都能比較。而全序關系可以保證集合中的任意兩個元素之間都可以比較。26 對于AOV網(wǎng)的拓撲排序就是將AOV網(wǎng)中的所有頂點排成一個線性序列。 拓撲排序?qū)嶋H上就

12、是要由某個集合上的一個偏序關系得到該集合上的一個全序關系。 27下圖給出在一個AOV網(wǎng)上實施上述步驟的例子。28 例如：計算機專業(yè)的學生必須完成一系列規(guī)定的基礎課和專業(yè)課才能畢業(yè)。29 4有向圖的拓撲排序算法 有向圖的拓撲排序算法： (1) 在有向圖中選擇一個沒有前驅(qū)的頂點，并把它輸出； (2) 從有向圖中刪去該頂點以及與它相關的有向邊。 重復上述兩個步驟，直到所有頂點都輸出，或者剩余的頂點中找不到?jīng)]有前驅(qū)的頂點。在前一種情況下，頂點的輸出序列就是一個拓撲序列；后一種情況則說明有向圖中存在回路，如果有向圖中存在回路，則該有向圖一定無法得到一個拓撲序列。30 上述算法僅能得到有向圖的一個拓撲序列

13、。改進上述算法，可以得到有向圖的所有拓撲序列。 如果一個有向圖存在一個拓撲序列，通常表示該有向圖對應的某個施工流程圖的一種施工方案切實可行；而如果一個有向圖不存在一個拓撲序列，則說明該有向圖對應的某個施工流程圖存在設計問題，不存在切實可行的任何一種施工方案。 31 例：對于如下圖所示的AOV網(wǎng)，寫出利用拓撲排序算法得到的一個拓撲序列。 解：根據(jù)拓撲排序算法，得到的一個拓撲序列為0,1,7,2,4,8,5,9,3,6。392475608132建筑工程拓撲排序問題 333 AOE圖與關鍵路徑1AOE網(wǎng)（邊表示活動的網(wǎng)） (1) AOE網(wǎng)概念：若在帶權的有向圖中，以頂點表示事件，以有向邊表示活動，邊

14、上的權值表示活動的開銷（如該活動持續(xù)的時間），則此帶權的有向圖稱為AOE網(wǎng)。 (2)AOE網(wǎng)表示一項工程能表示出： 完成預定工程計劃所需要進行的活動; 每個活動計劃完成的時間; 要發(fā)生哪些事件以及這些事件與活動之間的關系;34(3) 通過AOE網(wǎng)可以求得： 估算工程完成的時間 確定哪些活動是影響工程進度的關鍵。 (4) AOE網(wǎng)的兩個特點： 只有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各有向邊所代表的活動才能開始。 只有在進入一某頂點的各有向邊所代表的活動都已經(jīng)結束，該頂點所代表的事件才能發(fā)生。35a9=6a6=4a2=7a1=5a3=3a4=6a5=3a7=5a8=4a10=5a11=8a

15、14=9a12=2a13=8a15=3 圖9-19 AOE網(wǎng)v0v3v1v4v7v6v8v5v2v936基本概念：路徑長度：AOE網(wǎng)的一條路徑上所有活動的總和稱為該路徑的長度。關鍵路徑：在AOE網(wǎng)中，從源點到匯點的所有路徑中，具有最大路徑長度的路徑稱為關鍵路徑。關鍵活動：關鍵路徑上的活動稱為關鍵活動。顯然，完成整個工程的最短時間就是AOE網(wǎng)中關鍵路徑的長度，也就是AOE網(wǎng)中各關鍵活動所持續(xù)時間的總和。 例：找出前圖所示的AOE網(wǎng)中的關鍵路徑。解：在AOE網(wǎng)中，從源點v0到匯點v9共有13條路徑，分別計算這13條路徑的長度，得到最大路徑長度為31。最大路徑長度對應的關鍵路徑為(v0,v2,v3,

16、v4,v6,v9) 和(v0,v2,v3,v4,v7,v9)。373幾個參數(shù)的定義活動的持續(xù)時間dut()：對于有向邊代表的活動，dut()是該有向邊的權值。事件可能的最早開始時間e(k)：對于頂點k代表的事件，e(k)是從源點到該頂點的最大路徑長度。在一個有n+1個事件的AOE網(wǎng)中, 源點0的最早開始時間e(0)等于0。事件k（k=1,2,3,n）可能的最早開始時間e(k)可用遞推公式表示為： e(k)=0 頂點k=0為源點Max e(j)+dut() | 為網(wǎng)中的有向邊 其他頂點38活動可能的最早開始時間e(i)：對于有向邊ai代表的活動，e(i)是該活動的弧尾事件可能的最早發(fā)生時間。假設

17、活動ai代表的是有向邊，即ai是關聯(lián)事件j和事件k的的活動，則e(i) =e(j)。 活動允許的最晚開始時間l(i)：對于有向邊ai代表的活動，l(i)是該活動的弧頭事件允許的最晚發(fā)生時間減去該活動持續(xù)的時間。l(i)是在不推遲整個工程完成的前提下，活動ai必須開始的時間。假設活動ai代表的是有向邊，即ai是關聯(lián)事件j和事件k的的活動，則l(i) = l(k) - dut()。 這樣，每個活動允許的時間余量就是l(i) - e(i)。而關鍵活動就是l(i) - e(i) = 0的那些活動，即可能的最早開始時間e(i)等于允許的最晚開始時間l(i)的那些活動就是關鍵活動。394尋找關鍵活動的算法

18、 求AOE網(wǎng)中關鍵活動的算法步驟為： （1）建立包含n+1個頂點、e條有向邊的AOE網(wǎng)。其中，頂點v0為源點，頂點vn為匯點； （2）根據(jù)有向圖的拓撲排序算法，求出AOE網(wǎng)的拓撲序列。如果AOE網(wǎng)中存在環(huán)，拓撲序列不存在，則無法得到AOE網(wǎng)的關鍵活動，算法失敗退出； （3）從源點v0開始，令源點v0的最早開始時間ve0=0，按拓撲序列求其余各頂點k(k=1,2,3,n)的最早開始時間vek； （4）從匯點vn開始，令匯點vn的最晚發(fā)生時間vln=ven，按逆拓撲序列求其余各頂點k(k=n-1,n-2,2,1,0)的最晚發(fā)生時間vlk； （5）計算每個活動的最早開始時間ek (k=1,2,3,e

19、)； （6）計算每個活動的最晚開始時間lk (k=1,2,3,e)； （7）找出所有ek= lk的活動k，這些活動即為AOE網(wǎng)的關鍵活動。40 下圖給出了一個具有15個活動、11個事件的假想工程的AOE網(wǎng)。v1,v2, v11分別表示一個事件；,分別表示一個活動；用a1,a2, ,a15代表這些活動。其中,v1稱為源點，是整個工程的開始點，其入度為0；v11為終點，是整個工程的結束點，其出度為0 。 對于AOE網(wǎng)，可采用與AOV網(wǎng)一樣的鄰接表存儲方式。其中，鄰接表中邊結點的域為該邊的權值，即該有向邊代表的活動所持續(xù)的時間。415、求關鍵路徑的過程 下面以前圖所示的AOE網(wǎng)為例，求出上述參量，來

20、確定該網(wǎng)的關鍵活動和關鍵路徑。 (1) 按照式6-1求事件的最早發(fā)生時間vek ve 1=0 ve 2=3 ve 3=4 ve 4=ve2+2=5 ve 5=maxve2+1,ve3+3=7 ve 6=ve3+5=9 ve 7=maxve4+6,ve5+8=15 ve 8=ve5+4=11 ve 9=maxve8+10,ve6+2=21 ve 10=maxve8+4,ve9+1=22 ve 11=maxve7+7,ve10+6=2842(2) 按照式6-2求事件的最遲發(fā)生時間vlk。 vl 11= ve 11=28 vl 10= vl 11-6=22 vl 9= vl 10-1=21 vl 8

21、=min vl 10-4, vl 9-10=11 vl 7= vl 11-7=21 vl 6= vl 9-2=19 vl 5=min vl 7-8,vl 8-4=7 vl 4= vl 7-6=15 vl 3=min vl 5-3, vl 6-5=4 vl 2=min vl 4-2, vl 5-1=6 vl 1=minvl 2-3, vl 3-4=043 (3) 按照 (6-3)式和(6-4)式求活動ai的最早開始時間ei和最晚開始時間li活動a1 e 1=ve 1=0 l 1=vl 2 -3 =3活動a2 e 2=ve 1=0 l 2=vl 3 - 4=0活動a3 e 3=ve 2=3 l 3

22、=vl 4 - 2=13活動a4 e 4=ve 2=3 l 4=vl 5 - 1=6活動a5 e 5=ve 3=4 l 5=vl 5 - 3=4活動a6 e 6=ve 3=4 l 6=vl 6 - 5=14活動a7 e 7=ve 4=5 l 7=vl 7 - 6=15活動a8 e 8=ve 5=7 l 8=vl 7 - 8=13活動a9 e 9=ve 5=7 l 9=vl 8 - 4=7活動a10 e 10=ve 6=9 l 10=vl 9 - 2=19活動a11 e 11=ve 7=15 l 11=vl 11 - 7=21活動a12 e 12=ve 8=11 l 12=vl 10 - 4=18活動a13 e 13=ve 8=11 l 13=vl 9 - 10=11活動a14 e 14=ve 9=21 l 14=vl 10 -1=21活動a15 e 15=ve 10=22 l 15=vl 11 -6 =2244(5) 求關鍵路徑： 比較ei和li