圖論算法與模型構(gòu)建

湖南省長沙市第一中學(xué)曹利國圖論算法與模型構(gòu)建總覽圖的基本概念與存儲結(jié)構(gòu)圖的遍歷和染色性圖的連通性問題路徑問題

拓?fù)渑判蛄髁繂栴}匹配問題

圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖,而是以一種抽象的形式來表達(dá)一些確定的事物之間的聯(lián)系的一個數(shù)學(xué)系統(tǒng).

定義1一個有序二元組(V,E)稱為一個圖,記為G=(V,E),其中

①V稱為G的頂點(diǎn)集,V≠,其元素稱為頂點(diǎn)或結(jié)點(diǎn),簡稱點(diǎn);②

E稱為G的邊集,其元素稱為邊,它聯(lián)結(jié)V中的兩個點(diǎn),如果這兩個點(diǎn)是無序的,則稱該邊為無向邊,否則,稱為有向邊.

如果V={v1,v2,…,vn}是有限非空點(diǎn)集,則稱G為有限圖或n階圖.Sec.1圖的基本概念與存儲結(jié)構(gòu)

如果E的每一條邊都是無向邊,則稱G為無向圖(如圖1);

如果E的每一條邊都是有向邊,則稱G為有向圖(如圖2);

否則,稱G為混合圖.圖1圖2并且常記V={v1,v2,…,vn},|V|

=n

;E={e1,e2,…,em}(ek=vivj

),|E|

=m.稱點(diǎn)vi,vj為邊vivj的端點(diǎn).在有向圖中,稱點(diǎn)vi,vj分別為邊vivj的始點(diǎn)和終點(diǎn).

有邊聯(lián)結(jié)的兩個點(diǎn)稱為相鄰的點(diǎn),有一個公共端點(diǎn)的邊稱為相鄰邊.邊和它的端點(diǎn)稱為互相關(guān)聯(lián).常用d(v)表示圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目,

d(v)稱為頂點(diǎn)v的度數(shù).用N(v)表示圖G中所有與頂點(diǎn)v相鄰的頂點(diǎn)的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.我們今后只討論有限簡單圖：(1)頂點(diǎn)個數(shù)是有限的;(2)任意一條邊有且只有兩個不同的點(diǎn)與它相互關(guān)聯(lián);(3)若是無向圖,則任意兩個頂點(diǎn)最多只有一條邊與之相聯(lián)結(jié);(4)若是有向圖,則任意兩個頂點(diǎn)最多只有兩條邊與之相聯(lián)結(jié).當(dāng)兩個頂點(diǎn)有兩條邊與之相聯(lián)結(jié)時，這兩條邊的方向相反.

如果某個有限圖不滿足(2)(3)(4),可在某條邊上增設(shè)頂點(diǎn)使之滿足.

定義2若將圖G的每一條邊e都對應(yīng)一個實數(shù)F(e),則稱F(e)為該邊的權(quán),并稱圖G為賦權(quán)圖(網(wǎng)絡(luò)),記為G=(V,E,F).

定義3設(shè)G=(V,E)是一個圖,v0,v1,…,vk∈V,且1≤i≤k,vi-1vi∈E,則稱v0v1…vk是G的一條通路.如果通路中沒有相同的邊,則稱此通路為道路.始點(diǎn)和終點(diǎn)相同的道路稱為圈或回路.

如果通路中既沒有相同的邊,又沒有相同的頂點(diǎn),則稱此通路為路徑,簡稱路.

定義4任意兩點(diǎn)均有通路的圖稱為連通圖.

定義5連通而無圈的圖稱為樹,常用T表示樹.圖的儲存結(jié)構(gòu)矩陣鄰接表鄰接多重表十字鏈表無向圖鄰接5|4|3|/2|2|2|3|1|2|4|/5|/4|/5|/鄰接鏈表每一個頂點(diǎn)有一個所有與之相鄰的鏈表每一條邊2個（對無向圖）要在兩個頂點(diǎn)的鏈表中都加入空間復(fù)雜度O(|E|)

對稀疏圖這種方式比較好鄰接表Pascal語言const

maxv=10000;typeTnode=record//定義頂點(diǎn)類型

c:integer;//頂點(diǎn)編號

next:^Tnode;//此點(diǎn)的鄰接鏈表end;Var//數(shù)組g表示每個頂點(diǎn)的鄰接鏈表//的鏈表頭---哨兵g:array[1..maxv]ofTnode;

n,m,i,a,b:integer;

t:^Tnode;C++語言#include<iostream>usingnamespacestd;constint

maxv=10000;struct

