圖論相關算法課件

圖論

（ElementaryGraphAlgorithms）圖論

（ElementaryGraphAlgor1圖的定義圖是由頂點集合以及頂點間的關系的集合組成的一種關系的數學表示

G=（V，E）其中頂點是由有窮非空集合頂點之間的關系（邊）是有窮集合Path(x,y)表示從x到y的一條單向通路，它是有方向的圖的定義圖是由頂點集合以及頂點間的關系的集合組成的一種關系的2圖的分類有向圖：圖中的邊是有方向的。E(x,y)和E(y,x)表示的邊不同無向圖：圖中的邊是沒有方向的。完全圖：n個頂點的圖兩兩連邊，即有n(n-1)/2條邊，則此圖為n的完全圖。用Kn表示圖的分類有向圖：圖中的邊是有方向的。E(x,y)和E3圖的一些概念鄰接頂點：如果(u,v)∈E(G),則稱u與v互為鄰接頂點子圖：設有兩個圖G(V,E)和G’(V’,E’)，若V’V且E’E’，則稱圖G‘是圖G的子圖權：某些圖的邊上標有相關的數字，稱為該邊的權值圖的一些概念鄰接頂點：如果(u,v)∈E(G),則稱u與4頂點的度一個頂點V的度是與它相連邊的條數，記為Deg(V).頂點的入度一個頂點V的入度是以它為終點有向邊的條數，記為InDeg(V)頂點的出度一個頂點V的入度是以它為起點有向邊的條數，記為OutDeg(V)路徑在圖G＝(V,E)中,若從頂點vi出發(fā),沿一些邊經過一些頂點Vp1,Vp2,…,Vpm，到達頂點Vj。則稱頂點序列(ViVp1Vp2...VpmVj)為從頂點Vi到頂點Vj的路徑。它經過的邊(Vi,Vp1)、(Vp1,Vp2)、...、(Vpm,Vj)應是屬于E的邊。頂點的度一個頂點V的度是與它相連邊的條數，記為Deg(V5圖的存儲表示

鄰接矩陣(AdjacencyMatrix)設圖G=(V,E)是一個有N個頂點的圖，圖的鄰接矩陣是一個二維數組G.edge[N][N]定義：G.edge[i][j]=1If(i,j)∈E(G)0otherwise圖的存儲表示

鄰接矩陣(60213G.edge[i][j]=01001000012G.edge[i][j]=0111100010011010無向圖的臨界矩陣是對稱的有向圖的鄰接矩陣往往是不對稱的0213G.edge[i][j]=0100127圖的存儲表示

鄰接表(AdjacencyList)0213010023320123∧∧∧∧

Dataadjdestlinkdestlinkdestlink

同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結點代表一條邊，結點中另一個頂點的下表dest和指針link圖的存儲表示

鄰接表(Ad8圖論相關算法圖論相關算法9廣度優(yōu)先搜索通常用隊列(先進先出,FIFO)實現 Q={起點s};標記s為己訪問; while(Q非空){ 取Q隊首元素u;u出隊; 所有與u相鄰且未被訪問的點進入隊列; 標記u為已訪問; }廣度優(yōu)先搜索通常用隊列(先進先出,FIFO)實現10廣度優(yōu)先搜索由BFS得到的路徑是原圖中從S到T的邊數最少的路徑廣度優(yōu)先搜索樹不唯一廣度優(yōu)先搜索由BFS得到的路徑是原圖中從S到T的邊數最少的路11廣度優(yōu)先搜索的例子012543678012543678012543678

012112243

廣度優(yōu)先搜索的例子01254367801254367801212t=0;voidBFS(ints) //從s開始遍歷{

intqueue[maxn],tail,head;head=tail=0;queue[head]=s;depth[s]=0;time[s]=t++;visit[s]=true;

while(head<=tail) //queuenotempty{

intcurr=queue[head++];

inti;

for(i=0;i<n;i++)

if(adj[curr][i]&&!visit[i]) { visit[i]=true; depth[i]=depth[curr]+1; time[i]=t++; queue[++tail]=i; }}}t=0;13深度優(yōu)先搜索相關概念遞歸實現結點顏色：白色（開始），灰色（發(fā)現），黑色（結束）一個結點總是從白色變?yōu)榛疑?，再變?yōu)楹谏斔悬c都變?yōu)楹谏珪r，遍歷結束時間戳(timestamp):d[u]表示一個結點開始被訪問的時間，f[u]表示一個結點結束訪問的時間深度優(yōu)先搜索相關概念14深度優(yōu)先搜索inttimestamp=0;dfs(intp){ timestamp=timestamp+1; col[p]=GREY; d[p]=timestamp; for(每個與p相鄰的點i) if(col[i]==WHITE)dfs(i); timestamp=timestamp+1; f[p]=timestamp; col[p]=BLACK;}深度優(yōu)先搜索inttimestamp=0;15圖論相關算法課件16深度優(yōu)先搜索每個頂點的d[u]<f[u]DFS中，v是u的子孫d[u]<d[v]<f[v]<f[u]在搜索中發(fā)現u時可以從u出發(fā)沿一條完全由白色頂點組成的路徑到達vm條邊的連通圖，DFS中順序標號每條邊為1~m，則任意與頂點u關聯的所有邊（邊數>=2）的標號的GCD為1深度優(yōu)先搜索每個頂點的d[u]<f[u]17深度優(yōu)先搜索割點與割邊如果從圖中刪去某點和與該點相關聯的邊后，圖不再連通，那么這個點叫做割點(cutpoint)。如果從圖中刪去某條邊后，圖不再連通，那么這條邊叫做割邊或橋(bridge)。深度優(yōu)先搜索割點與割邊18關節(jié)點：圖中的關節(jié)點指這樣一個頂點，如果刪除它，圖就會被分割成至少兩個分離的子圖。關節(jié)點也稱作分離頂點或割點。0123456789101112頂點0、4、5、6、7和11為關節(jié)點。關節(jié)點：圖中的關節(jié)點指這樣一個頂點，如果刪除它，圖就會被分割19割點、割邊以及連通分量時間戳：dfn[i]表示結點i是第dfn[i]個被訪問到的結點。有的時候我們還要記錄某個結點被遍歷并檢查完畢的時間。voiddfs(v){ dfn[v]=++times;//記錄訪問結點的時間戳 visit[v]=1; for尋找一個v的相鄰節(jié)點u if(visit[u]==0)then DFS(u);}割點、割邊以及連通分量時間戳：dfn[i]表示結點i是第df20LMABCFIDGJEHKABLFMJCHKGIDE連通圖GG的深度優(yōu)先生成樹LMABCFIDGJEHKABLFMJCHKGIDE連通圖G21樹邊：深度優(yōu)先搜索樹中的實線表示樹邊，在DFS過程中，從v點訪問u點時，若u沒有被訪問過，則邊(v,u)為樹邊?；剡叄荷疃葍?yōu)先搜索樹中的虛線表示回邊，在DFS過程中，從v點訪問u點時，若u點已經訪問過，則邊(v,u)為回邊。ABLFMJCHKGIDE樹邊：深度優(yōu)先搜索樹中的實線表示樹邊，在DFS過程中，從v點22由深度優(yōu)先生成樹可得出兩類關節(jié)點的特性：(1)若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為關節(jié)點。因為圖中不存在聯結不同子樹中頂點的邊，因此，若刪去根頂點，生成樹便變成生成森林。如上圖中的頂點A。(2)若生成樹中某個非葉子頂點v，它的子樹中的任一結點均沒有指向v的祖先的回邊，則v為關節(jié)點。因為，若刪去v，則其子樹和圖的其他部分就被分割開來。如上圖中的頂點B、D和G。由深度優(yōu)先生成樹可得出兩類關節(jié)點的特性：(1)若生成樹的根23我們在DFS的基礎上增加一個low數組，low[i]用來記錄i及i的子孫相連的輩分最高的祖先的訪問時間戳。low[v]=min(dfn[v],low[w],dfn[k]);w是頂點v在深度優(yōu)先樹上的孩子結點；k是頂點v在深度優(yōu)先樹上由回邊聯結的祖先結點；我們在DFS的基礎上增加一個low數組，low[i]用來記錄24當low[j]<dfn[i](j是i的兒子)時，說明j或者j的子孫中存在指向i祖先的回邊。反之，若對于某個頂點v，存在孩子結點w，且low[w]>=dfn[v],表明w及其子孫均無指向v的祖先的回邊，則該頂點v必為關節(jié)點。具體算法如下：當low[j]<dfn[i](j是i的兒子)時，說明j或者j25voiddfs(intv){inti,w,cnum=0;//cnum表示孩子個數times++;visit[v]=1;dfn[v]=low[v]=times;//記錄時間戳for(i=0;i<map[v].size();i++){ w=map[v][i]; if(!visit[w])//w沒有訪問過，則w是v的孩子結點 { cnum++; dfs(w); low[v]=min(low[w],low[v]); if(v==root&&cnum==2)//如果v是根，且有2個以上的孩子，則為關節(jié)點 flag[v]=1; if(v!=root&&low[w]>=dfn[v])//不為根若low[w]>=dfn[v])，則為關節(jié)點 flag[v]=1; } elseif(v!=w)//w已經訪問過了，說明從v到w有一條回邊，w是v的祖先 { low[v]=min(low[v],dfn[w]); }} }voiddfs(intv)26橋：圖中的橋（bridge）是一條邊，如果刪除這條邊，將把連通圖分離成兩個斷開的子圖。無橋的圖稱作邊連通圖（edge-connectedgraph）。0123456789101112這個圖不是邊連通圖。邊0-5、6-7和11-12（帶陰影）為橋。橋：圖中的橋（bridge）是一條邊，如果刪除這條邊，將把連27在任何DFS樹中，當且僅當不存在回邊連通w的子孫與w的祖先時，樹邊v-w是一座橋。與割點類似的，我們定義low[]和dfn[]。父子邊e=u→v，當且僅當low[v]>dfn[u]的時候，e是割邊。在任何DFS樹中，當且僅當不存在回邊連通w的子孫與w的祖先時28有向圖的強連通分量在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通(stronglyconnected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。非強連通圖有向圖的極大強連通子圖，稱為強連通分量(stronglyconnectedcomponents)。下圖中，子圖{1,2,3,4}為一個強連通分量，因為頂點1,2,3,4兩兩可達。{5},{6}也分別是兩個強連通分量。有向圖的強連通分量在有向圖G中，如果兩個29求有向圖的強連通分量一般采用Kosaraju算法或Tarjan算法，兩者的時間復雜度都是O(n+m)。下面著重介紹一下Tarjan算法。[Tarjan算法]Tarjan算法是基于對圖深度優(yōu)先搜索的算法，每個強連通分量為搜索樹中的一棵子樹。dfs時，把當前搜索樹中未處理的節(jié)點加入一個堆棧，回溯時可以判斷棧頂到棧中的節(jié)點是否為一個強連通分量。求有向圖的強連通分量一般采用Kosaraju算法或Tarja30我們仍然定義dfn[i]為節(jié)點i搜索的次序編號(時間戳)，low[i]為i或i的子樹能夠追溯到的最早的棧中節(jié)點的次序號。由定義可以得出:當dfn(u)=low(u)時，以u為根的搜索子樹上的所有節(jié)點構成一個強連通分量。我們仍然定義dfn[i]為節(jié)點i搜索的次序編號(時間戳)，l31voidtarjan(inti){intj;dfn[i]=low[i]=++times;

//為節(jié)點u設定次序編號和Low初值instack[i]=true;Stack[++Stop]=i;//將節(jié)點u壓入棧中for(edge*e=V[i];e;e=e->next){j=e->t;if(!dfn[j]){ tarjan(j); if(low[j]<low[i]) low[i]=low[j];}elseif(instack[j]&&dfn[j]<low[i]) low[i]=dfn[j];}if(dfn[i]==low[i])//如果節(jié)點i是強連通分量的根{Bcnt++;do{ j=Stack[Stop--]; instack[j]=false; Belong[j]=Bcnt;}while(j!=i);}}voidsolve(){inti;Stop=Bcnt=times=0;memset(dfn,0,sizeof(dfn));for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);}voidtarjan(inti)32從節(jié)點1開始DFS，把遍歷到的節(jié)點加入棧中。搜索到節(jié)點u=6時，dfn[6]=low[6]=4，找到了一個強連通分量。退棧到u=v為止，{6}為一個強連通分量。從節(jié)點1開始DFS，把遍歷到的節(jié)點加入棧中。搜索到節(jié)點u=633返回節(jié)點5，發(fā)現dfn[5]=low[5]=3，退棧后{5}為一個強連通分量。返回節(jié)點5，發(fā)現dfn[5]=low[5]=3，退棧后{5}34返回節(jié)點3，繼續(xù)搜索到節(jié)點4，把4加入堆棧。發(fā)現節(jié)點4存在向節(jié)點1的回邊，節(jié)點1還在棧中，所以low[4]=dfn[1]=1。節(jié)點6已經出棧，不再訪問6，返回3，(3,4)為樹邊，所以low[3]=low[4]=1。返回節(jié)點3，繼續(xù)搜索到節(jié)點4，把4加入堆棧。發(fā)現節(jié)點4存在向35繼續(xù)回到節(jié)點1，最后訪問節(jié)點2。訪問邊(2,4)，4還在棧中，所以low[2]=4。返回1后，發(fā)現DFN[1]=LOW[1]，把棧中節(jié)點全部取出，組成一個連通分量{1,3,4,2}。至此，算法結束。經過該算法，求出了圖中全部的三個強連通分量{1,3,4,2},{5},{6}。繼續(xù)回到節(jié)點1，最后訪問節(jié)點2。訪問邊(2,4)，4還在棧中36[Kosaraju算法]Kosaraju是基于對有向圖及其逆圖兩次DFS的方法，其時間復雜度也是O(N+M)。kosaraju算法的步驟如下：(1)在有向圖G上，從某個頂點出發(fā)進行DFS，并按其所有鄰接點的搜索都完成(即退出DFS函數)的順序將頂點排列起來。[Kosaraju算法](1)在有向圖G上，從某個頂點出發(fā)37[Kosaraju算法]Kosaraju是基于對有向圖及其逆圖兩次DFS的方法，其時間復雜度也是O(N+M)。kosaraju算法的步驟如下：(2)在有向圖G上，從最后完成搜索的頂點出發(fā)，在圖G的逆圖G’上進行DFS，若此次遍歷不能訪問到有向圖中所有頂點，則從余下的頂點中最后完成搜索的那個頂點出發(fā)，繼續(xù)做逆圖中的DFS，直至有向圖中的所有頂點都被訪問到為止。每一次調用DFS作逆圖中的遍歷所訪問到的頂點集便是有向圖G中的一個強連通分量。[Kosaraju算法](2)在有向圖G上，從最后完成搜索38memset(visit,false,sizeof(visit));cnt=0;for(i=1;i<=n;i++){if(!visit[i])dfs(i); }memset(visit,false,sizeof(visit));memset(id,0,sizeof(id));ans=0;for(i=cnt-1;i>=0;i--){if(!visit[order[i]]){ans++;dfsn(order[i]);}}voiddfs(intpos)//正向DFS{inti,j;visit[pos]=true;for(i=0;i<adj[pos].size();i++){j=adj[pos][i];if(!visit[j]) dfs(j); }order[cnt++]=pos;//記錄結點結束dfs的時間順序}voiddfsn(intpos)//逆向DFS{inti,j;visit[pos]=true;id[pos]=ans;//求出連通分量for(i=0;i<adjn[pos].size();i++){j=adjn[pos][i];if(!visit[j]) dfsn(j);} }memset(visit,false,sizeof(visi39拓撲排序圖的結點存在一個拓撲序：如果圖中有邊(u，v)，則u必定排在v的前面拓撲排序在有向無環(huán)圖(DAG)上進行拓撲序列不一定唯一拓撲排序圖的結點存在一個拓撲序：如果圖中有邊(u，v)，則u40拓撲排序利用DFS，當節(jié)點u已經擴展完成，將標記顏色置為黑時，將u加入已排序列的頂部，搜索完成時，節(jié)點序列為拓撲序經過拓撲排序的頂點以與其完成時刻相反的順序出現拓撲排序利用DFS，當節(jié)點u已經擴展完成，將標記顏色置為黑時41拓撲排序算法(1)計算每個點的入度，入度為0的點加入隊列Q(2)從Q中取出一個點p，輸出(3)所有與p相鄰的點的入度減1。如果新得到了入度為0的點，則加入隊列Q。(4)轉步驟(2),直到所有點都輸出完畢如果在執(zhí)行過程中發(fā)現找不到入度為0的點,說明圖中存在環(huán)拓撲排序算法42拓撲排序13245678(不唯一)如何生成最小字典序的拓撲序列？可以使用最小堆維護當前入度為0的節(jié)點21348756拓撲排序2134875643最小生成樹生成樹：由G的n-1條邊構成的無環(huán)的子圖，這些邊的集合成為生成樹。最小生成樹：所有生成樹中權值最小的一個邊集T為最小生成樹，確定樹T的問題成為最小生成樹問題。prim算法kruskal算法最小生成樹生成樹：由G的n-1條邊構成的無環(huán)的子圖，這些邊的44prim算法任取一個頂點加入生成樹；在那些一個端點在生成樹里，另一個端點不在生成樹里的邊中，取權最小的邊，將它和另一個端點加進生成樹。重復上一步驟，直到所有的頂點都進入了生成樹為止。prim算法任取一個頂點加入生成樹；45圖論相關算法課件46intprim(ints)//s為初始加入的點{ inti,j,sum=0; for(i=1;i<=n;i++) closest[i]=map[s][i];used[s]=1; intnow; for(i=1;i<n;i++) { intmin=INT_MAX; for(j=1;j<=n;j++) if(!used[j]&&closest[j]<min) { min=closest[j]; now=j; } sum+=min;

used[now]=1 for(j=1;j<=n;j++) if(map[now][j]&&map[now][j]<closest[j]) closest[j]=map[now][j]; } returnsum;}時間復雜度為O(n^2)。(用堆維護最小優(yōu)先級隊列可以達到O(vlogv+elogv),有興趣的同學可以自己實現)intprim(ints)//s為初始加入的點時間復雜度47Kruskal算法對所有邊從小到大排序；依次試探將邊和它的端點加入生成樹，如果加入此邊后不產生圈，則將邊和它的端點加入生成樹；否則，將它刪去；直到生成樹中有了n-1條邊，即告終止。算法的時間復雜度O(eloge)Kruskal算法對所有邊從小到大排序；48圖論相關算法課件49kruskal算法實現的數據結構一維數組，將所有邊按從小到大的順序存在數組里面并查集先把每一個對象看作是一個單元素集合，然后按一定順序將相關聯的元素所在的集合合并。能夠完成這種功能的集合就是并查集。對于并查集來說，每個集合用一棵樹表示。它支持以下操作：Union(Root1,Root2)//合并兩個集合；getRoot(x)//搜索操作（搜索編號為x所在樹的根）。樹的每一個結點有一個指向其父結點的指針。kruskal算法實現的數據結構一維數組，將所有邊按從小到大50并查集的處理過程并查集的處理過程51并查集的實現introotMAXN];//定義根數組，記錄每個節(jié)點的父親節(jié)點voidinit()//函數功能:初始化{for(i=1;i<=N;i++)root[i]=i;//初始每個節(jié)點的根節(jié)點為自己}intgetRoot(intu)//函數功能：取u的根節(jié)點，并壓縮路徑{if(root[u]!=u)root[u]=getRoot(root[u]);returnroot[u];}voidunion(intu,intv)//函數功能：合并兩個節(jié)點{inta=getRoot(u),b=getRoot(v);root[a]=b;}并查集的實現introotMAXN];//定義根數組，52kruskal的實現init();//初始化sort(.......)//按權值對邊進行排序for每條邊(u,v)∈Eintr_1=getRoot(u),r_2=getRoot(v);if(r_1!=r_2)union(u,v);kruskal的實現init();//初始化53歐拉路歐拉路：經過圖中每條邊恰好一次的路歐拉回路：起點和終點相同的歐拉路歐拉路歐拉路：經過圖中每條邊恰好一次的路54歐拉路無向圖存在歐拉路的條件如果圖連通，且所有的點都是偶數度，則有歐拉回路。如果圖連通，且恰有兩點是奇數度，則有歐拉路。且歐拉路的起止點為這兩個奇數度點。對重邊、自環(huán)的情況仍適用。歐拉路無向圖存在歐拉路的條件55歐拉路有向圖存在歐拉路的條件如果圖連通，且每個點的入度等于出度，則存在歐拉回路。如果圖連通，且恰有一點u的出度比入度大1，另有一點v的出度比入度小1，其余的出度等于出度，則存在歐拉路，起點為u，終點為v。對重邊、自環(huán)的情況仍適用。歐拉路有向圖存在歐拉路的條件56歐拉路套圈算法voidEuler(intstart){ for(inti=1;i<=E;i++){ if(!visit[i]&&from==start){ visit[i]=1; Euler(to); path[++top]=i; } }}倒序path[]為歐拉路歐拉路套圈算法57歐拉路例題：給定一組單詞，問這些單詞能否連成一串，使得前面一個單詞的最后一個字母和后面一個單詞的第一個字母相同。歐拉路例題：58歐拉路SampleInput 6 aloha arachnid dog gopher rat tiger 3 oak maple elmSampleOutputaloha.arachnid.dog.gopher.rat.tiger***歐拉路SampleInputSampleOutput59歐拉路解法：先判斷連通性每個單詞相當于在首字母和尾字母之間連一條邊得到一個最多26個點的有向圖求歐拉路歐拉路解法：60漢密爾頓路漢密爾頓路：經過圖中每個點恰好一次的路漢密爾頓回路：起點和終點相同的漢密爾頓路常見方法：狀態(tài)壓縮DP漢密爾頓路漢密爾頓路：經過圖中每個點恰好一次的路61漢密爾頓路對于點數較少的情況，可以用狀態(tài)壓縮的DP來做。比如用opt[mask][k]表示已經訪問過mask表示的結點集合，并且最后位于點k的最優(yōu)解。狀態(tài)轉移方程為：opt[mask][k]=min(opt[mask-{k}][i]+cost[i][k])i是所有與k相鄰的點，mask-{k}指從mask除去k漢密爾頓路對于點數較少的情況，可以用狀態(tài)壓縮的DP來做。比如62圖論

