lxmgraphalgorithms

1、圖算法圖的遍歷l和樹的遍歷類似，在此，我們希望從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。這一過程就叫做圖的遍歷(traversinggraph)。圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等算法的基礎。l通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。它們對無向圖和有向圖都適用。圖的遍歷：廣度優(yōu)先搜索 廣度優(yōu)先搜索(breadth-first search)遍歷類似于樹的按層次遍歷的過程。 假設從圖中某頂點v出發(fā)，在訪問v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點

2、的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起始點，由近至遠，依次訪問和v有路徑相通且路徑長度為1，2，的頂點。圖的遍歷：廣度優(yōu)先搜索例子 例如，對右進行廣度優(yōu)先搜索遍歷的過程如圖(c)所示，得到的頂點訪問序列為 v1-v2-v3-v4-v5-v6-v7-v8 v8v5v4v6v7v1v3v2v1v3v6v7v5v2v4v8(c)圖的遍歷：深度優(yōu)先搜索 深度優(yōu)先搜索(depth-first search)遍歷類似于樹的先

3、根遍歷，是樹的先根遍歷的推廣。 假設初始狀態(tài)是圖中所有頂點未曾被訪問，則深度優(yōu)先搜索可從圖中某個頂點v出發(fā)，訪問此頂點，然后依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。圖的遍歷：深度優(yōu)先搜索例子 以圖 (a)中無向圖為例，深度優(yōu)先搜索遍歷圖的過程如圖 (b)所示。 (a) 由此，得到頂點訪問序列為： v1-v2-v4-v8-v5-v3-v6-v7 (b)v8v5v4v6v7v1v3v2v5v8v7v6v4v3v2v1無向圖的dfs算法p

4、106v5v4v1v3v2v5v4v1v3v2(1)(2)(3)(4)(5)(6)(7) 對(a)圖，由dfs算法可得(b)圖有向樹（實線）和余數（虛線），箭頭表示搜索過程。 其中tree=(1),(2),(3),(5)， back=(4),(6),(7) num(v1)=1, num(v2)=2, num(v4)=3, num(v3)=4,num(v5)=5 后退邊的方向是從num值高的頂點到num值小的頂點； 樹枝邊的方向是從num值低的頂點到num值高的頂點。 若從頂點a到可以沿著dfs外向樹樹枝走到頂點b，則成a點為b點的祖先，b點為a點的子孫。無向圖的dfs算法p106(1)tree

5、=, back=,i=1.all v v 作【father(v)=0,mark(v)=0】(2)任選一點r滿足mark(r)=0,作【v=r,mark(v)=1,num(v)=i 】(3)若所有與v點關聯的邊均已給出標志，則轉(5)；否則任選一未給標志的邊(v,w)轉(4)。(4)給(v,w)邊以v到w的方向，并給以標志*表示通過檢查。若mark(w)=0，則作【i+,num(w)=i,tree=tree u(v,w),mark(w)=1,father(w)=v,v=w ，轉(3) 】。若mark(w)=1，則作【back=back u (v,w) ，轉(3) 】(5)若father(v)!=

6、0，則作 【v=father(v)，轉(3)】； 否則作 【若all v v 恒有mark(v)=1， 則結束； 否則作 i+,轉(2) 】v5v4v1v3v2(1)(2)(3)(4)(5)(6)(7)有向無環(huán)圖的dfs算法p108 num(v1)=1, num(v2)=2, num(v3)=3, num(v4)=4, num(v5)=5, num(v6)=6, num(v7)=7,tree=(1),(2),(3),(7),(9)forward=(4),(5)cross=(8),(10)back=(11)v5v4v6v7v1v3v2v5v4v6v7v1v3v2(6)(1)(2)(3)(4)(5

7、)(7)(8)(9)(10)(11)圖的連通性：無向圖的連通性l 在簡單無向圖g = (v, e)中, 若存在一條路連接vi和vj, 則稱頂點vi和vj是連接的。若g中任意兩個頂點均是連接的,則稱g是連通(connected)的,否則是不連通的或分離(separated)圖。l 在n階簡單圖g, 如果對g的每對頂點u和v, deg(u) + deg(v) n1, 則g是連通圖。證明證明 假設假設g不連通不連通, 則則g至少有兩個分圖至少有兩個分圖。設其中一個分圖含有設其中一個分圖含有q個頂點個頂點, 而其余各分圖共含有而其余各分圖共含有n q個頂點。個頂點。在這兩部分中各取一個頂點在這兩部分中