Tnode{//定義頂點(diǎn)類型

intc;//頂點(diǎn)編號

Tnode*next;//此點(diǎn)的鄰接鏈表};//數(shù)組g表示每個頂點(diǎn)的鄰接鏈表//的鏈表頭---哨兵

Tnode

g[maxv];

int

n,m,i,a,b;

Tnode*t;圖G有n個頂點(diǎn)，編號從1到n。有m條有向邊，輸入時每行兩個整數(shù)ab，表示邊為從頂點(diǎn)a連接到頂點(diǎn)b。下面程序用指針實現(xiàn)圖的鄰接鏈表。Pascal語言procedureins(x:integer;var

p:Tnode);Begin//插入鏈表子過程

new(t);t^.c:=x;

t^.next:=p.next;

p.next:=t;end;begin

readln(n,m);

//初始化鄰接鏈表“哨兵”

fori:=1tondo

g[i].next:=nil;

//讀入邊，插入鄰接鏈表

fori:=1tomdobegin

readln(a,b);

ins(b,g[a]);{ins(a,g[b]);//無向邊時再加入}end;//...C++語言voidins(intx,Tnode&p){//插入鏈表子過程t=new(Tnode);t->c=x;t->next=p.next;

p.next=t;}intmain(){

cin>>n>>m;

//初始化鄰接鏈表“哨兵”

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

g[i].next=NULL;

for(i=0;i<m;i++){//讀入邊，插入鄰接鏈表

cin>>a>>b;

ins(b,g[a]);

//ins(a,g[b]);//無向邊時

}//…鄰接表的實現(xiàn)A（指針）Pascal語言constmaxV=1000;//最多頂點(diǎn)數(shù)

maxE=10000;//最多邊數(shù)typeTnode=record//定義頂點(diǎn)類型

c:integer;//節(jié)點(diǎn)編號

next:integer;//此節(jié)點(diǎn)的鄰接鏈表end;vare:array[1..maxE]ofTnode;g:array[1..maxV]ofTnode;

n,m,efree,i,a,b,t:integer;procedureins(x:integer;var

p:Tnode);begin//取一個空元素插入鏈表p后

e[efree].c:=x;e[efree].next:=p.next;

p.next:=efree;

efree:=efree+1;//新空元素下標(biāo)end;C++語言constint

maxV=1000,//最多頂點(diǎn)數(shù)

maxE=10000;//最多邊數(shù)struct

Tnode{//定義頂點(diǎn)類型

intc;//頂點(diǎn)編號

intnext;//此點(diǎn)的鄰接鏈表};//數(shù)組g表示每個頂點(diǎn)的鄰接鏈表//的鏈表頭---哨兵

Tnode

g[maxV],e[maxE];

intn,m,i,a,b,efree,t;voidins(intx,Tnode&p){//取一個空元素插入鏈表p后

e[efree].c=x;

e[efree].next=p.next;

p.next=efree;

efree++;//新空元素下標(biāo)}鄰接表的實現(xiàn)B（數(shù)組）Pascal語言

begin

readln(n,m);

//初始化鄰接鏈表“哨兵”

fori:=1tondo

g[i].next:=-1;

efree:=1;

//讀入邊，插入鄰接鏈表

fori:=1tomdobegin

readln(a,b);

ins(b,g[a]);

{ins(a,g[b]);//無向邊時}end;...C++語言

intmain(){

cin>>n>>m;efree=0;

//初始化鄰接鏈表“哨兵”

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

g[i].next=-1;

//讀入邊，插入鄰接鏈表

for(i=0;i<m;i++){

cin>>a>>b;

ins(b,g[a]);

//ins(a,g[b]);//無向邊時

}…鄰接表的實現(xiàn)B（數(shù)組）帶權(quán)圖的鄰接表存儲方法TypeLink=^Node;Node=Recordv,w:Longint;{頂點(diǎn)和費(fèi)用}Next:Link;End;Map:Array[1..Maxn]ofLink;{用鄰接表記錄的圖}

Read(n,m);Fori:=1tomdoBegin

Read(a,b,c);

New(p);

p^.v:=b;p^.w:=c;

p^.Next:=Map[a];

Map[a]:=p;End;Sec.2圖的遍歷和染色性圖的遍歷和染色性是解決一切圖論問題的根基，例如判斷圖的聯(lián)通性，判斷圖是否有環(huán)，判斷圖是否為二分圖，等等一些基本問題都要通過圖的遍歷和染色來進(jìn)行。這一步驟雖然很不起眼，但是在編程解題過程中往往都是一些最基本的步驟，整個問題的求解往往都是由它開始的。圖的遍歷

從圖中某一頂點(diǎn)出發(fā)，按某種搜索方法訪遍其余頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次。這一過程稱為圖的遍歷。遍歷圖的基本搜索方法有兩種：深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS。這兩種方法都適用于有向圖和無向圖。圖的深度優(yōu)先搜索遍歷

圖的深度優(yōu)先遍歷DFS算法是每次在訪問完當(dāng)前頂點(diǎn)后，首先訪問當(dāng)前頂點(diǎn)的一個未被訪問過的鄰接頂點(diǎn)，然后去訪問這個鄰接點(diǎn)的一個未被訪問過的鄰接點(diǎn)，這樣的算法是一個遞歸算法。

連通圖的深度優(yōu)先遍歷算法思想。（1）訪問初始頂點(diǎn)v并標(biāo)記頂點(diǎn)v已訪問。（2）查找頂點(diǎn)v的第一個鄰接頂點(diǎn)w。（3）若頂點(diǎn)v的鄰接頂點(diǎn)w存在，則繼續(xù)執(zhí)行；否則回溯到v，再找v的另外一個未訪問過的鄰接點(diǎn)。（4）若頂點(diǎn)w尚未被訪問，則訪問頂點(diǎn)w并標(biāo)記頂點(diǎn)w為已訪問。（5）繼續(xù)查找頂點(diǎn)w的下一個鄰接頂點(diǎn)wi，如果v取值wi轉(zhuǎn)到步驟（3）。直到連通圖中所有頂點(diǎn)全部訪問過為止。深度優(yōu)先遍歷的程序?qū)崿F(xiàn)：（鄰接表、Pascal）//圖的一般結(jié)構(gòu)

typegraph_node=record…end;typeAdjList=recordid:integer;next:^AdjList;end;

var

n_nodes,S_i:integer;nodes:array[1..maxN]ofgraph_node;visited:array[1..maxN]ofinteger;adj:array[1..maxN]of^AdjList;標(biāo)識項點(diǎn)有沒有訪問過每個頂點(diǎn)都有鄰接鏈表鄰接鏈表的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)深度優(yōu)先遍歷的程序?qū)崿F(xiàn)：（鄰接表、Pascal）置每個點(diǎn)標(biāo)識為“未訪問”從所有未被訪問的點(diǎn)k出發(fā)，調(diào)用DFS(k)proceduresearch();begink:integer;fork:=1ton_nodesdovisited[k]:=0;

fork:=1ton_nodesdoifvisited[k]<>0thenDFS(k);end;置被訪問節(jié)點(diǎn)的“時間”---次序訪問k的所有相鄰的節(jié)點(diǎn)

procedureDFS(k:integer);begin

//從k出發(fā)搜索

var

j:^AdjList;begininc(S_i);visited[k]:=S_i;j:=adj[k];while(j<>NULL)dobeginifvisited[j^.id]<>0thenDFS(j^.id);j:=j^.next;end;end;圖的廣度優(yōu)先搜索遍歷

圖的廣度優(yōu)先遍歷BFS算法是一個分層搜索的過程，和樹的層序遍歷算法類同，它也需要一個隊列以保持遍歷過的頂點(diǎn)順序，以便按出隊的順序再去訪問這些頂點(diǎn)的鄰接頂點(diǎn)。

連通圖的廣度優(yōu)先遍歷算法思想。

（1）頂點(diǎn)v入隊列。

（2）當(dāng)隊列非空時則繼續(xù)執(zhí)行，否則算法結(jié)束。

（3）出隊列取得隊頭頂點(diǎn)v；訪問頂點(diǎn)v并標(biāo)記頂點(diǎn)v已被訪問。

（4）查找頂點(diǎn)v的第一個鄰接頂點(diǎn)col。

（5）若v的鄰接頂點(diǎn)col未被訪問過的，則col入隊列。

（6）繼續(xù)查找頂點(diǎn)v的另一個新的鄰接頂點(diǎn)col，轉(zhuǎn)到步驟（5）。直到頂點(diǎn)v的所有未被訪問過的鄰接點(diǎn)處理完。轉(zhuǎn)到步驟（2）。廣度優(yōu)先遍歷的程序?qū)崿F(xiàn)：（鄰接表、C++）//圖的一般結(jié)構(gòu)

struct

graph_node{…};

struct

AdjList{

intid;

AdjList*next;};

int

n_nodes,S_index=0;

graph_nodenodes[maxN];

intvisited[maxN];

AdjList*adj[maxN];標(biāo)識項點(diǎn)有沒有訪問過每個頂點(diǎn)都有鄰接鏈表鄰接鏈表的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)廣度優(yōu)先遍歷的程序?qū)崿F(xiàn):（鄰接表、C++）置每個點(diǎn)標(biāo)識為“未訪問”從所有未被訪問的點(diǎn)k出發(fā)，調(diào)用BFS(k)voidsearch(){

intk;

for(k=0;k<n_nodes;k++)visited[k]=0;

for(k=0;k<n_nodes;k++)if(!visited[k])BFS(k);}寬度優(yōu)先遍歷的程序?qū)崿F(xiàn)：（鄰接表、C++）intq[maxN];voidBFS(intk){

int

front,back;q[0]=k;front=back=0;

for(;fron<=back;fron++){k=q[front];

visited[k]=++search_index;

for(Adjlist*j=adj[k];j!=NULL;j=j->next){if(!visited[j->id]){

q[++back]=j->id;

visited[j->id]=++S_index;}}}}BFS用的隊列，一般全局Front<=back,隊列不空訪問k的所有相鄰的節(jié)點(diǎn)

