5-圖論算法課件

ACM/ICPC程序設(shè)計簡單算法圖論-算法圖的遍歷 BFS(廣搜)

DFS(深搜)最小生成樹

Prim Kruskal最短路徑 Bellman-Ford Dijkstra Floyd-WarshallBFS練習(xí)DFS練習(xí)Prim練習(xí)Kruskal練習(xí)Bellman-Ford練習(xí)Dijkstra練習(xí)Floyd-Warshall練習(xí)圖的遍歷遍歷要訪問到圖中的每一個頂點。BFS(Breadth-FirstSearch)DFS(Depth-FirstSearch)BFS思想—遍歷篇1.從圖中某頂點v0出發(fā)，在訪問了v0之后，搜索v0的(所有未被訪問的)鄰接頂點v1.v2…2.依次從這些鄰接頂點出發(fā)，廣搜圖中其它頂點，直至圖中所有已被訪問的頂點的鄰接頂點都被訪問到。3.若此時圖中還有未被訪問到的頂點，則再選擇其中之一作為v0重復(fù)上述過程。直到圖中所有頂點均被訪問到。//搜索過程沒有回溯，是一種犧牲空間換取時間的方法。時間復(fù)雜度：O(V+E)BFS程序基本結(jié)構(gòu)定義一個隊列;起始點加入隊列;while(隊列不空){

取出隊頭結(jié)點;

若它是所求的目標(biāo)狀態(tài),跳出循環(huán);

否則，從它擴(kuò)展出子結(jié)點,全都添加到隊尾;}若循環(huán)中找到目標(biāo),輸出結(jié)果;否則輸出無解;BFS示例：DFS思想—遍歷篇1.將圖G中每個頂點標(biāo)記為未被訪問，選取一個頂點v作為搜索起點，標(biāo)記其為已訪問2.遞歸地深搜v的每個未被訪問過的鄰接頂點，直到從v出發(fā)所有可達(dá)的頂點都已被訪問過。3.若此時圖中還有未被訪問到的頂點，則再選擇其中之一作為v重復(fù)上述過程。直到圖中所有頂點均被訪問到。//時間復(fù)雜度：O(V+E)DFS程序基本結(jié)構(gòu)voidDFS(intstep){ for(i=0;i<Max_Elements;i++) { if(子結(jié)點符合條件) {

新子結(jié)點入棧；

if(是目標(biāo)結(jié)點)

輸出

else DFS(step+1); 子結(jié)點出棧

} }}DFS示例最小生成樹(MinimumSpanningTree)G(V,E)是無向連通賦權(quán)圖，G’(V,E’)是包含G中所有頂點的樹，且樹中各邊權(quán)總和最小，則G’是最小生成樹(可能不唯一)容易想到，用貪心策略。 Prim KruskalPrim思想—最小生成樹篇1.從V中任取一結(jié)點放入V'；2.在所有的端點分別在(V-V')和V'中的邊中，選一條權(quán)最小的加入E'；3.將邊E'在(V-V')中的頂點從V中取出放入V'；4.重復(fù)步驟2~3，直到V'與V相等為止。//該算法步步為營，每步生成的結(jié)果均為最終結(jié)果的一部分。它每次從連接V’與(V-V’)的邊中選最小邊，所選出的不一定是所有尚未選出的屬于最小生成樹的邊中的最小者。時間復(fù)雜度：O(ElgV)Prime程序基本結(jié)構(gòu)voidPrim(){ inti,j,k,min,lowcost[vex],closest[vex];