8、各取一個頂點u和和v, 則則0deg(u)q 1, 0deg(v)n q 1, 因此因此deg(u) + deg(v)n 2, 這與題設這與題設deg(u ) + deg(v)n 1矛盾。矛盾。圖的連通性：無向圖的連通性l 簡單圖是連通的當且僅當它具有生成樹。l p94 無向圖的連通塊數目判斷算法(1) i=1, f=1(2) 若頂點vai和vbi同屬于一個連通塊時轉(6)；否則轉(3)。(3)若頂點vai和vbi都不屬于任何一個連通塊，則用邊ei=建立一新連通塊，f=f+1，轉(6)(4)若頂點vai(或vbi ) 屬于第p個連通塊，但 vbi(或vai )不屬于任何一個連通塊，則邊ei=也

9、屬于第p個連通塊，轉(6)(5)若頂點vai和vbi分別屬于不同的兩個連通塊，則用邊ei=使這兩個不同連通塊連成一個連通塊，f=f-1，轉(6)(6) i=i+1, 若i1, 而刪除了s的任一真子集后得到的子圖是連通圖, 則稱s是g的一個點割集(cut-set of node)。l 切割點：若v g，將v點及與v點關聯的所有的邊從g中消去，余下的圖的連通塊數目增加了，則稱v點為切割點。 (cut-point)l 互連通圖：無切割點的連通圖叫做互連通圖。l 互連通塊：圖g的最大的互連通圖叫做互連通塊。例例 在上圖中在上圖中v2, v7, v3, v4為為點割集點割集, v3, v4均為均為割點割

10、點例例 在下圖中的在下圖中的v3和和v2都都是割點是割點, v2, v3,v4,v1, v2, v4,v5都都不不是點割集。是點割集。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e5連通塊劃分：利用dfs求切割點p110g=(v,e)是連通的無向圖，t是dfs樹，r是它的根結點，v是非根結點。根節(jié)點r為切割點，當且僅當r有多于一個兒子結點。非根結點v為切割點，當且僅當v的任一兒子結點w滿足：w不存在它的后裔結點（包括w）到v的祖先結點間的后退邊。vw1g1w2g2wsgsvw1g1w2g2wsgs連通塊劃分：利用dfs求切割點p110引進low(v)=minnum(w)|w t

11、(v)，其中t(v)是由v出發(fā)沿dfs樹t到達v的后裔結點u，最多通過一后退邊(u,w)到達的點w的集合。利用dfs搜索法對圖g的全部頂點和邊進行檢查過程，沿途留下low(v)的信息。搜索結束時，非根結點v是g的切割點的充要條件是v有兒子w，使得low(w)=num(v)vw1g1w2g2wsgs連通塊劃分：利用dfs求切割點p110(1)i=1, stack=.all v v 作【father(v)=0,mark(v)=0】(2)任選一點r滿足mark(r)=0,作【v=r, mark(v)=1, num(v)=i, low(v)=i 】(3)若所有與v點關聯的邊均已給出標志，則轉(5)；否