例1、雙棧排序(NOIP2008提高組)給出N(1<=n<=1000)個未排序的數(shù)，要求用兩個棧將它排好序。有4種操作：1、入棧12、出棧13、入棧24、出棧2必須滿足棧的先進(jìn)后出的性質(zhì)。不能排序則輸出-1可以排序則輸出字典序最小的操作序列。這道題的關(guān)鍵還是在于構(gòu)圖和染色。首先是構(gòu)圖：將所有數(shù)都看成點(diǎn)，兩個點(diǎn)ai和aj之間連一條邊的條件為ai和aj不能進(jìn)入同一個棧。而不能進(jìn)入同一個棧又如何判斷呢？如果存在k使得i<j<k且ak<ai<aj則ai和aj不能進(jìn)入同一個棧。構(gòu)圖完畢，問題就漸漸明朗了，如果圖中存在奇環(huán)則問題必然無解。然后按照輸入的順序?qū)D進(jìn)行二染色，染到1的入1棧，染到2的入2棧。這樣每個數(shù)字進(jìn)哪個棧都知道，剩下的就是模擬了。圖的連通分量最小生成樹問題（MST）橋和割頂Sec3.圖的連通性問題生成樹問題無向圖的最小生成樹（貪心思想）Prim算法，適用于點(diǎn)少的圖Kruskal算法，適用于邊少的圖有向圖的最小樹形圖局域網(wǎng)(net)某局域網(wǎng)內(nèi)有n(n<=100)臺計算機(jī)，由于建網(wǎng)時工作人員的疏忽，現(xiàn)在網(wǎng)內(nèi)存在回路，造成網(wǎng)絡(luò)卡的現(xiàn)象。我們用f(i,j)表示i,j之間連接的暢通程度(f(i,j)<=1000)，f(i,j)值越小表示i,j之間連接越通暢，f(i,j)為0表示i,j之間無網(wǎng)線連接?，F(xiàn)在我們需要除去一些連線，使得網(wǎng)絡(luò)中沒有回路，并且被除去網(wǎng)線的Σf(i,j)最大，請求出這個最大值。實際問題生成樹：一個|V|個點(diǎn)的圖，取其中|V|-1條邊，并連接所有的頂點(diǎn)，則組成原圖的一個生成樹。屬性：|v|-1條邊、連通、無環(huán)。最小生成樹：加權(quán)圖的最小生成樹是一棵生成樹，其所有邊的權(quán)值之和不會大于其它任何生成樹。簡單講：找出連接所有點(diǎn)的最低成本路線最小生成樹(MST）紅邊連接了所有頂點(diǎn),所以構(gòu)成一棵生成樹權(quán)和=1+2+4+4+7+8+9環(huán)屬性：一棵生成樹上，增加一條邊e，再刪除e所在環(huán)上的最大邊，會得到另一棵“更好”的生成樹(如果e不是最大邊)最小生成樹(MST)-----算法原理94剪切屬性：在圖中，剪切將頂點(diǎn)劃分成兩個不相交集合。交叉邊為這些頂點(diǎn)在兩個不同集合的邊。對于任何一個剪切，各條最小的交叉邊都屬于某個MST，且每個MST中都包含一條最小交叉邊。最小生成樹(MST)-----算法原理749最小邊原則：圖中權(quán)值最小的邊(如果唯一的話)一定在最小生成樹上。唯一性：一棵生成樹上，如果各邊的權(quán)都不相同，則最小生成樹是唯一的。反之不然。最小生成樹(MST)-----算法原理Prim算法構(gòu)建MST的過程將1號節(jié)點(diǎn)置入集合S中。找到所有連接S中的節(jié)點(diǎn)和非S中的節(jié)點(diǎn)的邊中的權(quán)值最小的那一條，并標(biāo)記這條邊，同時將連接的非S中的節(jié)點(diǎn)加入S集合。重復(fù)2步驟，直到所有節(jié)點(diǎn)都在S中了。1243561231231212算法描述1：(1)將G剪切成兩個集合A、B，A中只有一個點(diǎn)r

(2)取最小權(quán)的交叉邊(x,y)，x∈A,y∈B(3)將y加入A

(4)如果已經(jīng)加了n-1條邊，結(jié)束。否則，轉(zhuǎn)(3)最小生成樹(MST)-----Prim算法算法描述2：MST_Prim(G,r)//從任意點(diǎn)r出發(fā)，生長成一MSTfori=1tondo

dis[i]∞//初始化每點(diǎn)到A集合的最小值

inA[i]false//設(shè)頂點(diǎn)不在A中dis[r]0

//將r設(shè)為0（或-∞），準(zhǔn)備取出fori=1tondovget-min()//取dis[?]中最小的值c和頂點(diǎn)v,

inA[v]true//v放入A中

sumsum+c

//c加入MST的總和中

updata(v)//枚舉交叉邊(v,B),改進(jìn)dis[]最小生成樹(MST)-----Prim算法算法要點(diǎn)：每次求最小權(quán)交叉邊時，如果都重新計算，則顯然要枚舉(x,y)---x∈A,y∈B。O(n^2)時間復(fù)雜度。其實每次A中只是增加一個新頂點(diǎn)v，最多有交叉邊(v,y)，修改量只有與v有邊的頂點(diǎn)，為O(n)。只需記錄下B中的每個元素y與A所有元素中最小權(quán)邊，則求最小值最多為O(n)---有時可以用“堆”優(yōu)化。

最小生成樹(MST)-----Prim算法

Kruskal算法同樣是常用的求最小生成樹的算法之一，其算法思想如下：

Kruskal算法每次選擇n-1條邊，所使用的貪婪準(zhǔn)則是：從剩下的邊中選擇一條不會產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不可能形成一棵生成樹。Kruskal算法分e步，其中e是網(wǎng)絡(luò)中邊的數(shù)目。按耗費(fèi)遞增的順序來考慮這e條邊，每次考慮一條邊。當(dāng)考慮某條邊時，若將其加入到已選邊的集合中會出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。

這個算法可以用并叉集優(yōu)化到o(e*ɑ(e))的時間復(fù)雜度。(ɑ表示阿克曼反函數(shù))

最小生成樹(MST)-----Kruskal算法找到連接兩個不同連通分量（由已標(biāo)記的邊構(gòu)成的）的邊中，權(quán)值最小的那一條，標(biāo)記這條邊。重復(fù)1步驟，直到所有節(jié)點(diǎn)都在同一連通分量中。1243561231231212最小生成樹(MST)-----Prim算法MST_Kruskal(G)(1)將G所有條邊按權(quán)從小到大排序；圖mst開始為空

(2)從小到大次序取邊(x,y)(3)若加入邊(x,y)，mst就有環(huán)，則放棄此邊，轉(zhuǎn)(2)

(4)將邊(x,y)加入mst，如果已經(jīng)加了n-1條邊，結(jié)束。否則，轉(zhuǎn)(2)最小生成樹(MST)-----Kruskal算法算法要點(diǎn)：

Kruskal算法的最難點(diǎn)在于怎樣判斷加入邊(x,y)后是否形成了環(huán)。問題可化為：判斷邊(x,y)的兩個頂點(diǎn)x,y在圖（實際是森林）mst中是否已經(jīng)連通。如果已經(jīng)連通，加入邊將形成環(huán)；否則，不形成環(huán)。

并查集：連通點(diǎn)集之類問題，有高效算法---并查集。最小生成樹(MST)-----Kruskal算法算法描述：MST_Kruskal(G)

fori=1tondof[i]i;//初始化并查集

sort(e,e+m);//邊按大小排序c0;//取邊的計數(shù)器fori=1tomdo

//從小到大取邊vfind_set(e[i].v);//左端點(diǎn)所在連通塊“根”ufind_set(e[i].u);//右端點(diǎn)所在連通塊“根

if(u,v

不在同一連通塊上)//如果不在同一連通塊

union(v,u);//合并兩連通塊sum=sum+g[v][u];//加入這條邊的權(quán)if(++c==n-1)break;//if取了n-1條邊，結(jié)束最小生成樹(MST)-----Kruskal算法時間復(fù)雜度分析Prim算法普通的方法

O(|V|2)

Prim算法中用“堆”方法O((|E|+|V|)*log|V|)---對稀疏圖較好Kruskal算法O(|E|*log|E|+|N|*A(|V|))---對稀疏圖較好最小生成樹(MST)-----時間復(fù)雜度次小生成樹根據(jù)kruskal算法，不難證明，任意一棵次小生成樹必然是由最小生成樹換掉一條邊。如何實現(xiàn)?1、先求最小生成樹。O((E+V)logE)2、在生成樹上DFS求出任意兩點(diǎn)間路徑上的最大邊權(quán)F[I][J]。O(V^2)3、窮舉所有不在生成樹上的邊e=<s,t>，求出min{w[e]-F[s][t]}。O(E)時間復(fù)雜度：O((E+V)logE)例2、hurdles(USACO)給出一個N(1<=n<=300)個點(diǎn)M(1<=m<=25,000)條邊的無向圖，給出T(1<=t<=40,000)個詢問，詢問要求尋找一條從節(jié)點(diǎn)s，到節(jié)點(diǎn)t的路徑使得該路徑的邊權(quán)的最大值最小，只需輸出最大值即可。Hurdles.in56212123281352533442483412Hurdles.out48樸素想法：對于每次詢問做一遍DFS時間復(fù)雜度：O(T*M)標(biāo)準(zhǔn)算法：1、求出原圖的最小生成樹。2、對于每個詢問，在最小生成樹上進(jìn)行DFS找出最大邊即可。時間復(fù)雜度：O((N+M)*logM+T*N)最小生成樹的應(yīng)用示例（構(gòu)圖）Newstart.pdf最小生成樹的動態(tài)維護(hù)公路建設(shè)

與其實說橋和割頂，不如說是圖的dfs樹的運(yùn)用。而橋和割頂，只是dfs樹的一個比較重要的運(yùn)用。圖的dfs樹即對圖進(jìn)行深度優(yōu)先遍歷所形成的一棵樹。性質(zhì)：任何一棵圖的dfs樹不能可能有橫向邊而只可能有返祖邊。橋和割頂橋和割頂橋：定義：連通圖中的一條邊，如果刪去這一條邊，那么整個圖就不再連通了。割頂：連通圖中的一個點(diǎn)，如果刪去這個點(diǎn)和相關(guān)的邊，那么整個圖就不再連通了。（這里只討論無向圖中的橋和割頂）ACBGDFE在左圖中，DE之間的邊即為這張圖中唯一的一個橋。而D,E則分別為這張圖中的兩個割頂。ACBGDFEABDCEFG在dfs樹中，我們不難發(fā)現(xiàn)，對于一個橋，必然沒有一條返祖邊跨越這條邊，反之，則必然存在一條返祖邊跨越這條邊。橋和割頂橋和割頂

考慮到上面的這一個性質(zhì)，我們就可以引入時間戳來求一個圖的橋了。要判斷一條邊是不是橋，只需要看它的子樹中，有沒有一條返祖邊返回到這條邊的上面。因此，我們對于每個節(jié)點(diǎn)，維護(hù)一個訪問時間和它的子樹的最早訪問時間。由于dfs樹沒有橫向邊，這一點(diǎn)很好地保證了，一個節(jié)點(diǎn)的子樹的最早訪問時間比這個節(jié)點(diǎn)的訪問時間早，那么就存在一條返祖邊返回到這個節(jié)點(diǎn)的祖先。通過這種方式，我們就能夠求出一個圖中的橋了。偽代碼：Dfs(u){t=t+1;

time[u]=t;

min_time[u]=t

vst[u]=true;

for(u,v)∈Edo{if(vst[v]=false){

dfs(v);

min_time[u]=min(min_time[u],min_time[v]);}elsemin_time[u]=min(min_time[u],time[v]);}if(min_time[u]<time[u])u節(jié)點(diǎn)到父親的邊不是橋}橋和割頂橋和割頂思考：如何求一個圖的割頂？（與求圖的橋非常的相似）只需要考慮一個節(jié)點(diǎn)的所有子樹（不包括該節(jié)點(diǎn)本身）是否有返祖邊即可。（計算橋的時候需要考慮該節(jié)點(diǎn)本身）Sec4.最短路

最短路，是圖論中最基本的問題，也有著廣泛的運(yùn)用。解決這一問題的算法也有很多種。今天，主要就介紹一些較為常見的最短路算法。全局最短路徑算法：Floyd單源最短路徑算法：Dijkstra Bellman-ford SPFA最短路徑：對在權(quán)圖G=(V,E),從一個源點(diǎn)s到匯點(diǎn)t有很多路徑，其中路徑上權(quán)和最少的路徑，稱從s到t的最短路徑。簡單講：找出連接兩個給定點(diǎn)的最低成本路徑單源最短路徑問題：求從源點(diǎn)s到其它所有點(diǎn)的最短路徑問題。最短路徑(ShortestPath)-----定義三角形性質(zhì)設(shè)源點(diǎn)s到點(diǎn)x、y的最短路徑長度為dis[x]、dis[y]。x與y之間的距離是len[x][y]，則有下面的“三角形定理”：

dis[x]+len[x][y]>=dis[y]

松馳若在處理過程中，有兩點(diǎn)x、y出現(xiàn)不符合“三角形定理”，則可改進(jìn)一下—松馳：

if(dis[x]+len[x][y]<dis[y])

dis[y]=dis[x]+len[x][y];最短路徑(ShortestPath)-----屬性XYS如果邊沒有負(fù)權(quán)的，我們可以用類似Prim算法的貪心算法—Dijkstra算法。算法描述1：SP_Dijkstra(G,s)(1)將G中頂點(diǎn)分成兩個集合A、B，A集合中由已經(jīng)求出最短路徑的頂點(diǎn)組成，B集合是其它頂點(diǎn)。開始時A中只有一個點(diǎn)s

(2)從B集合中取一個當(dāng)前最短的頂點(diǎn)v(3)把v加入A集合，并對v相連的頂點(diǎn)試做“松馳”

(4)如果|A|=|V|，結(jié)束。否則轉(zhuǎn)(2)最短路徑-----Dijkstra算法Dijkstra算法Dijkstra算法中心——++124331632+∞+∞+∞0Dist值4321節(jié)點(diǎn)號32654選擇標(biāo)記擴(kuò)展算法描述2：SP_Dijkstra(G,s)//求單源s到其它點(diǎn)的最短距離fori=1tondodis[i]∞//初始化每點(diǎn)到s距離

inA[i]false//設(shè)頂點(diǎn)不在A中dis[s]0

//將dis[s]設(shè)為0，準(zhǔn)備取出fori=1tondovget-min()//取dis[?]中最小的值c和頂點(diǎn)v,

inA[v]true//v放入A中

updata(v)//檢查(v,B),松馳dis[?]sumsum+c

//c加入MST的總和中最短路徑-----Dijkstra算法與prim不相同點(diǎn)如果邊有負(fù)權(quán)的話，Dijkstra算法是錯誤的。這里需要不斷迭代地做“松馳”，直到無“松馳”為止。算法描述3：SP_Bellman(G,s)(1)初始化每點(diǎn)到s點(diǎn)的最短距離為∞

(2)取所有邊(x,y)，看x能否對y松馳。(3)如果沒有任何松馳，則結(jié)束break。

(4)如果松馳次數(shù)<N，轉(zhuǎn)(2)(5)否則，圖中有“負(fù)圈”。最短路徑-----Bellman-ford算法算法說明：Bellman-ford算法N次迭代就可以判斷圖中是否有“負(fù)環(huán)”。取所有邊有兩種方法：

(1)掃描每一點(diǎn)的鄰接鏈表

(2)用有序點(diǎn)對(x,y)記錄邊時，可直接取邊。但要請注意對無向圖，要注意(y,x)也要松馳。對于求s到某點(diǎn)t的最短距離，可能因為其它地方有“負(fù)環(huán)”而出現(xiàn)問題，要預(yù)處理。最短路徑-----Bellman-ford算法算法描述4：SP_Bellman(G,s)//求單源s到其它點(diǎn)的最短距離fori=1tondodis[i]∞//初始化每點(diǎn)到s距離dis[s]0

//將dis[s]設(shè)為0fori=1tondo

//最多迭代n

rel=false;//是否有松馳標(biāo)志

for每條邊(x,y)//取圖的每一條邊if(dis[x]+len[x][y]<dis[y])

//不滿足三角形性質(zhì)

dis[y]=dis[x]+len[x][y];

//松馳dis[y]

rel=true;ifrel=falsereturn0;//沒有一次松馳，則結(jié)束return-1;//迭代了n次，有負(fù)圈最短路徑-----Bellman-ford算法對迭代的改進(jìn)：SPFA算法

Bellman-ford算法中，每次都要檢查所有的邊。這個看起來比較浪費(fèi)，對于邊(x,y)，如果上一次dis[x]沒有改變，則本次的檢查顯然是多余的。我們每次只要從上次剛被“松馳”過的點(diǎn)x，來看看x能不能松馳其它點(diǎn)即可。

SPFA算法中用BFS中的隊列來存放剛被“松馳”過的點(diǎn)。由于頂點(diǎn)個數(shù)為|V|，隊列如果用數(shù)組的話顯然要用“循環(huán)隊列”使用空間。最短路徑-----SPFA算法算法描述：SP_SPFA(G,s)//求單源s到其它點(diǎn)的最短距離fori=1tondodis[i]∞;vis[i]false;

//初始化每點(diǎn)到s距離,不在隊列dis[s]0;//將dis[s]設(shè)為0vis[s]true;count1;

//s放入隊列head0;tail

0;q[0]=s;

//隊列頭尾指針while(count>0)dovq[head];//隊頭節(jié)點(diǎn)vfor每條邊(v,i)//與v相連的每一條邊if(dis[v]+len[v][i]<dis[i])

//不滿足三角形性質(zhì)

dis[i]

dis[v]+len[v][i];

//松馳dis[i]

if(vis[i]=false)//不在隊列，則加入隊列

vis[i]true;count+1;tail+1;q[tail]=i;

vis[v]false;head+1;count-1;//v出隊列最短路徑-----SPFA算法求每對節(jié)點(diǎn)之間最短距離問題：例如，求一個圖的直徑，即所有最短路徑中最長的。如果多次調(diào)用單源最短路徑算法，效果并不好。特別是對有負(fù)邊的圖。如果無負(fù)環(huán)，則有簡單的Floyd-warshell算法。這是動態(tài)規(guī)劃算法。最短路徑-----Floyd算法動態(tài)規(guī)劃算法定義d[i,j,k]為路徑中間只允許經(jīng)過節(jié)點(diǎn)1…k的情況下i到j(luò)的最短路距離它有兩種情況最短路經(jīng)過點(diǎn)k，d[i,j,k]=d[i,k,k-1]+d[k,j,k-1]最短路不經(jīng)過點(diǎn)k，d[i,j,k]=d[i,j,k-1]綜合起來，狀態(tài)轉(zhuǎn)移方程為

d[i,j,k]=min{d[i,k,k-1]+d[k,j,k-1],d[i,j,k-1]}邊界條件

d[i,j,0]=len[i][j]（不存在的邊權(quán)可為∞）最短路徑-----Floyd算法算法描述6：SP_Floyd(G)//求每對節(jié)點(diǎn)的最短距離fori=1tondo

forj=1tondo

dis[i,j]len[i][j];

//初始化邊界條件fork=1tondo//K放在最外層，數(shù)組少一維

fori=1tondoforj=1tondoif(dis[i,k]+dis[k][j]<dis[i,j])

//狀態(tài)轉(zhuǎn)移

dis[i,j]

dis[i][k]+dis[k][j];

最短路徑-----Floyd算法Floyd算法主要用于解決一類全局最短路的問題。優(yōu)點(diǎn)：常數(shù)小，編程復(fù)雜度低缺點(diǎn)：時間復(fù)雜度高，往往無法解決一類單源最短路的問題Fori=1ton1.取V-S中的一頂點(diǎn)u使dis[u]=min{dis[v]|v∈V-S}2.S=S+{u}3.ForV-S中每個頂點(diǎn)vdoRelax(u,v,W)Dijkstra算法優(yōu)化：

1.用臨接表存邊

2.用二叉堆（最小堆）維護(hù)V-S集合中節(jié)點(diǎn)當(dāng)前dis值算法復(fù)雜度從O(V^2)降到O((V㏒V+E)

Dijkstra算法最為經(jīng)典的解決單源最短路徑的算法不優(yōu)化：優(yōu)點(diǎn)：編程復(fù)雜度低缺點(diǎn)：時間復(fù)雜度不是很理想，所有邊權(quán)必須非負(fù)

優(yōu)化后：有點(diǎn)：時間復(fù)雜度理想缺點(diǎn)：編程復(fù)雜度略高（如果用c++選手用優(yōu)先隊列，可能空間復(fù)雜度較高），所有邊權(quán)必須非負(fù)

Bellman-ford算法基本流程：對每一條邊，都進(jìn)行V次松弛操作。如果不存在負(fù)權(quán)環(huán)，可以證明，任意一條最短路都至多經(jīng)過V個點(diǎn)，這一點(diǎn)保證了算法的正確性。此外，Bellman-ford算法還可以用于判斷一個圖中是否有負(fù)權(quán)環(huán)，經(jīng)過V次操作后，再進(jìn)行一次松弛操作，如果還有邊可以松弛，則說明該圖存在負(fù)權(quán)環(huán)。偽代碼：fori=1to|V|-1do

for(u,v)∈Edo

relax(u,v,w);判斷負(fù)權(quán)環(huán)

for(u,v)∈Edo

Ifdis[u]+w<dis[v]returnfalse時間復(fù)雜度太高?。?！優(yōu)化：SPFA算法

在Bellman-ford算法的實現(xiàn)過程中，實際上我們進(jìn)行了大量的冗余計算。尤其是在后面的松弛過程中，枚舉每一條邊事實上浪費(fèi)了大量的時間。由此，我們引入了SPFA算法。SPFA算法的本質(zhì)還是Bellman-ford，但是它通過一個隊列，去掉了大量的冗余計算，大大加速了算法。While(Q!=empty){u=Q.top;for(u,v)∈Edoif(relax(u,v,W)and(v∈V-Q)) Q=Q+v;Q=Q-u;}時間復(fù)雜度O(K*E)Dijkstra單源非負(fù)

O(|V|2)對稠密圖好可用“堆”優(yōu)化

O(|E|*log|V|)對稀疏圖較好Bellman-Ford單源無負(fù)環(huán)

O(|V|*|E|)可先用Dijkstra預(yù)處理優(yōu)化SPFA用更新隊列優(yōu)化,時間復(fù)雜度平均好，但不確定。Floyd全源無負(fù)環(huán)

O(|V|3)最短路徑-----算法比較例3、phoneline(USACO)

有N(1<=n<=1000)個點(diǎn)，M(1<=m<=10000)條邊，尋找一條從結(jié)點(diǎn)1到結(jié)點(diǎn)N的路徑，使得其中各邊長度的最大值最小。并且給定一個整數(shù)K(0<=k<=300)，可以使路徑中的K條邊長度變?yōu)榱恪Ｇ笞钚〉哪莻€最大值。乍看和最短路沒有關(guān)系，因為要求最大值最小。二分答案？1、對邊按照長度排序。2、二分要輸出的最小的最大值P。3、把所有邊長小于等于P的邊長度標(biāo)為0，大于P的邊長度標(biāo)為1。4、做一次單源最短路徑，求出1到N的最短路徑，看是否小于K。時間復(fù)雜度：Dijkstra:N^2*logM懸！Dijkstra

堆優(yōu)化:(NlogN+M)logM可行！SPFA:由于邊權(quán)有許多0，松弛次數(shù)不會很多可行！例4、block(USACO)Bessie來到一個小農(nóng)場，有時她想回老家看看她的一位好友。她不想太早地回到老家，因為她喜歡途中的美麗風(fēng)景。她決定選擇次短路徑，而不是最短路徑。農(nóng)村有R(1<=R<=100,000)條雙向的路，每條路連接N(1<=N<=5000)個結(jié)點(diǎn)中的兩個。結(jié)點(diǎn)的編號是1..N。Bessie從結(jié)點(diǎn)1出發(fā)，她的朋友(目的地)在結(jié)點(diǎn)N。次短路徑可以使用最短路徑上的路，而且允許退回，即到達(dá)一個結(jié)點(diǎn)超過一次。次短路徑是一種長度大于最短路徑的路徑(如果存在兩條或多條最短路徑存在，次短路徑就是比它們長，且不比其他任何的路徑長的路徑)。典型的次短路徑算法并不復(fù)雜在記錄最短路徑的Dist[i]數(shù)組中同時存放到i點(diǎn)的最短路徑和次短路徑，記作Dist[i][1]和Dist[i][2]，在做松弛操作的時候同時更新最短路徑和次短路徑。第一遍每次都選取Dist[i][1]最小的進(jìn)行松弛，在Dist[i][1]全部都松弛一遍后再選取Dist[i][2]最小的進(jìn)行松弛。時間復(fù)雜度同最短路徑拓?fù)渑判蛟趫D論中有著重要的地位，在歷屆NOIP中，對這方面的內(nèi)容也有所考察，比如03年的神經(jīng)網(wǎng)絡(luò)等等。拓?fù)渑判蚴轻槍τ邢驘o環(huán)圖而言的。拓?fù)渑判蚝笮纬傻男蛄袧M足這樣一個條件：不存在兩個點(diǎn)u,v，u在序列中在v之前并且v在圖中是u的前驅(qū)。1243657對于右圖，一個滿足條件的拓?fù)湫蛄惺?234567。然而1235764則不滿足條件，因為7在序列中在4之前，但是4是7的前驅(qū)。Sec.5拓?fù)渑判蛲負(fù)渑判?/p>