（ElementaryGraphAlgorithms）圖論

（ElementaryGraphAlgor63圖的定義圖是由頂點集合以及頂點間的關系的集合組成的一種關系的數學表示

G=（V，E）其中頂點是由有窮非空集合頂點之間的關系（邊）是有窮集合Path(x,y)表示從x到y的一條單向通路，它是有方向的圖的定義圖是由頂點集合以及頂點間的關系的集合組成的一種關系的64圖的分類有向圖：圖中的邊是有方向的。E(x,y)和E(y,x)表示的邊不同無向圖：圖中的邊是沒有方向的。完全圖：n個頂點的圖兩兩連邊，即有n(n-1)/2條邊，則此圖為n的完全圖。用Kn表示圖的分類有向圖：圖中的邊是有方向的。E(x,y)和E65圖的一些概念鄰接頂點：如果(u,v)∈E(G),則稱u與v互為鄰接頂點子圖：設有兩個圖G(V,E)和G’(V’,E’)，若V’V且E’E’，則稱圖G‘是圖G的子圖權：某些圖的邊上標有相關的數字，稱為該邊的權值圖的一些概念鄰接頂點：如果(u,v)∈E(G),則稱u與66頂點的度一個頂點V的度是與它相連邊的條數，記為Deg(V).頂點的入度一個頂點V的入度是以它為終點有向邊的條數，記為InDeg(V)頂點的出度一個頂點V的入度是以它為起點有向邊的條數，記為OutDeg(V)路徑在圖G＝(V,E)中,若從頂點vi出發(fā),沿一些邊經過一些頂點Vp1,Vp2,…,Vpm，到達頂點Vj。則稱頂點序列(ViVp1Vp2...VpmVj)為從頂點Vi到頂點Vj的路徑。它經過的邊(Vi,Vp1)、(Vp1,Vp2)、...、(Vpm,Vj)應是屬于E的邊。頂點的度一個頂點V的度是與它相連邊的條數，記為Deg(V67圖的存儲表示

鄰接矩陣(AdjacencyMatrix)設圖G=(V,E)是一個有N個頂點的圖，圖的鄰接矩陣是一個二維數組G.edge[N][N]定義：G.edge[i][j]=1If(i,j)∈E(G)0otherwise圖的存儲表示

鄰接矩陣(680213G.edge[i][j]=01001000012G.edge[i][j]=0111100010011010無向圖的臨界矩陣是對稱的有向圖的鄰接矩陣往往是不對稱的0213G.edge[i][j]=01001269圖的存儲表示

鄰接表(AdjacencyList)0213010023320123∧∧∧∧

Dataadjdestlinkdestlinkdestlink

同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結點代表一條邊，結點中另一個頂點的下表dest和指針link圖的存儲表示

鄰接表(Ad70圖論相關算法圖論相關算法71廣度優(yōu)先搜索通常用隊列(先進先出,FIFO)實現 Q={起點s};標記s為己訪問; while(Q非空){ 取Q隊首元素u;u出隊; 所有與u相鄰且未被訪問的點進入隊列; 標記u為已訪問; }廣度優(yōu)先搜索通常用隊列(先進先出,FIFO)實現72廣度優(yōu)先搜索由BFS得到的路徑是原圖中從S到T的邊數最少的路徑廣度優(yōu)先搜索樹不唯一廣度優(yōu)先搜索由BFS得到的路徑是原圖中從S到T的邊數最少的路73廣度優(yōu)先搜索的例子012543678012543678012543678

012112243

廣度優(yōu)先搜索的例子01254367801254367801274t=0;voidBFS(ints) //從s開始遍歷{

intqueue[maxn],tail,head;head=tail=0;queue[head]=s;depth[s]=0;time[s]=t++;visit[s]=true;

while(head<=tail) //queuenotempty{

intcurr=queue[head++];

inti;

for(i=0;i<n;i++)

if(adj[curr][i]&&!visit[i]) { visit[i]=true; depth[i]=depth[curr]+1; time[i]=t++; queue[++tail]=i; }}}t=0;75深度優(yōu)先搜索相關概念遞歸實現結點顏色：白色（開始），灰色（發(fā)現），黑色（結束）一個結點總是從白色變?yōu)榛疑?，再變?yōu)楹谏斔悬c都變?yōu)楹谏珪r，遍歷結束時間戳(timestamp):d[u]表示一個結點開始被訪問的時間，f[u]表示一個結點結束訪問的時間深度優(yōu)先搜索相關概念76深度優(yōu)先搜索inttimestamp=0;dfs(intp){ timestamp=timestamp+1; col[p]=GREY; d[p]=timestamp; for(每個與p相鄰的點i) if(col[i]==WHITE)dfs(i); timestamp=timestamp+1; f[p]=timestamp; col[p]=BLACK;}深度優(yōu)先搜索inttimestamp=0;77圖論相關算法課件78深度優(yōu)先搜索每個頂點的d[u]<f[u]DFS中，v是u的子孫d[u]<d[v]<f[v]<f[u]在搜索中發(fā)現u時可以從u出發(fā)沿一條完全由白色頂點組成的路徑到達vm條邊的連通圖，DFS中順序標號每條邊為1~m，則任意與頂點u關聯的所有邊（邊數>=2）的標號的GCD為1深度優(yōu)先搜索每個頂點的d[u]<f[u]79深度優(yōu)先搜索割點與割邊如果從圖中刪去某點和與該點相關聯的邊后，圖不再連通，那么這個點叫做割點(cutpoint)。如果從圖中刪去某條邊后，圖不再連通，那么這條邊叫做割邊或橋(bridge)。深度優(yōu)先搜索割點與割邊80關節(jié)點：圖中的關節(jié)點指這樣一個頂點，如果刪除它，圖就會被分割成至少兩個分離的子圖。關節(jié)點也稱作分離頂點或割點。0123456789101112頂點0、4、5、6、7和11為關節(jié)點。關節(jié)點：圖中的關節(jié)點指這樣一個頂點，如果刪除它，圖就會被分割81割點、割邊以及連通分量時間戳：dfn[i]表示結點i是第dfn[i]個被訪問到的結點。有的時候我們還要記錄某個結點被遍歷并檢查完畢的時間。voiddfs(v){ dfn[v]=++times;//記錄訪問結點的時間戳 visit[v]=1; for尋找一個v的相鄰節(jié)點u if(visit[u]==0)then DFS(u);}割點、割邊以及連通分量時間戳：dfn[i]表示結點i是第df82LMABCFIDGJEHKABLFMJCHKGIDE連通圖GG的深度優(yōu)先生成樹LMABCFIDGJEHKABLFMJCHKGIDE連通圖G83樹邊：深度優(yōu)先搜索樹中的實線表示樹邊，在DFS過程中，從v點訪問u點時，若u沒有被訪問過，則邊(v,u)為樹邊?；剡叄荷疃葍?yōu)先搜索樹中的虛線表示回邊，在DFS過程中，從v點訪問u點時，若u點已經訪問過，則邊(v,u)為回邊。ABLFMJCHKGIDE樹邊：深度優(yōu)先搜索樹中的實線表示樹邊，在DFS過程中，從v點84由深度優(yōu)先生成樹可得出兩類關節(jié)點的特性：(1)若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為關節(jié)點。因為圖中不存在聯結不同子樹中頂點的邊，因此，若刪去根頂點，生成樹便變成生成森林。如上圖中的頂點A。(2)若生成樹中某個非葉子頂點v，它的子樹中的任一結點均沒有指向v的祖先的回邊，則v為關節(jié)點。因為，若刪去v，則其子樹和圖的其他部分就被分割開來。如上圖中的頂點B、D和G。由深度優(yōu)先生成樹可得出兩類關節(jié)點的特性：(1)若生成樹的根85我們在DFS的基礎上增加一個low數組，low[i]用來記錄i及i的子孫相連的輩分最高的祖先的訪問時間戳。low[v]=min(dfn[v],low[w],dfn[k]);w是頂點v在深度優(yōu)先樹上的孩子結點；k是頂點v在深度優(yōu)先樹上由回邊聯結的祖先結點；我們在DFS的基礎上增加一個low數組，low[i]用來記錄86當low[j]<dfn[i](j是i的兒子)時，說明j或者j的子孫中存在指向i祖先的回邊。反之，若對于某個頂點v，存在孩子結點w，且low[w]>=dfn[v],表明w及其子孫均無指向v的祖先的回邊，則該頂點v必為關節(jié)點。具體算法如下：當low[j]<dfn[i](j是i的兒子)時，說明j或者j87voiddfs(intv){inti,w,cnum=0;//cnum表示孩子個數times++;visit[v]=1;dfn[v]=low[v]=times;//記錄時間戳for(i=0;i<map[v].size();i++){ w=map[v][i]; if(!visit[w])//w沒有訪問過，則w是v的孩子結點 { cnum++; dfs(w); low[v]=min(low[w],low[v]); if(v==root&&cnum==2)//如果v是根，且有2個以上的孩子，則為關節(jié)點 flag[v]=1; if(v!=root&&low[w]>=dfn[v])//不為根若low[w]>=dfn[v])，則為關節(jié)點 flag[v]=1; } elseif(v!=w)//w已經訪問過了，說明從v到w有一條回邊，w是v的祖先 { low[v]=min(low[v],dfn[w]); }} }voiddfs(intv)88橋：圖中的橋（bridge）是一條邊，如果刪除這條邊，將把連通圖分離成兩個斷開的子圖。無橋的圖稱作邊連通圖（edge-connectedgraph）。0123456789101112這個圖不是邊連通圖。邊0-5、6-7和11-12（帶陰影）為橋。橋：圖中的橋（bridge）是一條邊，如果刪除這條邊，將把連89在任何DFS樹中，當且僅當不存在回邊連通w的子孫與w的祖先時，樹邊v-w是一座橋。與割點類似的，我們定義low[]和dfn[]。父子邊e=u→v，當且僅當low[v]>dfn[u]的時候，e是割邊。在任何DFS樹中，當且僅當不存在回邊連通w的子孫與w的祖先時90有向圖的強連通分量在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通(stronglyconnected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。非強連通圖有向圖的極大強連通子圖，稱為強連通分量(stronglyconnectedcomponents)。下圖中，子圖{1,2,3,4}為一個強連通分量，因為頂點1,2,3,4兩兩可達。{5},{6}也分別是兩個強連通分量。有向圖的強連通分量在有向圖G中，如果兩個91求有向圖的強連通分量一般采用Kosaraju算法或Tarjan算法，兩者的時間復雜度都是O(n+m)。下面著重介紹一下Tarjan算法。[Tarjan算法]Tarjan算法是基于對圖深度優(yōu)先搜索的算法，每個強連通分量為搜索樹中的一棵子樹。dfs時，把當前搜索樹中未處理的節(jié)點加入一個堆棧，回溯時可以判斷棧頂到棧中的節(jié)點是否為一個強連通分量。求有向圖的強連通分量一般采用Kosaraju算法或Tarja92我們仍然定義dfn[i]為節(jié)點i搜索的次序編號(時間戳)，low[i]為i或i的子樹能夠追溯到的最早的棧中節(jié)點的次序號。由定義可以得出:當dfn(u)=low(u)時，以u為根的搜索子樹上的所有節(jié)點構成一個強連通分量。我們仍然定義dfn[i]為節(jié)點i搜索的次序編號(時間戳)，l93voidtarjan(inti){intj;dfn[i]=low[i]=++times;

//為節(jié)點u設定次序編號和Low初值instack[i]=true;Stack[++Stop]=i;//將節(jié)點u壓入棧中for(edge*e=V[i];e;e=e->next){j=e->t;if(!dfn[j]){ tarjan(j); if(low[j]<low[i]) low[i]=low[j];}elseif(instack[j]&&dfn[j]<low[i]) low[i]=dfn[j];}if(dfn[i]==low[i])//如果節(jié)點i是強連通分量的根{Bcnt++;do{ j=Stack[Stop--]; instack[j]=false; Belong[j]=Bcnt;}while(j!=i);}}voidsolve(){inti;Stop=Bcnt=times=0;memset(dfn,0,sizeof(dfn));for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);}voidtarjan(inti)94從節(jié)點1開始DFS，把遍歷到的節(jié)點加入棧中。搜索到節(jié)點u=6時，dfn[6]=low[6]=4，找到了一個強連通分量。退棧到u=v為止，{6}為一個強連通分量。從節(jié)點1開始DFS，把遍歷到的節(jié)點加入棧中。搜索到節(jié)點u=695返回節(jié)點5，發(fā)現dfn[5]=low[5]=3，退棧后{5}為一個強連通分量。返回節(jié)點5，發(fā)現dfn[5]=low[5]=3，退棧后{5}96返回節(jié)點3，繼續(xù)搜索到節(jié)點4，把4加入堆棧。發(fā)現節(jié)點4存在向節(jié)點1的回邊，節(jié)點1還在棧中，所以low[4]=dfn[1]=1。節(jié)點6已經出棧，不再訪問6，返回3，(3,4)為樹邊，所以low[3]=low[4]=1。返回節(jié)點3，繼續(xù)搜索到節(jié)點4，把4加入堆棧。發(fā)現節(jié)點4存在向97繼續(xù)回到節(jié)點1，最后訪問節(jié)點2。訪問邊(2,4)，4還在棧中，所以low[2]=4。返回1后，發(fā)現DFN[1]=LOW[1]，把棧中節(jié)點全部取出，組成一個連通分量{1,3,4,2}。至此，算法結束。經過該算法，求出了圖中全部的三個強連通分量{1,3,4,2},{5},{6}。繼續(xù)回到節(jié)點1，最后訪問節(jié)點2。訪問邊(2,4)，4還在棧中98[Kosaraju算法]Kosaraju是基于對有向圖及其逆圖兩次DFS的方法，其時間復雜度也是O(N+M)。kosaraju算法的步驟如下：(1)在有向圖G上，從某個頂點出發(fā)進行DFS，并按其所有鄰接點的搜索都完成(即退出DFS函數)的順序將頂點排列起來。[Kosaraju算法](1)在有向圖G上，從某個頂點出發(fā)99[Kosaraju算法]Kosaraju是基于對有向圖及其逆圖兩次DFS的方法，其時間復雜度也是O(N+M)。kosaraju算法的步驟如下：(2)在有向圖G上，從最后完成搜索的頂點出發(fā)，在圖G的逆圖G’上進行DFS，若此次遍歷不能訪問到有向圖中所有頂點，則從余下的頂點中最后完成搜索的那個頂點出發(fā)，繼續(xù)做逆圖中的DFS，直至有向圖中的所有頂點都被訪問到為止。每一次調用DFS作逆圖中的遍歷所訪問到的頂點集便是有向圖G中的一個強連通分量。[Kosaraju算法](2)在有向圖G上，從最后完成搜索100memset(visit,false,sizeof(visit));cnt=0;for(i=1;i<=n;i++){if(!visit[i])dfs(i); }memset(visit,false,sizeof(visit));memset(id,0,sizeof(id));ans=0;for(i=cnt-1;i>=0;i--){if(!visit[order[i]]){ans++;dfsn(order[i]);}}voiddfs(intpos)//正向DFS{inti,j;visit[pos]=true;for(i=0;i<adj[pos].size();i++){j=adj[pos][i];if(!visit[j]) dfs(j); }order[cnt++]=pos;//記錄結點結束dfs的時間順序}voiddfsn(intpos)//逆向DFS{inti,j;visit[pos]=true;id[pos]=ans;//求出連通分量for(i=0;i<adjn[pos].size();i++){j=adjn[pos][i];if(!visit[j]) dfsn(j);} }memset(visit,false,sizeof(visi101拓撲排序圖的結點存在一個拓撲序：如果圖中有邊(u，v)，則u必定排在v的前面拓撲排序在有向無環(huán)圖(DAG)上進行拓撲序列不一定唯一拓撲排序圖的結點存在一個拓撲序：如果圖中有邊(u，v)，則u102拓撲排序利用DFS，當節(jié)點u已經擴展完成，將標記顏色置為黑時，將u加入已排序列的頂部，搜索完成時，節(jié)點序列為拓撲序經過拓撲排序的頂點以與其完成時刻相反的順序出現拓撲排序利用DFS，當節(jié)點u已經擴展完成，將標記顏色置為黑時103拓撲排序算法(1)計算每個點的入度，入度為0的點加入隊列Q(2)從Q中取出一個點p，輸出(3)所有與p相鄰的點的入度減1。如果新得到了入度為0的點，則加入隊列Q。(4)轉步驟(2),直到所有點都輸出完畢如果在執(zhí)行過程中發(fā)現找不到入度為0的點,說明圖中存在環(huán)拓撲排序算法104拓撲排序13245678(不唯一)如何生成最小字典序的拓撲序列？可以使用最小堆維護當前入度為0的節(jié)點21348756拓撲排序21348756105最小生成樹生成樹：由G的n-1條邊構成的無環(huán)的子圖，這些邊的集合成為生成樹。最小生成樹：所有生成樹中權值最小的一個邊集T為最小生成樹，確定樹T的問題成為最小生成樹問題。prim算法kruskal算法最小生成樹生成樹：由G的n-1條邊構成的無環(huán)的子圖，這些邊的106prim算法任取一個頂點加入生成樹；在那些一個端點在生成樹里，另一個端點不在生成樹里的邊中，取權最小的邊，將它和另一個端點加進生成樹。重復上一步驟，直到所有的頂點都進入了生成樹為止。prim算法任取一個頂點加入生成樹；107圖論相關算法課件108intprim(ints)//s為初始加入的點{ inti,j,sum=0; for(i=1;i<=n;i++) closest[i]=map[s][i];used[s]=1; intnow; for(i=1;i<n;i++) { intmin=INT_MAX; for(j=1;j<=n;j++) if(!used[j]&&closest[j]<min) { min=closest[j]; now=j;