圖論中常用經(jīng)典算法

圖論中的常用經(jīng)典算第一節(jié)最小生成樹算一、生成樹的概若圖是連通的無向圖或強(qiáng)連通的有向圖，則從其中任一個(gè)頂點(diǎn)出發(fā)調(diào)用一次bfs或dfs后便可以系統(tǒng)地圖中所有頂點(diǎn)；若圖是有根的有向圖，則從根出發(fā)通過調(diào)用一次dfs或bfs亦可系統(tǒng)地所有頂點(diǎn)。在這種情況下，圖中所有頂點(diǎn)加上遍歷過程中經(jīng)過的邊所構(gòu)成的子圖稱為bfs或dfs后不能系統(tǒng)地所有頂點(diǎn)，而只能得到以出發(fā)點(diǎn)為根的連通分支（或強(qiáng)連通分支）的生成樹要其它頂點(diǎn)則還需要從沒有過的頂點(diǎn)中找一個(gè)頂點(diǎn)作為起始點(diǎn)再次調(diào)用bfsdfs但不管如何，都可以證明：具有n個(gè)頂點(diǎn)的帶權(quán)連通圖，其對應(yīng)的生成樹有n-1條邊二、求圖的最小生成樹算嚴(yán)格來說，如果圖G=（V，E）是通的無向圖，則把它的全部頂點(diǎn)V和一部分邊E’構(gòu)GEG對于連通圖，生成樹的權(quán)即為生成樹中所有邊上的權(quán)值總和，權(quán)值最小的生成樹稱為圖例1、城市