我們可以通過一個隊列來解決這一類問題。我們每次把入度為0的點(diǎn)入隊，然后依次處理這些點(diǎn)，將這些點(diǎn)的出邊刪除，刪除時，順便將新造成的入度為0的點(diǎn)入隊，處理完某個點(diǎn)后，這個點(diǎn)出隊。如此操作，直到隊列為空。如果還存在某個點(diǎn)沒有入過隊，這說明這個有向圖存在環(huán)。偽代碼：While(Q!=empty){u=Q.top;for(u,v)∈Edo{

dec(cnt[v])if(cnt[v]=0)Q=Q+v;}Q=Q-u;

}拓?fù)渑判蛩惴▽ふ胰攵葹?的節(jié)點(diǎn)將找到的節(jié)點(diǎn)放入隊列中，刪除所有這個節(jié)點(diǎn)引出的邊重復(fù)1，直至沒有度為0的節(jié)點(diǎn)如果有節(jié)點(diǎn)不在隊列中，則說明原圖中有環(huán)，否則無環(huán)。1253647求關(guān)鍵路徑算法對給定的圖進(jìn)行拓?fù)渑判虬凑胀負(fù)渑判虻慕Y(jié)果擴(kuò)展和標(biāo)記12345687964511247924Sec6.網(wǎng)絡(luò)流與匹配問題網(wǎng)絡(luò)最大流最小費(fèi)用最大流二分圖的最大匹配二分圖的最佳匹配網(wǎng)絡(luò)流算法尋找增廣鏈，并根據(jù)增廣鏈修改流量。重復(fù)這一步驟，直到不再存在增廣鏈。如果需要在此基礎(chǔ)上求最小費(fèi)用最大流，只需從增廣鏈的選擇上著手。二分圖與匹配算法二分圖的匹配算法又稱匈牙利算法匈牙利算法的中心——可增廣軌不斷尋找可增廣軌，并根據(jù)可增廣軌修改匹配最佳匹配只是在選擇可增廣軌時，將匹配的權(quán)值作為選擇的條件圖的應(yīng)用(模型構(gòu)建)

