圖論算法與模型構建

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

拓撲排序流量問題匹配問題

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

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

①V稱為G的頂點集,V≠,其元素稱為頂點或結點,簡稱點;②

E稱為G的邊集,其元素稱為邊,它聯結V中的兩個點,如果這兩個點是無序的,則稱該邊為無向邊,否則,稱為有向邊.

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

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

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

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

=n

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

),|E|

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

有邊聯結的兩個點稱為相鄰的點,有一個公共端點的邊稱為相鄰邊.邊和它的端點稱為互相關聯.常用d(v)表示圖G中與頂點v關聯的邊的數目,

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

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

定義2若將圖G的每一條邊e都對應一個實數F(e),則稱F(e)為該邊的權,并稱圖G為賦權圖(網絡),記為G=(V,E,F).

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

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

定義4任意兩點均有通路的圖稱為連通圖.

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

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

maxv=10000;typeTnode=record//定義頂點類型

c:integer;//頂點編號

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

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

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

maxv=10000;struct

Tnode{//定義頂點類型

intc;//頂點編號

Tnode*next;//此點的鄰接鏈表};//數組g表示每個頂點的鄰接鏈表//的鏈表頭---哨兵

Tnode

g[maxv];

int

n,m,i,a,b;

Tnode*t;圖G有n個頂點，編號從1到n。有m條有向邊，輸入時每行兩個整數ab，表示邊為從頂點a連接到頂點b。下面程序用指針實現圖的鄰接鏈表。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]);//無向邊時

}//…鄰接表的實現A（指針）Pascal語言constmaxV=1000;//最多頂點數

maxE=10000;//最多邊數typeTnode=record//定義頂點類型

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

next:integer;//此節(jié)點的鄰接鏈表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;//新空元素下標end;C++語言constint

maxV=1000,//最多頂點數

maxE=10000;//最多邊數struct

Tnode{//定義頂點類型

intc;//頂點編號

intnext;//此點的鄰接鏈表};//數組g表示每個頂點的鄰接鏈表//的鏈表頭---哨兵

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++;//新空元素下標}鄰接表的實現B（數組）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]);//無向邊時

}…鄰接表的實現B（數組）帶權圖的鄰接表存儲方法TypeLink=^Node;Node=Recordv,w:Longint;{頂點和費用}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圖的遍歷和染色性圖的遍歷和染色性是解決一切圖論問題的根基，例如判斷圖的聯通性，判斷圖是否有環(huán)，判斷圖是否為二分圖，等等一些基本問題都要通過圖的遍歷和染色來進行。這一步驟雖然很不起眼，但是在編程解題過程中往往都是一些最基本的步驟，整個問題的求解往往都是由它開始的。圖的遍歷

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

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

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

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;標識項點有沒有訪問過每個頂點都有鄰接鏈表鄰接鏈表的節(jié)點數據結構深度優(yōu)先遍歷的程序實現：（鄰接表、Pascal）置每個點標識為“未訪問”從所有未被訪問的點k出發(fā)，調用DFS(k)proceduresearch();begink:integer;fork:=1ton_nodesdovisited[k]:=0;

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

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算法是一個分層搜索的過程，和樹的層序遍歷算法類同，它也需要一個隊列以保持遍歷過的頂點順序，以便按出隊的順序再去訪問這些頂點的鄰接頂點。

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

（1）頂點v入隊列。

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

（3）出隊列取得隊頭頂點v；訪問頂點v并標記頂點v已被訪問。

（4）查找頂點v的第一個鄰接頂點col。

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

（6）繼續(xù)查找頂點v的另一個新的鄰接頂點col，轉到步驟（5）。直到頂點v的所有未被訪問過的鄰接點處理完。轉到步驟（2）。廣度優(yōu)先遍歷的程序實現：（鄰接表、C++）//圖的一般結構

struct

graph_node{…};

struct

AdjList{

intid;

AdjList*next;};

int

n_nodes,S_index=0;

graph_nodenodes[maxN];

intvisited[maxN];

AdjList*adj[maxN];標識項點有沒有訪問過每個頂點都有鄰接鏈表鄰接鏈表的節(jié)點數據結構廣度優(yōu)先遍歷的程序實現:（鄰接表、C++）置每個點標識為“未訪問”從所有未被訪問的點k出發(fā)，調用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)先遍歷的程序實現：（鄰接表、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é)點

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

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

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

dis[i]∞//初始化每點到A集合的最小值

inA[i]false//設頂點不在A中dis[r]0

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

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

sumsum+c

//c加入MST的總和中

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

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

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

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

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

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

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

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

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

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

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

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

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