12、則任選一未給標志的邊(v,w)，給(v,w)邊以v到w的方向，并給以標志*表示通過檢查。并將(v,w)邊加到棧stack頂上，轉(4)。(4) 若mark(w)=0，則作【i+, low(w)=i , num(w)=i, mark(w)=1, father(w)=v, v=w ，轉(3) 】。若mark(w)=1，則作【low(v)=minlow(v), num(w) ，轉(3) 】(5)若father(v)!=0，則作 【若low(v)=num(father(v)，則作【從堆棧stack中移走邊(father(v),v)及其上棧中元素并輸出，轉(6)】，否則轉(6)】； 否則結束。 (6)l

13、ow(father(v)=minlow(v), low(father(v), v=father(v)， 轉(3)。圖的連通性：簡單有向圖的連通性一個有向圖一個有向圖g是強連通的是強連通的充要條件充要條件是是g中有一個中有一個回路回路, 它至少它至少包含每個頂點包含每個頂點一次。一次。證明證明 充分性充分性 如果如果g中有一個回路中有一個回路, 它它至少包含每個頂點一次至少包含每個頂點一次, 則則g中中任何兩個頂點都是相互可達任何兩個頂點都是相互可達的的, 即即g是強連通圖。是強連通圖。必要性必要性 若有向圖若有向圖g是強連通的是強連通的, 則則任何兩個頂點都是相互任何兩個頂點都是相互可達的可達

14、的, 所以必可作一個回路經過圖中所有各點。所以必可作一個回路經過圖中所有各點。否則必有一個回路否則必有一個回路不包含不包含某一頂點某一頂點v, 因而因而v與回路上的各與回路上的各頂點就頂點就不是相互可達不是相互可達的的, 與強連通條件矛盾。與強連通條件矛盾。圖的連通性：簡單有向圖的連通性 在簡單有向圖在簡單有向圖g中中,l (1) 若對若對g的邊不考慮方向的邊不考慮方向, 即把它看作無向圖是即把它看作無向圖是連通的連通的, 則稱則稱g是弱連通是弱連通(weakly connected)的的;l (2) 若對若對g中任意兩個頂點中任意兩個頂點u和和v, 或者或者u到到v有路有路, 或者或者v到到

15、u有路有路, 則稱則稱g是單向連通的是單向連通的(unilaterally connected);l (3) 若對若對g中任意兩個頂點中任意兩個頂點u和和v, u到到v有路且有路且v到到u有路有路, 則稱則稱g是強連通的是強連通的(strongly connected)。l 由定義可知由定義可知: 若圖若圖g是強連通的是強連通的, 則必是單向連通則必是單向連通的的; 若圖若圖g是單向連通的是單向連通的, 則必是弱連通的。但這則必是弱連通的。但這兩個命題兩個命題, 其逆不成立。其逆不成立。強連通塊的劃分l極大的強連通子圖稱為強連通塊。l強連通塊劃分算法p112-114最短通路問題l求帶權簡單連通

16、圖一點到另一點的最短通路dijkstra算法（離散數學及其應用p477l求一點到其他各點最短通路稍微修改dijkstra算法l求任意兩點間最短距離floyed算法圖的生成樹l圖的生成樹的應用道路掃雪ip組播連通簡單圖的生成樹生成算法：廣度優(yōu)先算法l 任意選取圖中一個頂點為根。然后添加與這個頂點相關聯的所有邊。在這個階段所添加的新頂點成為生成樹在1層上的頂點。任意地排序它們。l 下一步，按順序訪問一層上地每個頂點，只要不產生簡單回路，就添加與這個頂點相關聯地每條邊到樹里。這樣就產生了樹里在2層上地頂點。l 遵循相同的過程，直到已經添加了樹里的所有頂點。l 圖邊數有窮且連通，故這個過程以產生生成樹

17、而告終。連通簡單圖的生成樹生成算法：廣度優(yōu)先算法 例如，對右圖進行廣度優(yōu)先搜索遍歷的過程如圖(c)所示，得到的頂點訪問序列為 v1-v2-v3-v4-v5-v6-v7-v8 v8v5v4v6v7v1v3v2v1v3v6v7v5v2v4v8(c)連通簡單圖的生成樹生成算法：深度優(yōu)先算法l 任意選取圖中一個頂點為根。通過相繼地添加邊來形成在這個頂點上開始的通路，其中每條新邊都與通路上的最后一個頂點以及還不在通路上的一個頂點相關聯。繼續(xù)盡可能地添加邊到這條通路。l 若這條通路經過圖的所有頂點，則由這條通路組成地樹就是生成樹。否則，則必須添加其他的邊。后退到通路里的次最后頂點，若有可能，則形成在這個頂

18、點上開始的經過還沒有訪問過的頂點的通路。若不能這樣做，則再在通路里后退一個頂點，然后再試。重復這個過程，在所訪問過的最后一個頂點上開始，在通路上一次后退一個頂點，只要有可能就形成新的通路，直到不能添加更多的邊為止。l 圖邊數有窮且連通，故這個過程以產生生成樹而告終。連通簡單圖的生成樹生成算法：深度優(yōu)先算法 以下圖(a)中無向圖為例，深度優(yōu)先搜索遍歷圖的過程如圖(b)所示。 (a) 由此，得到頂點訪問序列為： v1-v2-v4-v8-v5-v3-v6-v7 (b)v8v5v4v6v7v1v3v2v5v8v7v6v4v3v2v1連通簡單圖的生成樹生成算法：深度優(yōu)先算法l如何生成所有的生成樹？（決策

19、樹）l本質：回溯連通簡單圖的生成樹生成算法：深度優(yōu)先算法l回溯應用舉例1、圖著色能否用3種顏色為右圖著色，使得相鄰頂點不同顏色？2、n皇后問題 在n*n棋盤上，如何放置n個皇后，使得沒有兩個皇后可以互相攻擊？（p102）連通簡單圖的生成樹生成算法：深度優(yōu)先算法l回溯應用舉例3、迷宮：求出在下面的迷宮里從標記x的出發(fā)位置到出口的通路1、圖著色 首先選擇某個頂點a并且指定它的顏色為1，然后挑選第二個頂點b，而且若b不與a相鄰，則指定它的顏色為1。否則，指定b顏色為2。然后來到第三個頂點c。若有可能，則對c用顏色1。否則，若有可能則用顏色2。只有當顏色1和顏色2都不能用時才應當用顏色3。 繼續(xù)這個過

20、程，只要有可能就指定n種顏色表中第一種允許的顏色給新頂點。若遇到不能用n種顏色中的任何一種來著色，則回溯到最后一次所做的指定，并且若有可能就改變最后著色的頂點的顏色，用顏色表中下一種允許的顏色。若不可能改變顏色，則再回溯到更前面的指定，一次后退一步，知道有可能改變一個頂點的顏色為止。然后只要有可能就繼續(xù)指定新頂點的顏色。圖著色能否用3種顏色為右圖著色，使得相鄰頂點不同顏色？2、n皇后問題l 從空棋盤開始，在k+1階段上，嘗試在棋盤上第k+1行里放置一個新的皇后，其中前k行里已經有了皇后。檢查第k+1行里的格子，從第一列的格子開始，尋找放置這個皇后的位置，使得它不與已經在棋盤上的皇后在同一行里或

21、在同一斜線上。l 若不可能在第k+1行里找到放置皇后的位置，則回溯到第k行里對皇后的放置。在這一行里下一個允許的列里放置皇后，若這樣的行存在的話。若沒有這樣的列存在，則繼續(xù)回溯。2、n皇后問題l可以把這個問題可能結果看成一個1，2，3，4的排列，如（1，4，3，2）表示第一行的第1列，第二行的第4列，第三行的第3列，第四行的第2列放置皇后。l可以將所有可能的排列用n元n層的搜索樹表示。l對該樹做深度優(yōu)先搜索，并在每一步檢查是否符合要求，不滿足則回溯。任何一條從根結點到葉子結點的路徑都是問題的解3、迷宮每一步的可能行動序列為1向左，2向上，3向右，4向下。每一步如果可能盡量按照行動序列次序執(zhí)行。

22、遇到走不通的時候看看是否有下個行動可執(zhí)行。如果沒有則回溯上一步，換用行動序列中的下個行動。連通簡單圖的生成樹生成算法：其他算法l教材p95：利用det(bkbkt)生成樹的清單l教材p96：利用基本割集多項式生成l教材p98：minty算法l教材p101：mayeda-seshu算法最小生成樹 問題背景： 假設要在n個城市之間建立通信聯絡網，則連通n個城市只需要n-1條線路。這時，自然會考慮這樣一個問題，如何在最節(jié)省經費的前提下建立這個通信網。 在每兩個城市之間都可以設置一條線路，相應地都要付出一定的經濟代價。n個城市之間，最多可能設置n(n-1)/2條線路，那么，如何在這些可能的線路中選擇n

23、-1條，以使總的耗費最少呢? 最小生成樹分析問題（建立模型）： 可以用連通圖來表示n個城市以及n個城市間可能設置的通信線路，其中圖的頂點表示城市，邊表示兩城市之間的線路，賦于邊的權值表示相應的代價。對于n個頂點的連通網可以建立許多不同的生成樹，每一棵生成樹都可以是一個通信網。現在，我們要選擇這樣一棵生成樹，也就是使總的耗費最少。這個問題就是構造連通網的最小代價生成樹(minimumcostspanningtree)(簡稱為最小生成樹)的問題。一棵生成樹的代價就是樹上各邊的代價之和。最小生成樹 構造最小生成樹可以有多種算法。其中多數算法利用了最小生成樹的下列一種簡稱為mst的性質： 假設g=(v

24、，e)是一個連通圖，u是頂點集v的一個非空子集。若 (u，v)是一條具有最小權值(代價)的邊，其中u u，vv-u，則必存在一棵包含邊 (u，v)的最小生成樹。最小生成樹 可以用反證法證明之： 假設圖g的任何一棵最小生成樹都不包含(u ,v)。設t是連通網上的一棵最小生成樹，當將邊(u，v)加入到t中時，由生成樹的定義，t中必存在一條包含(u,v)的回路。另一方面，由于t是生成樹，則在t上必存在另一條邊(u,v)，其中uu，vv-u，且u和u之間，v和v之間均有路徑相通。刪去邊(u, v)，便可消除上述回路，同時得到另一棵生成樹t，。因為(u，v)的代價不高于(u，v)，則t的代價亦不高于t，t是包含(u，v)的一棵最小生成樹。由此和假設矛盾。uvuvuv-u最小生成樹算法 解決方案： 普里姆(prim)算法和克魯斯卡爾(kruskal)算法是兩個利用mst性質構造最小生成樹的算法。 下面先介紹prim算法。 假設g=(v，e)是連通圖，te是n上最小生成樹中邊的集合。算法從u=u0(u0v)，te=開始，重復執(zhí)行下述操作：在所有uu，v v-u的邊(u，v) e中找一條代價最小的邊(u0 ，v