例題1:(TRAVEL)

一個城市中有N個車站，已知M條連接這些車站的公共汽車單向路線，設(shè)計算法求出從第一號車站到第N號車站的最少換車次數(shù).分析這道題粗看起來似乎不太簡單，但我們仔細(xì)分析一下題目就會發(fā)現(xiàn)，這道題實際上可以轉(zhuǎn)化為最短路徑問題來進(jìn)行求解?？紤]經(jīng)過的所有路線中，每條路線都只保留一頭一尾兩個車站，則經(jīng)過的車站數(shù)目再減2實際上就是所求的換車次數(shù)了。要使換車次數(shù)最少，也就是要找從1到N的一條最短路徑。而圖中的邊也需要重新設(shè)計。在每一條路線中，任兩個結(jié)點(diǎn)均由其中的前者向后者連一條邊，然后將每條邊的長度都定為1。利用圖論模型進(jìn)行構(gòu)造例題2：圓桌吃飯問題

n個人圍著一張圓桌吃飯，每個人都不愿意兩天與同一人為鄰，問最多能坐多少天，并給出一種排列方案？轉(zhuǎn)化為圖論模型

設(shè)G=(V,E)為一完全圖，|V|=n。圖中的每個頂點(diǎn)代表一個人，連結(jié)頂點(diǎn)的邊表示人之間的相鄰關(guān)系。因此，每種圍繞圓桌的吃飯方案就成為圖中的一條哈密爾頓回路。設(shè)L=<v1,v2,…,vn>為G中的一條哈密爾頓回路，其中所含的邊的集合記為e(L)。問題轉(zhuǎn)化為：求m與L1,L2,…,Lm，使得e(Li)∩e(Lj)=φ，并且m達(dá)到最大值。構(gòu)造方法