以下e3i,j,wiji,j下面的圖（）5（B（C）（A）03，19。出發(fā)點(diǎn)：具有n個(gè)頂點(diǎn)的帶權(quán)連通圖，其對應(yīng)的生成樹有n-1那么選哪n-1條邊呢？設(shè)圖G的度為n，G=（V，E，介紹兩種基于貪心的算法，Prim算法Kruskal法。1、用Prim算法求最小生成樹的思想如下（X，YYS，邊（X，Y）TE；T其中圖（E）中的4條粗線將5個(gè)頂點(diǎn)連通成了一棵最小生成樹。Prim算法的正確性可以通過反PrimelistFori:=1Ton-1Don-1Fork:=1Ton-1DoForj:=kTon-1 Ifelist[j].weight<minThenBeginmin:=elist[j].weight；m:=j；End；Ifm<>kThenBeginj:=elist[k].endv；{jFori:=k+1Ton-1Do{修改未加入的邊集}Begins:=elist[i].endv；w:=g[j,s]；IfThenBegin2、用Kruskal算法求最小生成樹的思想如下設(shè)最小生成樹為T=（V，TE，設(shè)置邊的集合TE的初始狀態(tài)為空集。將圖G中的邊按權(quán)值從TTE中，保留作為T的一條邊；若選取的邊使生成樹形成回路，則將其舍棄；如此進(jìn)行下去，直到TEn-1TKruskal保留的邊形成回路？可以將頂點(diǎn)劃分到不同的集合中，每個(gè)集合中的頂點(diǎn)表示一個(gè)無回路的連通分量，很明顯算法開始時(shí)，把所有n個(gè)頂點(diǎn)劃分到n個(gè)集合中，每個(gè)集合只有一個(gè)頂點(diǎn)，表此這條邊應(yīng)該保留，且把它們作為通分量，即把它的兩個(gè)頂點(diǎn)所在集合合并成一個(gè)集合。Kruskal①將圖的結(jié)構(gòu)轉(zhuǎn)換成邊集數(shù)組表示的形式elist，并按照權(quán)值從小到大排好序S[1..n]，S[iS[i]=ii:=1iWhilei<=n-1DoFork:=1TonDoBegin Ifelist[j].fromvins[k] Thenm1:=k；Ifelist[j].endvins[k]Thenm2:=k；Ifm1<>m2Then elistjis[m2]:=[ 3、總以上兩個(gè)算法的時(shí)間復(fù)雜度均為O（n*n。參考程序Prim.pasKruskal.pas。請大家用以上兩種算法完成1。三、應(yīng)用舉n往是不同的。當(dāng)然，如果將任意兩臺計(jì)算機(jī)都用數(shù)據(jù)線連接，費(fèi)用將是相當(dāng)龐大的。為了節(jié)省費(fèi)用，（2<=n<=1003012101210，本題是典型的求圖的最小生成樹問題可以利用Prim算法或者Kruskal算法求出下Kruskal，Programwire(Input,vargArray[1..100,1..100]OfIntegerlArray0..100]Of u:Array[0..100]OfBoolean； {u[i]=True，表示頂點(diǎn)i還未加入到生成樹中；n,i,j,k,total:Integer；Assign(Input,Assign(Output,'wire.out')；Fori:=1TonDoForj:=1TonDoRead(g[i，j])；Fillchar(l,sizeof(l),$7F)；l[1]:=0； Fillchar(u,sizeof(u),1)； Fori:=1TonDok:=Forj1Ton Ifu[j]And(l[j]l[k])Thenkj；u[k]:=False； Forj:=1TonDo Ifu[j]And(g[k，j]<l[j])Thenl[j]:=g[k，j]；total:=0；Fori:=1TonDoInc(total,l[i])； 第二節(jié)最短路徑算等難度的題目，這類問題很能聯(lián)系實(shí)際，學(xué)生的建模能力，反映出學(xué)生的創(chuàng)造性思維，因?yàn)樵趲?quán)圖G=（V，E）中，若頂點(diǎn)Vi,Vj是圖G個(gè)頂點(diǎn)，從頂點(diǎn)ViVj的路徑長度定義為路徑上各條邊的權(quán)值之和。從頂點(diǎn)Vi到Vj可能有多條路徑，其中路徑長度最小的一條路徑稱為頂點(diǎn)Vi到Vj的最短路徑。一般有兩類最短路徑問題：一類是求從某個(gè)頂點(diǎn)（源點(diǎn)）到其它頂例1、假設(shè)A、B、C、D、E各個(gè)城市之間旅費(fèi)如下圖所示。想從城市A出發(fā)游覽各城市一遍，實(shí)際上知道，遞歸（深搜）之類的算法一般用于求所有解問題（例如求從A出發(fā)每個(gè)城市都要走一遍一共有哪幾種走法？的。constdis:array[1..5,1..5]ofinteger=(((0,6,(10,13,6,(15,12,5,11,0)一、寬度優(yōu)先搜索1、從AAB、AC、AD、AE（第二層結(jié)點(diǎn)，當(dāng)然每個(gè)新結(jié)點(diǎn)2、再次由AB展開得到ABC、ABD、ABE三個(gè)新結(jié)點(diǎn)（第三層結(jié)點(diǎn)而由AC結(jié)點(diǎn)可展開得到ACB、ACD、ACE三個(gè)新結(jié)點(diǎn)，自然由AD可以展開得到ADB、ADC、ADE，由AE可以展開得到AEB、AEC、AED3：ABCD、ABCE、ABDC、ABDE、ABEC5、到此，所有可能的結(jié)點(diǎn)均已展開，而第五層結(jié)點(diǎn)中旅費(fèi)最少的那個(gè)就是題目的解了。A＊算A*算法。三、等代價(jià)搜索A＊算法的相AB（7AC（3AD（10A（括號中的數(shù)字；2、把未展開過的AB、AC、AD、AE四個(gè)結(jié)點(diǎn)中距離最小的一個(gè)展開，即展開AC（3）結(jié)點(diǎn)，ACB（8ACD（163、再從未展開的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開即展開AB（7）結(jié)點(diǎn)得到AB（12ABD（20、ABE（19）AB4ACB（8）5A＊原則（或某一估價(jià)函數(shù)值）A（那個(gè)結(jié)點(diǎn)展開并不是大規(guī)模的，不是全部展開，因而耗時(shí)要比寬度優(yōu)先搜索小得多。例2、題目基本同例1，現(xiàn)在把權(quán)定義成距離，現(xiàn)在要求A點(diǎn)到E點(diǎn)的最短路徑，但并不要求每到什么時(shí)候才能得到答案呢？這個(gè)很荊手的問題。EE不對。實(shí)際上，應(yīng)該是搜索到：當(dāng)確定將要展開的某個(gè)結(jié)點(diǎn)（即所有未展開的結(jié)點(diǎn)中距離最小的那個(gè)點(diǎn)）的最后一個(gè)字母是E時(shí)，這個(gè)結(jié)點(diǎn)就是所要求的答案！因?yàn)楸冗@個(gè)結(jié)點(diǎn)大的點(diǎn)四、寬度優(yōu)先搜索+剪效率的關(guān)鍵在于減少無意義的搜索。假如在搜索時(shí)已經(jīng)搜出從起點(diǎn)A到點(diǎn)B的某一條路徑的長度是X，那么就可以知道，從A到B的最短路徑長度必定≤X，因此，其他從A到B的長度大于或等于X的路徑可以一律剔除。具體實(shí)現(xiàn)時(shí)，可以開一個(gè)數(shù)組h[1..n]，n是結(jié)點(diǎn)總數(shù)，h[i]表示i1將起點(diǎn)start入隊(duì)，h[start]:=0，h[k]:=maxlongint(1<=k<=n，且k≠start)。whileth[t]+w[t,newp]until maxint=maxlongintdiv4; h:array[1..maxn]oflongint;g:array[1..maxn,1..maxn]oflongint;procedurevarhead,tail,i,t:longint;q:array[1..maxq]oflongint;fori:=1tondoh[i]:=maxint;fori:=1tonif(g[t,i]<>maxint)and(h[t]+g[t,i]<h[i])

untilhead=tail;

fori:=1tonforj:=1tondo

if(g[i,j]<=0)and(i<>j)then

fori:=2tonwrin('From1To',i,'Weigh',h[i]);五、迭代該算法的中心思想是：任意兩點(diǎn)i,j間的最短距離（記為Dij）會等于從i點(diǎn)出發(fā)到達(dá)j點(diǎn)DijminDijDik+Dkj}，1<=k<=n這樣，就找到了一個(gè)類似動(dòng)態(tài)規(guī)劃的表達(dá)式，只不過這里不把它當(dāng)作動(dòng)態(tài)規(guī)劃去處A到E1、D[i]:=g[s,i](1<=i<=n)；c:=false;Dijforj:=1tondofork:=1tonifD[j]>D[k]+g[k,j]beginD[j]:=D[k]+g[k,j]; c:=true;end;Untilnotc； maxint=maxlongintdiv4; D:array[1..maxn]oflongint;g:array[1..maxn,1..maxn]oflongint;

fori:=1tonforj:=1tondo

if(g[i,j]<=0)and(i<>j)thenfori:=1tondoD[i]:=g[1,i];forj:=1tonfork:=1tondo ifD[j]>D[k]+g[k,j]thenuntilnot

fori:=2tonwrin('From1To',i,'Weigh',D[i]);六、動(dòng)態(tài)規(guī)性就。遞歸：類似只能找到這樣一個(gè)不確定關(guān)系的表達(dá)式，f(n)的值是動(dòng)態(tài)的，隨著f(n-1),f(n-2)等值的改變而譬如下兩個(gè)有向圖B9B9C3A2548D1EB9C3A2548D1EA、B、D、C、E。F(E)AEF(B)=min{F(A)}+3=3F(D)=min{F(A)+8,F(B)+2}=5F(C)=min{F(B)+9,F(D)+5F(E)=min{F(D)+1,F(C)+4總的式子是：F(i)=min{F(k)+dis(i,k)ki，kiconstmaxint=maxlongintdiv g:array[1..maxn,1..maxn]oflongint;{有向圖的鄰接矩陣}pre:array[1..maxn]oflongint;{pre[i]記錄結(jié)點(diǎn)i的入度}tp:array[1..maxn]oflongint;{拓?fù)渑判虻玫降男蛄衹s:array[1..maxn]oflongint;

fori:=1tondoforj:=1tondoifg[i,j]>0pre[j]:=pre[j]+1;i→jjfori:=1tondo{拓?fù)渑判騷while(pre[j]<>0)doj:=j+1;{找入度為0fork:=1tonifg[j,k]>0thenfilldword(s,sizeof(s)div4,maxint);{s數(shù)組中的單元初始化為maxint} {默認(rèn)起點(diǎn)是1號結(jié)點(diǎn)}fori:=2tondo forj:=1toidoif(g[tp[j],tp[i]]>0)and

fori:=2tonwrin('From1To',i,'Weigh',s[i]);七、標(biāo)號標(biāo)號法是一種非常直觀的求最短路徑的算法，單從分析過程來看，可以用一個(gè)數(shù)軸簡單1、以A02、因?yàn)镃點(diǎn)離起點(diǎn)A最近，因此可以斷定C一定是由A直接到C這條路徑是最短的（因?yàn)锳、C兩點(diǎn)間沒有其它的點(diǎn)，所以C點(diǎn)可以確定是由A點(diǎn)直接到達(dá)為最短路徑。因而就可以以CCA'、B'、D'、E'。5、由上圖可以得出結(jié)論：點(diǎn)C、B、D、E就是點(diǎn)A到它們的最短路徑（注意：這些路徑并不A到E13。至于它經(jīng)過了哪幾個(gè)點(diǎn)大家可在上述過程中加以記錄即可。 maxint=maxlongintdiv g:array[1..maxn,1..maxn]oflongint;{鄰接矩陣}mark:array[1..maxn]ofboolean; s:array[1..maxn]oflongint; {最短路徑長度}

fori:=1tonforj:=1tondoif(i<>j)and(g[i,j]=0)then mark[1]:=true;{將起點(diǎn)標(biāo)志為已擴(kuò)展}fori:=1tondos[i]:=g[1,i];{sforj:=1tondoif(notmark[j])and((k=0)or(s[k]>s[j]))thenifk<>0thenuntilk=0;

forj:=1ton if(notmark[j])and(s[k]+g[k,j]<s[j])then

fori:=2tonwrin('From1To',i,'Weigh',s[i]);八、Dijkstra算法（從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑，單源最短路徑例3、如下圖，假設(shè)C1,C2,C3,C4,C5,C6是六座城市，他們之間的連線表示兩城市間有道路相通，連線旁的數(shù)字表示路程。請編寫一程序，找出C1到Ci的最短路徑(2≤i≤6)，輸出路徑序列及最短對于一個(gè)含有n個(gè)頂e條邊的圖來說從某一個(gè)頂點(diǎn)Vi到其余任一頂點(diǎn)Vj的最短路徑，可能是它們之間的（ViVj也可能是經(jīng)過k中間頂點(diǎn)和k+1條邊所形成的路徑(1≤k≤n-2)。下面給出解決這個(gè)問題的Dijkstra算法思想。值（0SS=[Vi]j用來當(dāng)前求得的最短路徑，初始時(shí)Vij如果是聯(lián)的，則dist[j]等于值，否則等maxint，dist[j]distpath[1..n]iVj執(zhí)行時(shí)，先從S以外的頂點(diǎn)（即待求出最短路徑的終點(diǎn)）所對應(yīng)的dist數(shù)組元素中，找出其dist[m]path[m]中的頂點(diǎn)或邊的序列即為最短路徑接著把Vm并入集合SVm作為新考慮的中間頂點(diǎn)，對S以外的每個(gè)頂點(diǎn)Vj，比較dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加dist[j]，同時(shí)把Vj或邊（Vm，Vj）并入到path[j]中。重復(fù)以上過程n-2次，即可在dist數(shù)組中得到從源點(diǎn)到其path對于上圖，采用Dijkstra算法找出C1到Ci之間的最短路徑(2≤i≤6)的過程如下：1234560481234560478123456047891234560478912345604789C1到C2的最短路徑為：C1——C2，長度為C1到C3的最短路徑為：C1——C2——C3C1到C4的最短路徑為：C1——C2——C4C1到C5的最短路徑為：C1——C2——C3——C5，長度為C1到C6的最短路徑為：C1——C2——C3——C5——C6下面給出具體的Dijkstra算法框架（注：為了實(shí)現(xiàn)上的方便，用一個(gè)一維數(shù)組s[1..n]代替集合S，用來保存已求得最短路徑的終點(diǎn)集合，即如果s[j]=0表示頂點(diǎn)Vj不在集合中，反之，s[j]=1Vj。ProcedureDijkstra(GA,dist,path,i)；{表示求Vi到圖G中其余頂點(diǎn)的最短路徑，GA為G，distpathpathForj:=1TonDo Ifj<>iThenElses[j]:=1；Ifdist[j]<maxint Thenpath[j]:=[i]+[j]Elsepath[j]:=[]；Fork:=1Ton-2DoForj:=1Ton {求出第kIf(s[j]=0)and(dist[j]<w) Beginm:=j；w:=dist[j]；Ifm<>iThens[m]:=1elseexitVmSmaxint，無需再計(jì)算下去}Forj:=1TonDo If(s[j]=0)and(dist[m]+GA[m,j]<dist[j])Then九、Floyed算例4、求任意一對頂點(diǎn)之間的最短路這個(gè)問題的解法有兩種一是分別以圖中的每個(gè)頂點(diǎn)為源點(diǎn)共調(diào)用n次Dijkstra算法的時(shí)間復(fù)雜度為O（n3；另外還有一種算法：Floyed算法，它的思路簡單，但時(shí)間復(fù)雜度仍O(shè)（n3Floyed設(shè)具有n頂點(diǎn)的一個(gè)帶權(quán)圖G鄰接矩陣用GA表示，再設(shè)一個(gè)與GA類型的表示每對頂點(diǎn)之間最短路徑長度的二維數(shù)組A，A的初值等于GA。Floyed算法需要在A上進(jìn)行n次運(yùn)算，每次以Vk（1≤k≤n）作為新考慮的中間點(diǎn)，求出每對頂點(diǎn)之間的當(dāng)前最短路徑長度，最后依次運(yùn)算后，A中的每個(gè)元素A[i，j]就是圖G中從頂點(diǎn)Vi到頂點(diǎn)Vj的最短路徑長度。再設(shè)一個(gè)二維數(shù)P[1..n,1..n]，setof1..n。ProcedureFloyed(GA，A，P)；Fori:=1TonDo{最短路徑長度數(shù)組和最短路徑數(shù)組初始化}Forj:=1TonDoIf ThenElsep[i,j]:=[Fork:=1TonDo Fori:=1TonDoForj:=1TonDoIf(i=k)or(j=k)or(i=j)ThenIfA[i,k]+A[k,j]<A[i,j]Then A[i,j]：=P[i,j]：=P[i,k]+P[k,j]；Floyed其長度。十、總結(jié)與如果有向圖出現(xiàn)了回路，按照最長路徑的思想和判斷要求，則計(jì)算可能沿著回路的循環(huán)下去。這就引出了一個(gè)問題：如何判斷一個(gè)有向圖中是否存在回路？可以用bfs或dfs在搜的過程第三撲排序算子工程（活動(dòng)）完成之后才能開始，可以用有向圖來形象地表示這些子工程（活動(dòng)）之間的“AOVAOV（活動(dòng)）VijVijVjVi<ViVj>iVjVjiAOV造成環(huán)中的活動(dòng)都無法進(jìn)行。AOVAOV拓?fù)湫蛄校?43657、0123567。AOV12412314534647要等到工程3、工程5、過程6都完成后才能進(jìn)行?？梢娪葾OV網(wǎng)構(gòu)造拓?fù)湫蛄芯哂泻芨叩膶?shí)際只要選擇一個(gè)入度為0后從AOV網(wǎng)中刪除此頂點(diǎn)及以此頂點(diǎn)為起點(diǎn)的所有關(guān)聯(lián)邊；重復(fù)上述兩步，直到不存在入度為的頂點(diǎn)為止，若輸出的頂點(diǎn)數(shù)小于AOV序列就是一種拓?fù)湫蛄小?輸出 2， 輸出 輸出 6， 6， 輸出 輸出 m=8，AOVn=8：01243567。為了算法實(shí)現(xiàn)上的方便，采用鄰接表AOV網(wǎng)，不過稍做修改，在頂點(diǎn)表中增加一個(gè)ProcedureTopSort(dig:graphlist)；{用鄰接表dig圖G} n,top,i,j,k,m:Integer； Fori:=1Ton {對入度為0的所有頂點(diǎn)進(jìn)行，序號壓棧Ifdig.adj[i].id=0Then Whiletop<>0 {取一個(gè)入度為0的頂點(diǎn)序號} Write(dig.adj[top].v)；{輸出頂點(diǎn)序號} {指向Vj鄰接表的第一個(gè)鄰接點(diǎn)}Whilep<>nil {刪除所有與Vj相關(guān)邊} dig.adj[k].id:=dig.adj[k].id-1； Ifdig.adj[k].id=0ThenBegin

Ifm<nThenWrin(‘no 思考：拓?fù)渑判蛞话阌迷谀男﹫龊辖獯穑喝缗谢芈坊驁D的動(dòng)態(tài)規(guī)劃過程中分階段例1、士兵排隊(duì)（soldier）有n個(gè)士（1≤n2，依次為A、BC……隊(duì)列練時(shí)，指揮官要把一些士兵從高到矮依次排成一行。但現(xiàn)在指揮官不能直接獲得每個(gè)人的身高信息，只能獲得“p12這樣的比較結(jié)果（p12∈{'A'，，'Z'}p1>p2A>BB>，F(xiàn)>D系：（soldier.in）第二至第k+1行：每行兩個(gè)大寫字母（中間和末尾都沒有空格代表兩個(gè)士兵，且第一個(gè)士輸出（soldier.out）一個(gè)只包含大寫字母的字符序列，表示排隊(duì)方案（只要案即可輸入樣例（soldier.in）3輸出樣例（soldier.out）問題分析士兵的身高關(guān)系對應(yīng)一張有向圖，圖中的頂點(diǎn)對應(yīng)一個(gè)士兵，有向邊<vi，vji于士兵j。按照從高到矮將士兵排出一個(gè)線形的順序關(guān)系，即為對有向圖的頂點(diǎn)進(jìn)行拓?fù)渑艆⒖汲绦騪rogram g:array['A'..'Z','A'..'Z']of0..1;{圖的鄰接矩陣}d:array['A'..'Z']oflongint; s:array['A'..'Z']ofboolean; procedurereadata; vari,j,k:longint; fori:=1tokdo {將b begin whil