for(i=2;i<=n;i++){ lowcost[i]=c[1][i];//第1個點到其他點的代價

closest[i]=1;//初始時，所有點的起點都是點1 } for(i=2;i<=n;i++){ min=maxcost;//maxcost一個很大的數(shù)

for(j=2;j<=n;j++) if(closest[j]&&lowcost[j]<min&&lowcost[j]>0) { min=lowcost[j];//在v中找到最小的代價點k k=j; }

closest[k]=0;//k歸入u中

for(j=2;j<=n;j++)

if(closest[j]&&c[k][j]<lowcost[j]&&c[k][j]>0){ lowcost[j]=c[k][j];//以k點為起點進(jìn)行新一輪的代價計算,更新lowcost[]和closest[] closest[j]=k; } }}無向連通圖,初始時u只包含1個點，后一步步將v中的點添加到u中來。用closest[i]=0表示i點在u集合中,lowcost[i]當(dāng)前起點到i點的最小代價c[i][j]頂點i到j(luò)的權(quán)(i到j(luò)無邊，則令c[i][j]=-1)，共有n個頂點(該模板中，頂點從1開始計)Prim示例：V2V0V3V5V4V1V2V0V3V5V4V11U={v0}U={v0,v2}U={v0,v2,v5}U={v0,v2,v5,v3}U={v0,v2,v5,v3,v1}U={v0,v2,v5,v3,v1,v4}V3V4V141V0V2V5V4V1214V0V2V5V3V41425V2V0V5V1V335124V2V1V0V5V3V4Kruskal思想：—最小生成樹篇1.將邊按邊樹由小到大排序。2.每次加最小邊&&不構(gòu)成回路。3.加進(jìn)了n-1條邊就得到了最小生成樹//Kruskal算法并不保證每步生成的結(jié)果是連通的（中間結(jié)果可能不是樹）。Kruskal程序基本結(jié)構(gòu)：優(yōu)先隊列+并查集Kruscal示例：實例的執(zhí)行過程12435661655563421、初始連通分量：{1},{2},{3},{4},{5},{6}2、反復(fù)執(zhí)行添加、放棄動作。條件：邊數(shù)不等于n-1時邊 動作 連通分量

(1,3)添加 {1,3},{4},{5},{6},{2}(4,6)添加 {1,3},{4,6},{2},{5}(2,5)添加 {1,3},{4,6},{2,5}(3,6)添加 {1,3,4,6},{2,5}(1,4)放棄 因構(gòu)成回路

(3,4)放棄 因構(gòu)成回路

(2,3)添加 {1,3,4,5,6,2}1243561534255算法實現(xiàn)要點:用并查集的相關(guān)操作：實現(xiàn)集合的并；判斷新邊的兩端點是否處于同一集合，來確定是否構(gòu)成回路。最短路徑(ShortestPath):最短路徑問題：如果從圖中某一頂點(稱為源點)到達(dá)另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。邊上權(quán)值非負(fù)情形的單源最短路徑問題

—

Dijkstra算法邊上權(quán)值為任意值的單源最短路徑問題

—Bellman-Ford算法所有頂點之間的最短路徑

—Floyd算法Dijkstra思想：—最短路徑篇初始化：

S←{v0};dist[j]←Edge[0][j],j=1,2,…,n-1;1、求出最短路徑的長度：

dist[k]←min{dist[i]},i

V-S;S←S

U{k

};2、修改：

dist[i]←min{dist[i],dist[k]+Edge[k][i]},foriV-S;3、判斷：若S=V,則算法結(jié)束，否則轉(zhuǎn)1。引入一個輔助數(shù)組dist。dist[i]表示當(dāng)前從源點v0到終點vi

的最短路徑的長度。時間復(fù)雜度:O(V2)Dijkstra程序基本結(jié)構(gòu)：voiddisktra(intv)//原點是v{ bools[maxn];registerinti,j,k;

for(i=1;i<=n;i++){ dist[i]=c[v][i]; s[i]=0;//i不在集合S中 if(dist[i]==manint)//vtoi沒有邊

prev[i]=0; else prev[i]=v; }

s[v]=1;dist[v]=0; for(i=1;i<n;i++){ inttemp=manint,u=v;

for(j=1;j<=n;j++) if(!s[j]&&dist[j]&&dist[j]<temp){ u=j; temp=dist[j]; }

s[u]=1;

for(j=1;j<=n;j++) if(!s[j]&&c[u][j]<manint){ intnewdist=dist[u]+c[u][j]; if(newdist<dist[j]){ dist[j]=newdist; prev[j]=u; } } }}結(jié)點從1開始計，maxn為最大結(jié)點數(shù),n為結(jié)點數(shù)，manint是無窮大,c[i][j]i到j(luò)的權(quán)，pre[]記錄父結(jié)點,dist[i]源點到i的最短路徑，s[]表示左邊的集合constintmaxn=101,

manint=99999999;intc[maxn][maxn],prev[maxn],dist[maxn],n;Dijkstra逐步求解的過程Bellman-Ford思想：—最短路徑篇1.圖中無負(fù)回路2.最短路徑長度數(shù)組序列dist1[u],…,distn-1[u]，其中disti[u]從v到u最多經(jīng)過i條邊3.dist1[u]=Edge[v,u] distk[u]=min{distk-1[u],min{distk-1[j]+Edge[j,u]}}//時間復(fù)雜度：O(VE)Bellman-Ford程序基本結(jié)構(gòu)：voidBellman-Ford(){ inti; for(i=1;i<=n;i++){ d[i]=manint; par[i]=0; } d[s]=0; for(i=1;i<=n-1;i++){ foreachedge(u,v) if(d[v]>d[u]+w(u,v)){ d[v]=d[u]+w(u,v); par[v]=u; } } foreachedge(u,v) if(d[v]>d[u]+w(u,v)) returnfalse; returntrue;}s為起點，d[i]是s到i的最短路徑長度，par[i]記錄i結(jié)點的父節(jié)點.如果不存在從s可達(dá)的負(fù)權(quán)環(huán)，返回true.Floyd-Warshall思想：—最短路徑篇定義一個n×n的方陣序列∶A0，A1…，An，其中Ak[i-1][j-1]表示從vi到vj允許k個頂點v0,v1,…,vk-1為中間頂點的最短路徑長度（A0是圖的鄰接矩陣）。A0[i][j]表示從vi到vj不經(jīng)過任何中間頂點的最短路徑長度。An[i][j]就是從vi到vj的最短路徑長度。 A0[i][j]=arcs[i][j] 0≤i≤n-1,0≤j≤n-1 Ak[i][j]=min{Ak-1[i][j],Ak-1[i][k-1]+Ak-1[k-1][j]} 1≤k≤n，加入第k個頂點vk-1為中間頂點。//時間復(fù)雜度O(n3)Floyd-Warshall程序基本結(jié)構(gòu)：for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(d[i][j]>d[i][k]+d[k][j])d[i][j]=d[i][k]+d[k][j];

(d[i][j]=Min(d[i][j],d[i][k]+d[k][j]))Floyd示例：執(zhí)行Floyd算法后:061211941∞0∞∞∞∞∞58071496∞∞∞0∞∞∞∞9∞100∞∞13168722014161711108307123459851068776183Exercise

Practicemakesperfect!Themore,thebetter!BFS：

zoj(1091)國際象棋棋盤上有一個馬，要跳到指定目標(biāo)，最少跳幾步？

abcdefgh12345678h8a1輸入：a1h8輸出：Togetfroma1toh8takes6knightmoves.

跳馬的規(guī)則

abcdefgh12345678在2×3的矩形里：BFS：

abcdefgh1234567803321322312332233323333333233332例如：從a1到e4當(dāng)目標(biāo)出現(xiàn)在所擴(kuò)展出的結(jié)點里，結(jié)果就找到了。Togetfroma1toe4takes3knightmoves.

BFS：intmain(){for(;;){if(!(cin>>c1))break;cin>>d1>>c2>>d2;//輸入起點、終點。

for(inti=0;i<8;i++)for(intj=0;j<8;j++)m[i][j]=0;//所有點都標(biāo)記為“沒走”

proc();}return0;}#include<iostream>#include<queue>usingnamespacestd;intd[8][2]={{1,2},{1,-2},{2,-1},{2,1},{-1,2},{-1,-2},{-2,-1},{-2,1}};intm[8][8];//給走過的點標(biāo)記charc1,c2,d1,d2;voidproc();voidproc(){intx,y,nx,ny,sx,sy,dx,dy,step=0;sx=c1-'a';sy=d1-'1';dx=c2-'a';dy=d2-'1';queue<int>tq;

tq.push(sx);tq.push(sy);tq.push(step);

m[sx][sy]=1;while(!tq.empty()){

x=tq.front();tq.pop();y=tq.front();tq.pop();step=tq.front();tq.pop();if(x==dx&&y==dy)break;

for(inti=0;i<8;i++){nx=x+d[i][0];ny=y+d[i][1];if(nx<0||nx>=8||ny<0||ny>=8||m[nx][ny])continue;

tq.push(nx);tq.push(ny);tq.push(step+1);

m[nx][ny]=1;}}cout<<"Togetfrom"<<c1<<d1<<"to"<<c2<<d2<<"takes"<<step<<"knightmoves."<<endl;}初始點入隊取出隊頭元素新點加入隊尾KnightMoveszoj(1091)程序?qū)崿F(xiàn)雙向BFS