作一圓，把圓周分成n-1等分，標(biāo)上n-1個刻度，將頂點(diǎn)1至n-1依次排列在圓周上，頂點(diǎn)n放在圓心。先從圓心出發(fā)，向任意點(diǎn)連一條線，再從這點(diǎn)出發(fā)，沿圓周向左右兩個方向迂回連線，直到連完圓周上所有的點(diǎn)，再連回圓心。這樣就構(gòu)造出一條哈密爾頓回路。保持所有的頂點(diǎn)位置不變，把所有連線圍繞圓心逆時針方向旋轉(zhuǎn)一個刻度，得到一條新的哈密爾頓回路。這樣連續(xù)旋轉(zhuǎn)(n-1)div2次，就得到了(n-1)div2條回路。N=5當(dāng)n=5時構(gòu)造圖象，充分展示各變量之間的關(guān)系

【例3】01串問題(NOI)

給定N,L0,A0,B0,L1,A1,B1，設(shè)計一個長度為N的01串，使得對于任何連續(xù)的長度為L0的子串，0的個數(shù)大于等于A0,且小于等于B0,對于任何連續(xù)的長度為L1的子串，1的個數(shù)大于等于A1且小于B1。【解題分析】模式1分析不等式

設(shè)hi為01子串s0..si(1<=I<=n)中1的個數(shù)，其中s0=0,h0=0。顯然，由hi的定義可以得出不等式0<=hi-1<=hi,hi<=hi-1+1,移項即得：