if(u,v

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

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

O(|V|2)

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

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

考慮到上面的這一個性質，我們就可以引入時間戳來求一個圖的橋了。要判斷一條邊是不是橋，只需要看它的子樹中，有沒有一條返祖邊返回到這條邊的上面。因此，我們對于每個節(jié)點，維護一個訪問時間和它的子樹的最早訪問時間。由于dfs樹沒有橫向邊，這一點很好地保證了，一個節(jié)點的子樹的最早訪問時間比這個節(jié)點的訪問時間早，那么就存在一條返祖邊返回到這個節(jié)點的祖先。通過這種方式，我們就能夠求出一個圖中的橋了。偽代碼：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é)點到父親的邊不是橋}橋和割頂橋和割頂思考：如何求一個圖的割頂？（與求圖的橋非常的相似）只需要考慮一個節(jié)點的所有子樹（不包括該節(jié)點本身）是否有返祖邊即可。（計算橋的時候需要考慮該節(jié)點本身）Sec4.最短路

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

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

松馳若在處理過程中，有兩點x、y出現不符合“三角形定理”，則可改進一下—松馳：

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

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

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

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

inA[i]false//設頂點不在A中dis[s]0

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

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

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

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

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

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

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

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

//將dis[s]設為0fori=1tondo

//最多迭代n

rel=false;//是否有松馳標志

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

//不滿足三角形性質

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

//松馳dis[y]

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

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

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

//初始化每點到s距離,不在隊列dis[s]0;//將dis[s]設為0vis[s]true;count1;

//s放入隊列head0;tail

0;q[0]=s;

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

//不滿足三角形性質

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é)點之間最短距離問題：例如，求一個圖的直徑，即所有最短路徑中最長的。如果多次調用單源最短路徑算法，效果并不好。特別是對有負邊的圖。如果無負環(huán)，則有簡單的Floyd-warshell算法。這是動態(tài)規(guī)劃算法。最短路徑-----Floyd算法動態(tài)規(guī)劃算法定義d[i,j,k]為路徑中間只允許經過節(jié)點1…k的情況下i到j的最短路距離它有兩種情況最短路經過點k，d[i,j,k]=d[i,k,k-1]+d[k,j,k-1]最短路不經過點k，d[i,j,k]=d[i,j,k-1]綜合起來，狀態(tài)轉移方程為

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]（不存在的邊權可為∞）最短路徑-----Floyd算法算法描述6：SP_Floyd(G)//求每對節(jié)點的最短距離fori=1tondo

forj=1tondo

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

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

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

//狀態(tài)轉移

dis[i,j]

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

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

1.用臨接表存邊

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

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

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

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

for(u,v)∈Edo

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

for(u,v)∈Edo

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

在Bellman-ford算法的實現過程中，實際上我們進行了大量的冗余計算。尤其是在后面的松弛過程中，枚舉每一條邊事實上浪費了大量的時間。由此，我們引入了SPFA算法。SPFA算法的本質還是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;}時間復雜度O(K*E)Dijkstra單源非負

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

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

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

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

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

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

我們可以通過一個隊列來解決這一類問題。我們每次把入度為0的點入隊，然后依次處理這些點，將這些點的出邊刪除，刪除時，順便將新造成的入度為0的點入隊，處理完某個點后，這個點出隊。如此操作，直到隊列為空。如果還存在某個點沒有入過隊，這說明這個有向圖存在環(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;

}拓撲排序算法尋找入度為0的節(jié)點將找到的節(jié)點放入隊列中，刪除所有這個節(jié)點引出的邊重復1，直至沒有度為0的節(jié)點如果有節(jié)點不在隊列中，則說明原圖中有環(huán)，否則無環(huán)。1253647求關鍵路徑算法對給定的圖進行拓撲排序按照拓撲排序的結果擴展和標記12345687964511247924Sec6.網絡流與匹配問題網絡最大流最小費用最大流二分圖的最大匹配二分圖的最佳匹配網絡流算法尋找增廣鏈，并根據增廣鏈修改流量。重復這一步驟，直到不再存在增廣鏈。如果需要在此基礎上求最小費用最大流，只需從增廣鏈的選擇上著手。二分圖與匹配算法二分圖的匹配算法又稱匈牙利算法匈牙利算法的中心——可增廣軌不斷尋找可增廣軌，并根據可增廣軌修改匹配最佳匹配只是在選擇可增廣軌時，將匹配的權值作為選擇的條件圖的應用(模型構建)

例題1:(TRAVEL)

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

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

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

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

【例3】01串問題(NOI)

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

設hi為01子串s0..si(1<=I<=n)中1的個數，其中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

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

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

當I>=L1時，根據條件，Si-L1+1…

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

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

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

（2）

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

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

模型2構造有向圖G

我們構造有向圖G，如圖：

其中vi代表s串中的第I位。若k<=vi-vj,則vi向vj引出一條權為k的有向邊<vi,vj>,表明si…sj中至少需增加k個1（k為正值）或減少k個1(k為負值)。由此得出構造有向圖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的最長路徑：我們已構造了一個有n+1個頂點的有向圖G。

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

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

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

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