abcdefgh123456780212212122211112012從起點、終點同時開始雙向BFS,有效地提高了時空效率。從起點找2步能跳到的點從終點找1步能跳到的點DFS：pku2258給無向圖，求此圖中的最長路徑。要求路不能重復(fù)走，但節(jié)點可以重復(fù)地到達(dá)。如輸入輸出？//best用來記錄最長路徑的長度，gr[i][j]i到j(luò)的邊長為1，以每一個結(jié)點為源點進(jìn)行深搜#include<stdio.h>#include<memory.h>intgr[25][25],best,n,m;voiddfs(intp,intdepth)//p為源點，depth為深度{ inti; boolflag=true; for(i=0;i<n;i++){ if(gr[p][i]){ gr[i][p]=gr[p][i]=0;//表示該路已用過

dfs(i,depth+1);//以i為源點深層搜索

flag=false; gr[i][p]=gr[p][i]=1;//表不用該路

} } if(flag){ if(depth>best) best=depth; return; }}

main(){ inti,a,b; while(scanf("%d%d",&n,&m)!=EOF){ if(n==0&&m==0)break; best=0; memset(gr,0,sizeof(gr)); for(i=0;i<m;i++){ scanf("%d%d",&a,&b); gr[a][b]=gr[b][a]=1; } for(i=0;i<n;i++) dfs(i,0); printf("%d\n",best); }}青蛙(zju1942)湖中有一些石頭露出水面。青蛙Freddy蹲在其中一塊上面，他女朋友Fiona在另一塊上。Freddy想跳到Fiona那里。Freddy可以在兩石頭間跳躍，有不同的路徑選擇；他希望找到一條路，路上跳躍的最大距離最小。輸入這些石頭的坐標(biāo)，輸出這個最小值。Prim:zju1942intmain(){intn,i,j,k,x[200],y[200],T=1;ifstreamfin("frogger.in");#definecinfinwhile(cin>>n&&n){for(i=0;i<n;i++){cin>>x[i]>>y[i];for(j=0;j<i;j++)d[i][j]=d[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}#include<iostream>#include<fstream>#include<cmath>usingnamespacestd;#defineMin(a,b)((a)>(b)?(b):(a))#defineMax(a,b)((a)>(b)?(a):(b))doubled[201][201];Prim:

doublelowcost[200],min,answer;memset(lowcost,0,sizeof(lowcost));answer=d[0][1];for(i=1;i<n;i++){//與集合鄰接的邊長初始化，現(xiàn)在集合中只有一個點0lowcost[i]=d[0][i];//初始化lowcost[]answer=Min(answer,d[0][i]);//同時找出最短邊}for(i=1;i<n;i++){min=1000000;j=-1;for(k=1;k<n;k++)if(lowcost[k]!=0&&lowcost[k]<min){//找有最小邊權(quán)的鄰接點

min=lowcost[k];j=k;}

answer=Max(answer,min);if(j==1)//當(dāng)集合加進(jìn)了點1，可以結(jié)束

break;Prim:

lowcost[j]=0;//集合加進(jìn)點jfor(k=1;k<n;k++)//更新鄰接點邊權(quán)

if(d[j][k]<lowcost[k]&&lowcost[k]!=0){lowcost[k]=d[j][k];}}printf("Scenario#%d\n",T++);printf("FrogDistance=%.3lf\n\n",answer);}return0;}Kruscal:zju1942classEdge{//邊類，記錄三個信息：端點、邊長public:inte,s;doubledis;Edge(){}Edge(inta,intb,doublec):e(a),s(b),dis(c){}}edge[40000];//用一個數(shù)組保存邊boolcmp(Edgee1,Edgee2){

//排序時，需要比較邊的長短

returne1.dis<e2.dis;}Kruscal:（并查集的操作）ints[200];intFind(intk){//尋找k的祖先

intr,t,tmp;for(r=k;s[r]!=r;r=s[r]);for(t=k;t!=r;t=tmp){tmp=s[t];s[t]=r;//路徑壓縮

}returnr;}voidUnite(inta,intb){//把a、b所在的集合合并

a=Find(a);b=Find(b);if(a!=b){//當(dāng)a,b屬于不同的集合，合并這兩個集合

s[b]=a;}合并只需要一個操作：修改父節(jié)點。Kruscal:intmain(){intn,i,j,x[200],y[200],T=1,L;while(cin>>n&&n){L=0;for(i=0;i<n;i++){cin>>x[i]>>y[i];for(j=0;j<i;j++){edge[L++]=Edge(i,j,sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));}}sort(edge,edge+L,cmp);//標(biāo)準(zhǔn)庫的函數(shù)，對邊進(jìn)行從小到大排序#include<iostream>#include<algorithm>#include<cstdio>#include<cmath>usingnamespacestd;Kruscal:

for(i=0;i<n;i++)//并查集的初始化，剛開始，每個點自成集合。

s[i]=i;for(i=0;i<L;i++){//從最小邊長的邊開始，把邊兩端點所在集合合并起來

Unite(edge[i].e,edge[i].s);if(Find(0)==Find(1))//當(dāng)0與1處同一集合，當(dāng)前所加邊長就是所求

break;}printf("Scenario#%d\n",T++);printf("FrogDistance=%.3lf\n\n",edge[i].dis);}return0;}Bellman-Ford:HomeWorkvoidInitialize_Single_Source(ints){ for(i=1;i<=n;i++) { d[i]=65535; Pa[i]=-1; } d[s]=0;}voidRelax(intu,intv){ if(d[v]>d[u]+w[u][v]) { d[v]=d[u]+w[u][v]; Pa[v]=u; }}It’stoexaminewhetherthereexitsnegativecyclesinG,isexist->false;noexist->true#include<stdio.h>#defineMAX100inti,j,k,n,s;intd[MAX],Pa[MAX],w[MAX][MAX];//d[]isanupperboundontheweightofashortestpathfromsourcestov