0<=hi-hi-1

-1<=hi-1-hiL0-b0<=hi-hi-l0

當(dāng)I>=L0時，根據(jù)條件，Si-L0+1…Si中0的個數(shù)(L0-(hi-hi-L0))在a0～b0之間，即a0<=L0-(hi-hi-L0)<=b0

a0-L0<=hi-L0-hi-b1<=hi-l1-hi

當(dāng)I>=L1時，根據(jù)條件，Si-L1+1…

Si中1的個數(shù)(hi-hi-L1)在a1～b1之間，即a1<=hi-hi-L1<=b1。a1<=hi-hi-L1

一旦有了h序列，我們可以由左至右構(gòu)造s串：如果hi-1=hi，則說明si=0；否則si=1(1<=I<=n)。由此看來，問題的關(guān)鍵是如何計算h序列。

仔細(xì)觀察上述推論條件，發(fā)現(xiàn)有以下特點(diǎn)：（1）除h0=0外，其余的條件都是由“<=”連接的不等式

（2）

每個不等式都是含兩個h未知數(shù)、一個常數(shù)的一次不等式；可見，所有不等式都整理成了k<=hi-hj

它給我們啟示，上述不等式類似于連接兩點(diǎn)的一條有向邊。因此，我們聯(lián)想到信息學(xué)解題中常用的圖論知識。