Bellman-Ford:boolBellman_Ford(ints){ Initialize_Single_Source(s); for(i=1;i<n;i++) { for(j=1;j<=n;j++) for(k=1;k<=n;k++) if(w[j][k]!=65535) Relax(j,k); } for(j=1;j<=n;j++) for(k=1;k<=n;k++) if(w[j][k]!=65535&&d[k]>d[j]+w[j][k]) returnfalse; returntrue;}intmain(){ scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&w[i][j]); scanf("%d",&s);//s<=n; if(Bellman_Ford(s)) printf("Nonegativecyclesexitshere."); elseprintf("Thereexitsnegativecycles!"); printf("\n"); return0;}/*565535665535765535655356553558-465535-26553565535655356553565535-3655359265535765535655351*/Dijkstra:pku2387voidDijkstra(intn,intv){ for(inti=1;i<=n;i++) { dist[i]=c[v][i]; s[i]=false; if(dist[i]==MAX)prev[i]=0; elseprev[i]=v; } dist[v]=0;s[v]=true; for(i=1;i<n-1;i++) { inttemp=MAX; intu=v; for(intj=1;j<=n;j++) if((!s[j])&&(dist[j]<temp)) { u=j;temp=dist[j]; } s[u]=true; for(j=1;j<=n;j++) if((!s[j])&&(c[u][j]<MAX)) { intnewdist=dist[u]+c[u][j]; if(newdist<dist[j]) { dist[j]=newdist; prev[j]=u; } } }}#include<stdio.h>#include<math.h>#include<iostream>usingnamespa