模型2構(gòu)造有向圖G

我們構(gòu)造有向圖G，如圖：

其中vi代表s串中的第I位。若k<=vi-vj,則vi向vj引出一條權(quán)為k的有向邊<vi,vj>,表明si…sj中至少需增加k個1（k為正值）或減少k個1(k為負(fù)值)。由此得出構(gòu)造有向圖G的方法：

0<=hi-hi-1

-1<=hi-1-hi

a0-L0<=hi-L0-hi

L0-b0<=hi-hi-l0a1<=hi-hi-L1-b1<=hi-l1-hi

計算圖G的最長路徑：我們已構(gòu)造了一個有n+1個頂點(diǎn)的有向圖G。

（1）圖G中無環(huán)令D[I]表示從頂點(diǎn)0到頂點(diǎn)I的最長路徑長度。對于圖中每條從點(diǎn)I指向點(diǎn)J的權(quán)為C[I,J]的邊，有性質(zhì)

D[I]+C[I,J]<=D[J]（注意：這與上述不等式的形式相似）這樣，令hi=D[I]，h完全符合所有限制條件，即為原不等式組的一組解。

（2）G中含有環(huán)可用反證法證明無解。從s1出發(fā)，順序確定每位二進(jìn)制數(shù)。當(dāng)hi=hi-1時，說明s1…si-1中1的個數(shù)與s1…si中1的個數(shù)相同，即si為0；否則si為1。

最短路例題4：求第一、第二、