計算機算法與數(shù)據(jù)結(jié)構(gòu)的圖的表示

算法與數(shù)據(jù)結(jié)構(gòu)（C++版）

第十章：圖

2009年

第十章：圖

?定義和術語

?圖的表示法

?圖的標準界面

?遍歷及其應用

?有向無圈圖，關鍵路徑

?最小代價生成樹

?最短路徑

?最大流問題

1

定義1(圖，有向圖，無向圖)圖G由兩個有限的

集合V,E組成.記為G=(K石).稱V為圖G的

頂點集合,稱V中的元素為頂點，簡稱為點;稱E為

圖G的弧邊集合,稱E中的元素為弧邊,簡稱為邊

或者孤.

?稱圖G=(V,石)為有向圖,如果任何一個

弧邊eeE,都包含一個有序?qū)?琳0),其

中〃eV,。eV.稱u為e的弧尾或者起點,

記為tail(e)或者t(e)；稱。為e的弧頭或者終

點，記為head(e)或者h(e).如果需要特別指明

弧邊e的兩個頂點,用符號u^v表示.這時

稱u為(v的)前驅(qū)頂點,稱u為(u的)后繼

頂點.

?稱圖G=(V,B)為無向圖,如果任何一個弧

邊eGE,都包含一個無序?qū)?lt;u,v>,其

中〃eV,0e匕稱為弧邊e的兩個頂

點，分別記為nl(e)和v2(e).如果需要特別指

明弧邊的兩個頂點,用符號uMv表示.這時稱

頂點u,v互為相鄰頂點.

2

無向圖有向圖

3

定義2（單重圖與多重圖）稱圖G=（V,E）為單重

圖,如果沒有兩個弧邊具有相同的起點和終點.否則

就稱圖G為多重圖.

路徑，簡單路徑，圈（circle）,連通圖，強連通圖：

定義3如果圖G中存在頂點和弧邊交替序列

vev

Oll',,vn_^envn

其中q的弧尾為3—1，弧頭為3（如果是無向圖,

則ei的兩個頂點為｛3-1,3｝），則稱這個交替的序

列為從VQ到vn的一個路徑.稱n為路徑長度.

稱｛。0,。九｝為路徑的頂點,稱其他頂點為內(nèi)部頂點.

如果路徑的內(nèi)部頂點互不相同,則稱其為簡單路徑.如

果。0=vn,則稱其為一個圈.如果存在從〃到。的

路徑,則稱從“到?？蛇_.如果圖中任意兩個頂點都

可達,則稱其為連通的（如果G為無向圖）或者為強

連通的（如果G為有向圖）.

4

單重圖的鄰接矩陣表示法

設G=(KE)為單重圖.如果G是有向圖,

則因<|V|2.如果G是無向圖，則\E\<|V|(|V|+

1)/2.可以用一個矩陣A來存儲弧邊集的權(quán)值.令

AUv=弧邊〃一。的權(quán)值

需要一個奇異值來表示不存在弧邊uTV.奇異值

的選擇沒有一定的標準，例如，如果權(quán)值的類型為實數(shù),

則奇異值可以是0,00,-00,還可以是NaN.當然也

可以用另加標志位的方法來表示不存在某個弧邊.如

果弧邊不帶權(quán)值，Auv的值可以為布爾量.Auv=1

表示E中存在邊”一o.AUv—0表示E中不存

在邊”一。.

5

無向圖有向圖

鄰接矩陣表示法

ABCDABCDE

010000

00010

01000?

00100

00011

無向圖鄰接矩陣表示有向圖鄰接矩陣表不

其中圓圈內(nèi)的頂點并不存儲，只是個示意

6

有向圖的鄰接表表示法

有向圖，不管是單重的或者是多重的，都可以用所謂的

鄰接表表示法存儲.在這種表示法中，每個頂點維護

一個所有從它出發(fā)的所有弧邊的集合.這個集合通常

用單鏈表存儲.上面有向圖的鄰接表表示法的示意圖

如下：

有向圖的鄰接表表示法示意圖

7

有向圖的逆鄰接表表示法

有向圖也可以用所謂的逆鄰接表表示法存儲.在這種

表示法下，每個頂點維護一個到達它的所有弧邊的集

合.這個集合通常用單鏈表存儲.上面的有向圖的逆

鄰接表表示法示意圖如下：

有向圖的逆鄰接表表示法示意圖

8

無向圖的多重鄰接表表示法

無向圖的存儲比較麻煩.下面介紹其多重鄰接表表示.

在這種表示法中，每個弧邊用一個對象表示.每個弧

邊對象均處在兩個鏈表之中.這個對象的內(nèi)部示意圖

如下：

UulinkweightVvlink

其中小。分別是弧邊的兩個頂點.vEg也為弧邊的

權(quán)值.ulink為指針域，指向下一個弧邊對象，這個被

指的弧邊對象也有一個頂點為u.類似的，vlink為

指針域，指向另一個以。為頂點的弧邊對象.上面的

無向圖及其多重鄰接表表示示意圖如下.

無向圖的多重鄰接表表示法示意圖（權(quán)值域被忽略）

9

弧邊的界面

structArc

{

//返回有向圖弧邊的起點.

inttail(void);

//返回有向圖弧邊的終點

inthead(void);

//返回無向圖弧邊的一個頂點.

intvl(void);

//返回無向圖弧邊的與el不同的另一個頂點

intv2(intel);

〃返回弧邊的兩個頂點

pair<int,int>ends(void);

〃返回對弧邊權(quán)值的引用

Weight_type&weight(void);

}；

10

tempiate<typenameVT,typenameWT>

structDigraph(或者Graph){

typedefVTVertex_type;

typedefWTWeight.type;

typedef/*與實現(xiàn)相關*/Arc_type;

explicitGraph_type(intn=0);

voidreset(intn);//置為n個頂點。個弧邊的圖

voidset_vtx(intu,VTconstfeinfo);

voidset.arc(intu,intv,WTconstfewt);

voiderase_arc(intu,intv);

intV(void);//返回頂點個數(shù)

intE(void);〃返回弧邊個數(shù)

VT&v(inti)〃返回對第i個頂點的引用

｝；

11

有向圖弧邊迭代子

template<typenameVT,typenameWT>

structDigraph{

typedef/*實現(xiàn)相關*/Arc.iterator;

typedef/*實現(xiàn)相關*/In..arc_iterator;

typedef/*實現(xiàn)相關*/Out._arc_iterator;

Arc_iteratorbegin(void);

Arc_iteratorend(void);

Out_arc_iteratorout_begin(intv);

Out_arc_iteratorout_end(intv);

In_arc_iteratorin_begin(intv);

In_arc_iteratorin_end(intv);

}；

12

無向圖弧邊迭代子

template<typenameVT,typenameWT>

structGraph{

typedef/*實現(xiàn)相關*/Arc_iterator;

typedef/*實現(xiàn)相關*/Adj._arc_iterator;

Arc.iteratorbegin(void);

Arc_iteratorend(void);

Adj_arc_iteratoradj.begin(intu);

Adj_arc_iteratoradj_end(intu);

}；

13

定義4(轉(zhuǎn)置圖)稱有向圖GT=(VT,石丁)為G=

(V,E)的轉(zhuǎn)置圖,如果VT=V并且&GET,u=

tail(eT),v=head(eT)的充要條件是存在弧邊eE

G：v=tail(e))u=head^e).

利用圖的抽象界面求轉(zhuǎn)置圖：

template<classGl,classG2>

voidtranspose(Gl*pg,G2&g2)

{

intn=g2.V();pg->reset(n);

typenameG2::Arc_iteratorfirst=g2.begin();

typenameG2::Arc_iteratorlast=g2.end();

for(;first!=last;++first)

pg->set_arc(first->head(),first->tail(),

first->weight());

while(-n>=0)

pg->set_vtx(n,g2.v(n));

}

程序返回后，圖*pg就是圖g的轉(zhuǎn)置圖.

14

圖的遍歷

用某種次序訪問頂點.有兩種方式：

?深度優(yōu)先遍歷(Depthfirsttraverse)

?與寬度優(yōu)先遍歷(Breadthfirsttraverse).

15

深度優(yōu)先遍歷及其應用

根頂點：出發(fā)的頂點.

以V為根的深度優(yōu)先遍歷(有向圖)：

dfs(Digraphfeg,intv)

{

visit(g,v);//訪問圖g的第v個頂點

Digraph::Out_arc_iteratorfirst=g.out_begin(v);

Digraph::Out_arc_iteratorlast=g.out_end(v);

for(;first!=last;++first)

{

v=first->head();

if(v還沒有被訪問過)

dfs(g,v);

}

}

16

深度優(yōu)先遍歷及其應用（續(xù)）

以V為根的深度優(yōu)先遍歷(無向圖)：

dfs(Graphfeg,intv)

{

visit(g,v);//訪問圖g的第v個頂點

Graph::Adj_arc_iteratorfirst=g.adj_begin(v);

Graph::adj_arc_iteratorlast=g.adj_end(v);

for(;first!=last;++first)

{

v=first->v2(v);

if(v還沒有被訪問過)

dfs(g,v);

}

}

17

深度優(yōu)先遍歷及其應用（續(xù)）

?深度優(yōu)先遍歷頂點的次序不是唯一的.

?從某個頂點出發(fā)并不一定能訪問到所有的頂點.

定理5（深度優(yōu)先遍歷基本定理）設圖G中的兩個

頂點u,V可達（在有向圖中記為Us2,在無向圖中

記為UiV）.在某次深度優(yōu)先遍歷圖G的過程中,

如果先訪問到u,則從u出發(fā)一定可以訪問到3也就

是說，在此次深度優(yōu)先遍歷對應的森林中，。一定處

于以u為根的子樹中.

18

訪問所有的頂點

約定尋根的次序，當從某個頂點出發(fā)的遍歷結(jié)束后，按

照尋根次序確定下一個根.然后再做深度優(yōu)先遍歷.

如果給定尋根次序，深度優(yōu)先遍歷的遞歸程序可以描

述為：

dfs_all(Digraphfeg,vector<int>constferoots)

{

for(inti=0;i<g.V();++i)

{

intv=roots[i];

if(v還沒有被訪問過)

dfs(g,v);

向量roots為尋根次序，必須是{。，…，n―1}的

一個排列.

19

生成森林

給定尋根次序，深度優(yōu)先遍歷圖得到一個森林，稱之為

深度優(yōu)先遍歷的生成森林.

以尋根序0(A),1(B),2(C),3(D),4(E),5(F)深

度優(yōu)先遍歷它所得到的生成森林：

012345

ABCDEF

013254

041253

深度優(yōu)先遍歷有向圖

prl先序編碼

ir：中序編碼

20

生成森林弧邊分類

樹邊：即在深度優(yōu)先遍歷時走過的弧邊.在上圖中的

弧邊(1,3)(1,5)(3,2)均為樹邊.

返回邊：弧邊(u,v)為返回邊，如果u,v同在一棵

樹中，并且v為u的祖先.在上圖中有一個弧邊

為返回邊(2,1).

朝下邊：弧邊(u,v)為朝下邊，如果u,v同在一棵

樹中，并n.v為u的子孫.在上圖中(1,2)為朝

下邊.

跨越邊：不屬于以上三類的弧邊為跨越邊.在上圖中,

(1,0)(5,3)(4,5)(4,3)均為跨越邊.

注意，跨越邊的方向一定是自右向左的.

21

定理6如果有向圖G中存在圈,則以任意尋根序?qū)?/p>

其進行深度優(yōu)先遍歷中必然存在返回邊.

由此得到，只要在深度優(yōu)先遍歷中判別是否存在返回

邊，就可以判別有向圖是否為有向無圈圖.

22

深度優(yōu)先遍歷的非遞歸程序

template<classGraph>

voiddfs_pre_rank(vector<int>*pr,Graph&g,

vector<int>constfeod)

{

pr->clear();intconstn=g.V();pr->resize(n,-1);

typedeftypenameGraph::Out_arc_iteratorItr;

stack<pair<int,Itr>>s;

for(intcount=-1,i=0;i<n;++i){

intconstv=od[i];

if((*pr)[v]>=0)continue;

(*pr)[v]=++count;

s.push(make_pair(v,g.out_begin(v)));

do{

if(s.top().second!=g.out_end(s.top().first)){

intconstw=s.topO.second->head();

if((*pr)[w]>=0)

++s.top().second;//wvisited

else{

(*pr)[w]=++count;

s.push(make_pair(w,g.out_begin(w)));

}

}else{

s.pop();

if(s.empty())break;

++s.top()?second;

}

}while(true);

}//~for

1//~voiddfs_pre_rank(...)

23

深度優(yōu)先遍歷的非遞歸程序(續(xù))

template<classGraph>

voiddfs_inorder(vector<int>*in,Graph&g)

{

in->clear();intconstn=g.V();

vector<bool>visited(n,false);

typedeftypenameGraph::Out_arc_iteratorItr;

stack<pair<int,Itr>>s;

for(intv=0;v<n;++v){

if(visited[v])continue;

visited[v]=true;

s.push(make_pair(v,g.out_begin(v)));

do{

if(s.top().second!=g.out_end(s.top().first)){

intconstw=s.top().second->head();

if(visited[w])++s.top().second;

else{

visited[w]=true;

s.push(make_pair(w,g.out_begin(w)));

}

}else{

in->push_back(s.top().first);

s.pop();

if(s.empty())break;

++s.top()?second;

}

}while(true);

}//~for

1//~voiddfs_inorder(...)

24

其中visited向量是新引入的，用來判別頂點是否已

經(jīng)被訪問過.

上面的程序假設尋根序為0,1,...,n-l.

深度優(yōu)先遍歷復雜度：

注意到深度優(yōu)先遍歷是，訪問到所有的頂點和弧邊.

每次訪問只需固定的工作量，所有深度優(yōu)先遍歷的時

間復雜度為O(V|+|E|).其空間復雜度正比于程序

中堆棧的大小.在最不利的情況下，堆棧中元素個數(shù)

可以達到|V|.所以其空間復雜度為。(|丁|).

Kosaraju算法：求有向圖的強連通分量是問題

R.Kosaraju方法：用一種特殊的尋根次序去深度優(yōu)

先遍歷圖，使得生成森林中的每一棵樹對應于圖中的

一個強連通分量.

定理7(S.Kosaraju)假設圖G為有向圖,R

為G的轉(zhuǎn)置圖.如果用R的某次深度優(yōu)先遍歷的中

序序列的倒序作為尋根次序深度優(yōu)先遍歷G,則生成

森林中的每一棵樹代表一個強連通分量.G中兩個頂

點u.v屬于同一個強連通分量的充要條件是在

生成森林的同一棵樹中.

證明：由于G與R具有相同的強連通分量，下面證明

用G的中序序列的倒序作為尋根序深度優(yōu)先遍歷R,

其生成森林中的一棵樹對應于G的一個強連通分量.

設T為R生成森林中的一棵樹，u.v為T中的兩

個頂點.t為T的根結(jié)點.欲證明T中兩頂點u.v

在G中相互可達，只需證明任意T頂點u均和T

的根結(jié)點t在G中相互可達即可.由于在R中存在

自力至U〃的路徑，所以在G中存在自u到t的路

25

徑.根據(jù)遍歷R是的尋根序可知：這個路徑上的所有

頂點(除t外)的中序編碼ir值均小于沂?).記這

個路徑為u-'t.

R生成森林中的一顆樹

現(xiàn)在考慮G的生成森林.按照頂點〃所處的位置,

將其分為四個部分.B中的頂點為〃的祖先頂

點，C中的頂點為“的子孫頂點.A中的頂點處

在”的左邊，D中頂點處在u的右邊.由于ir⑴>

ir(u),所以在G的生成森林中，頂點t只能處在B,

D中.如果t處在區(qū)域D中，則有pr(t)>pr(u).

記力為路徑u一t上先序編碼最小的頂點.這樣存

在自力到珀勺路徑Lt,而且在訪問力時，這個路徑

上的所有頂點均沒有被訪問到.根據(jù)深度優(yōu)先遍歷基

本定理，tETx.所以ir⑴<ir⑺.矛盾.所以頂

點力只能處在區(qū)域B中.也就是說在G的生成森林中,

t為〃的祖先頂點.即在G中必然存在自t到u的路

徑.

上面證明了R生成森林中一棵樹中的頂點必然屬于同

一個強連通分量.不難證明，同一強連通分量中的頂

點必然屬于同一棵樹.證畢.

下面給出R.Kosaraju方法的實現(xiàn).用一個整數(shù)向

量來表示圖的強連通分量.

template<classGraph>

voiddfs_sc_kosaraju(vector<int>*sc,Graphfeg)

{

Graphr;

inverse(&r,g);〃：r為g的轉(zhuǎn)置圖

vector<int>in;

dfs_inorder(&in,r);〃in為遍歷r的中序序列

std::reverse(in.begin(),in.end());

dfs_tree(sc,g,in);

}

程序返回后，Osc)[u]==(*sc)[v]為圖g的兩個

頂點U,v屬于同一個強連通分量的充要條件.

Tarjan算法

用任意的尋根序去深度優(yōu)先遍歷圖，在一次遍歷的過

程中找出圖的強連通分量.

G=(V,E)為有向圖，F(xiàn)為某次深度優(yōu)先遍歷G的

生成森林.

對于任意的ve匕記

Tv\尸中以。為根的子樹;

S。：G中包含。的強連通分量.

代表頂點：設s為圖G的一個強連通分量，稱〃e

S為S的代表頂點，如果

pr(u)=min{pr(v):vES}

顯然，S的代表頂點就是在深度優(yōu)先遍歷時，最

先訪問到的S中的頂點.

26

Tarjan方法基于這樣的觀察：

如果頂點〃不是的代表頂點，則必然存在一個弧

邊

e：tail(e)GTu,v=head(e)6Su

使得

pr(i>)<pr(u)

定義8(low(u))令集合

Au={yeV：BeeE：x=eTu,y=h(e)eSu}

約定空集合的最小值為無窮大.定義

v

low(u)=min{min{”(0):eAu},pr(u)}

顯然，low?)就是頂點V通過返回邊或者某些跨越

邊所能到達的最高層.

27

定理9u為Su的代表頂點的充要條件是

pr(u)=Zow(u)

證明：如果low(u)<pr(u),即存在gGS”使

得p/(n)<顯然u不是第一個被訪問到的Su

中的頂點.所以u不是代表頂點.

反之，設〃不是S”的代表頂點，不妨設Su的代表頂

點為x,由于u,x屬于同一個強連通分量，所以ue

Tx,并且必然存在從u到I的路徑.在這個路徑上

的所有頂點均屬于S”.在這個路徑上必然存在一個

弧邊eEE：t=tail{e)GTu,h=head^e)任Tu.

下面證明pr(h)<pr^u),這樣low(u)<pr(h)<

p『(u).根據(jù)深度優(yōu)先基本定理，”(h)<”?).如

果pr(h)>pr(u),則pr(u)<pr(h)<pr。).這說

明在訪問九時還處在乙中，即九en.矛盾.證畢.

28

low(a)滿足遞歸式：

low(u)=min{low(v):veTu}

即low(u)與虱中的所有頂點有關，所以必須在訪問

完1Z的子樹后才能得到low(u).

Tarjan方法計算/ow(iz),一1旦發(fā)現(xiàn)low(u)=

即找到了一個代表頂點，馬上記錄這個強連通分量,

Tarjan算法用一個數(shù)組來存儲low(u),這個數(shù)組

的初始值被置為P『(u).隨著遍歷的進行不斷更

新Zow(iz).當訪問完乙時，就得到了low⑺的

值.由于生成森林中一個子樹中可能包含多個強連通

分量，

Tarjan方法還使用一個堆棧來記錄強連通分量.

29

template<classGraph>

voiddfs_sc_tarjan(vector<int>*sc,Graph&g)

{

intconstn=g.V();

sc->clear();

sc->resize(n);

vector<int>low(n,-1);

vector<int>pr(n,-1);

typedeftypenameGraph::Out_arc_iteratorItr;

stack<pair<int,Itr>>s;〃模擬遞歸調(diào)用使用棧

stack<int>scs;〃供記錄強連通分量使用

intpent=-1;〃先序編碼計數(shù)器

intsent=-1;〃強連通分量計數(shù)器

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

{

if(pr[i]>=0)

continue;

low[i]=pr[i]=++pcnt;

s.push(make_pair(i,g.out_begin(i)));

scs.push(i);

do{

intu=s.topO.first;

intv;

if(s.topO.second!=g.out_end(u))

{

if(pr[v=s.topO.second->head()]<0)

{

low[v]=pr[v]=++pcnt;

s.push(make_pair(v,g.out_begin(v)));

scs.push(v);

30

}

else

{

low[u]=min(low[u],low[v]);

++s.top().second;

}

}

else

{//u的子樹已經(jīng)被訪問完

if(pr[u]==low[u])

{〃發(fā)現(xiàn)代表頂點

++scnt;

do{

v=scs.top()；

scs.pop();

(*sc)[v]=sent;

low[v]=numeric_limits<int>::max();

}while(u!=v);

}

s.pop();

if(s.empty())

break;

++s.top().second;

low[s.top().first]

=minClow[s.top().first],low[u]);

}

}while(true);

}//~for

1//~voiddfs_sc_tarjan(...)

無向圖的深度優(yōu)先遍歷

對無向圖的深度優(yōu)先遍歷也有對應的生成森林.

圖只包含樹邊和返回邊，不存在朝下邊和跨越邊.

生成森林中的每一棵樹代表原圖中的一個連通分量.

A；0123456

ABCDEFG

0123456

6105324

0120006

無向圖生成森林A,B,D為關節(jié)點

其中弧邊(巳A)(F,A)為返回邊，其他為樹邊.

31

定義10(關節(jié)點(articulationpoints),重連通圖)

假設無向圖G=(V,E)為連通的.如果刪除其中的

一個頂點Vev以及所附屬的弧邊后不再連通,則稱

頂點。為圖G的關節(jié)點.如果圖G不存在關節(jié)點,

則稱其為重連通圖.

重連通圖的任意兩個頂點之間至少存在兩條(不同

的)路徑.深度優(yōu)先遍歷可以求出圖的關節(jié)點.

定理11假設連通無向圖G=(匕石)某次深度優(yōu)

先遍歷的生成森林為F.對于veVr定X

lowQu)=min<min{low^x):力是u孩子},?

Imin{pr(oj):(。,力)是返回邊))

則F的根頂點v為G的關節(jié)的的充要條件是。至少

有兩個孩子.其他頂點。為關節(jié)點的充要條件是存

在。的一個孩子頂點w使得low(w)>p/(u).

顯然low^就是。自身通過一個返回邊，或者其孩

子通過一個返回邊能夠到達的最高層次.定理的證明

32

略去.以上面的圖為例，頂點A為關節(jié)點，因為它

有兩個孩子；頂點B為關節(jié)點，因為B的孩子C,

而low(C)>pr(B)；D為關節(jié)點，因為有其孩子頂

點G,Zow(G)>pr(D).

下面給出求連通圖的關節(jié)點的實現(xiàn).程序深度優(yōu)先遍

歷圖，在遍歷的過程中計算low數(shù)組，并記錄根結(jié)點

的孩子個數(shù).由此得出圖的關節(jié)點.在深度優(yōu)先遍歷

無向圖時，有一個問題需要注意，即每一個弧邊都被遍

歷兩次.所以，當?shù)诙伪闅v同一個弧邊時，不能更

新low數(shù)組的值.為了判定返回邊是否被第二次訪問,

需要引入生成森林的中序編碼汨數(shù)組.對于樹邊，可

以利用堆棧上的信息判定其是否為第二次訪問.程序

中還考慮了自環(huán)邊和多重邊的情況.

template<classGraph>

booldfs_arti_pts(vector<bool>*a,Graph&g)

{

intconstn=g.V();

a->clear();

a->resize(n,false);

vector<int>pr(n,-1);

vector<int>ir(n,-1);

vector<int>low(n,numeric_limits<int>::max());

typedeftypenameGraph::Adj_arc_iteratorItr;

stack<pair<int,Itr>>s;

intpent=-1;

intient=-1;

intrts=0;

low[0]=pr[0]=++pcnt;

s.push(make_pair(0,g.adj.begin(0)));

for(;;)

{

while(s.top()?second!=g.adj_end(s.top().first))

{

intconstv=s.top().first;

intconstw=s.top().second->v2(v);

if(pr[w]<0)

{〃樹邊

if(v==0)++rts;

low[w]=pr[w]=++pcnt;

s.push(make_pair(w,g.adj_begin(w)));

}

else

33

if((ir[w]<0)&&(v!=w)){

pair<int,Itr>consttemp=s.top()；

s.pop();//返回邊的第一次訪問

if(!s.empty()&&(w!=s.top().second->v2(v)))

low[v]=min(low[v],pr[w]);

s.push(temp);

}

++s.top().second;

}

1//~while

intconstchild=s.top().first;

ir[child]=++icnt;

s.pop();

if(s.empty())

break;

low[s.top().first]=

min(low[child],low[s.top().first]);

if(low[child]>=pr[s.top().first])

(*a)[s.topO.first]=true;

}//~for

(*a)[0]=rts>1;

for(rts=n;一一rts>=0;)

if(pr[rts]<0)

returnfalse;

returntrue;

1//~booldfs_arti_pts(...)

寬度優(yōu)先遍歷及其應用

不論是有向圖還是無向圖，都可以做所謂的寬度優(yōu)先

遍歷.從根頂點。出發(fā)寬度優(yōu)先遍歷可以描述為,

首先訪問。的還沒有被訪問的鄰接點，然后再訪問所

有這些鄰接點中沒有被訪問過的鄰接點.以此類推.

從。出發(fā)寬度優(yōu)先遍歷只能訪問到從?？蛇_的頂點.

并不一定能夠訪問到所有的頂點.如果給定尋根序

列，則可以訪問到所有的頂點，并且對應得到寬度優(yōu)

先遍歷的生成森林.下圖是一個有向圖及其以尋根序

0(A),1(B),2(C),3(D),4(E),5(F)寬度度優(yōu)先

遍歷它所得到的生成森林.

有向圖生成森林

34

寬度優(yōu)先遍歷可以用隊列實現(xiàn).

template<typenameGraph>

voidbfs(Graphfeg,vector<int>const&roots)

{

intconstn=g.V();

vector<bool>visited(n,false);

queue<int>q;

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

{

if(visited[roots[i]])

continue;

q.push(roots[i]);

do{

intconstv=q.front();

q-pop();

visited[v]=true;

visit(g,v);

typedeftypenameGraph::Out_arc_iteratorItr;

Itrfirst=g.out_begin(v);

Itrlast=g.out_end(v);

for(;first!=last;++first)

intconstw=first->head();

if(?visited[w])

q.push(w);

}

}while(?q.empty());

}

}

35

有向無圈圖

定義12(入度，出度，源點，匯點，s-t圖，有向無圈圖)

設G為有向圖,而v為其一個頂點.定義v的入度

為G中以v為弧尾的弧邊的個數(shù).定義v的出度

為G中以v為弧頭的弧邊的個數(shù).稱入度為零的頂

點為源點，出度為零的頂點為匯點.如果G中只有一

個源點,一個匯點,則稱其為s-t圖.如果G中不存

在圈,則稱其為有向無圈圖(DAG).

有向無圈圖至少有一個源點和一個匯點.諸如任務調(diào)

度等問題都可以歸結(jié)為有向無圈圖問題.

36

集合上的偏序

定義13稱集合X上的關系RCXxX為偏序,如

果

1.R是傳遞的.即如果（力,g）eR,（g,z）eR,

則（力,z）GR

2.R為反自反的.即eX,（力,力）0A

偏序關系通常用Y表示.（/,g）eR記為力Yg.偏

序關系一定是反對稱的.即1Y%gY力中最多只能

有一個成立.有向無圈圖可以誘導出頂點集合上的一

個偏序關系.

定理14假設G=（V,E）為有向無圈圖.對寸叫wG

『，定X。Y僅的充要條件是在G中存在自v到w的

路徑.則Y為V上的偏序.

37

定義15(拓撲序列，逆拓撲序列)有向無圈圖G=

(V,石)拓撲排序是指將頂點集合V重新排序為V=

｛%),???,。九—1｝，使得對Vee石，3=tail(e),Vj=

head(e),有i<j.這時稱序列｛比),…，。九為

圖G的拓撲序列.稱｛。九一1,…，。o｝為圖G的逆拓

撲序列.

拓撲排序與調(diào)度問題有關.將任務看成為圖的頂點.

任務與任務之間的次序關系看作為弧邊.例如大學生

選修的課程，有些課程之間存在次序關系.假設一個學

期只能選項一門課程.要選修完所有課程，則必需將

所有課程排序.下面的算法求DAG的拓撲排序.

while(g不是空圖)

1x求

7—g中入度為0的頂點v,

2x將

7—V以及從v出發(fā)的弧邊從g中刪除;

3X相H

71u

輸出的頂點序列就是圖g的拓撲排序.為了實現(xiàn)上面

的算法，需要計算圖的頂點的入度.如果圖用逆鄰接表

表小,則g.in_begin(v)與g.in_end(v))這兩個迭代子

38

之間的距離就是頂點V的入度.下面的程序只利用弧

邊迭代子.對圖的存儲沒有特別的要求.其復雜度仍

然為線性的.

template<classDAG>

voidin_degree(vector<int>*id,DAG&g)

{

id->clear();

id->resize(g.V(),0);

typedeftypenameDAG::Arc_iteratorItr;

Itrfirst=g.beginO;

Itrlast=g.end();

for(;first!=last;++first)

++(*id)[first->head()];

}

下面就是求有向無圈圖的拓撲排序算法的實現(xiàn).注意

算法并不是向上面所描述的那樣去刪除圖中的頂點和

弧邊，而是用一個數(shù)組來記錄頂點的入度.刪去頂點

和弧邊用更新頂點的入度數(shù)組來模擬.為了避免查找

的麻煩，還需要一個容器來存放所有入度為零的頂點.

它可以是向量，鏈表，堆棧或者隊列.下面的實現(xiàn)選擇

隊列.

template<classDAO

booltopologic_sort(vector<int>*ts,DAG&g)

{

typedeftypenameDAG::Out_arc_iteratorItr;

vector<int>id;

in_degree(&id,g);

queue<int>zeroes;

for(intu=id.size();-u>=0;)

if(id[u]==0)

zeroes.push(u);

ts->clear();

while(!zeroes.empty())

{

intv=zeroes.front();

zeroes.pop();

ts->push_back(v);

Itrfirst=g.out_begin(v);

Itrlast=g.out_end(v);

for(;first!=last;++first)

{

v=first->head();

if(-id[v]==0)

zeroes.push(v);

}

}

returnid.size()==ts->size();

}

39

AOE網(wǎng)，關鍵路徑

在任務調(diào)度問題中，還可以將任務看做為圖的弧邊.

如果任務s4完成以后，任務九，?,,，”才能開

始，則在圖中添加一個頂點心即在圖中，頂點。代表

任務si,...,sk已經(jīng)完成，任務九，?…，”可以開始的

狀態(tài).每個弧邊可以帶有權(quán)值，權(quán)值的含義可以是完

成該任務所需的時間.稱這種以弧邊代表任務的帶權(quán)

的圖為AOE(AactivityOnEdge)網(wǎng).容易證明,

AOE網(wǎng)一定是有向無圈圖.

在AOE網(wǎng)中，頂點之間的加權(quán)最長路徑的長度有著

明顯的實際意義.它是從一個狀態(tài)到達另一個狀態(tài)所

需要的最少時間.從源點到匯點的加權(quán)最長路徑的長

度就是完成整個工程所需的最少時間.當人力物力充

沛，任務之間可以與任意程度的并行時，整個工程的確

可以在最少日寸間內(nèi)完成.

在考慮AOE網(wǎng)中的最長路徑時，可以假設圖中只有

一個源點，一個匯點.稱這樣的圖為s-t網(wǎng).如果原

圖中有多個源點，可以在源點之間添加權(quán)值為零的弧

40

邊使得其只剩下一個源點.同理，也可以在兩個匯點

之間添加權(quán)值為零的弧邊使得其只剩下一個匯點.以

下只考慮s-t圖.這樣的圖，從源點到其他頂點均可

達.任何一個頂點都可以到達匯點.

定義16（關鍵路徑）稱AOE網(wǎng)中從源點到匯點的

加權(quán)最長路徑為關鍵路徑.

注意關鍵路徑可以有多條.極端的情況下，所有從源

點到匯點的路徑都為關鍵路徑.所以要表示所有的關

鍵路徑，只能還是一個有向無圈圖.為了使得問題表

示簡單，可以求出所有在關鍵路徑上的頂點.這個問

題可以用下面幾個定義解決.

定義17（狀態(tài)的最早發(fā)生時間，最遲發(fā)生時間，工期）

設。為AOE網(wǎng)中的頂點,定義v的最早發(fā)生時間為

從源點到v的最長加權(quán)路徑的長度.記之為e（v）.定

義源點的最早方生時間為零.即e（源點）=0.定義

工期為源點到匯點的加權(quán)最長路徑長度.即工期=

e（匯點）.定義匯點的最遲發(fā)生時間為工期.即1（匯點）=

e(匯點).定義其他頂點v的最遲發(fā)生時間為Z(o)=

工期-d到匯點的最長加權(quán)路徑長度.

定理18AOE網(wǎng)中頂點v處在某個關鍵路徑上的

充要條件是e(v)=1(").

證明留給讀者.式。)可以按照圖的拓撲序列依次求

出.Z(。)可以按照圖的逆拓撲序以此求出.

求I⑺示意圖

如上左圖，以。為終點的弧邊有三個.所以源點到。的

路徑只能有三種情況，要么經(jīng)過Q,要么經(jīng)過b,要

么經(jīng)過C.而的拓撲排序應該在V之前.如

果e(a),e(b),e(c)已經(jīng)得到,則

e(a)+w(a,0),

e(v)=maxe(b)+w9,v)、

e(c)+w(c,o)

template<classDAO

voidcritical_path(vector<bool>*cp,DAG&g)

vector<int>to;

topologic_sort(&to,g);//to:g的拓撲序列

intconstn=g.V();

typedeftypenameDAG::Weight_typeWT;

vector<WT>e(n,Weight_traits<WT>::min());

e[0]=Weight_traits<WT>::zero();

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

typedeftypenameDAG::In_arc_iteratorItr;

Itrfirst=g.in_begin(to[i]);

Itrlast=g.in_end(to[i]);

for(;first!=last;++first)

e[to[i]]=

max(e[to[i]],e[first->tail()]+first->weight());

}

vector<WT>1(n,Weight_traits<WT>::max());

1[n-1]=e[n-1];

for(inti=n-1;-i>=0;){

typedeftypenameDAG::Out_arc_iteratorItr;

Itrfirst=g.out_begin(to[i]);

Itrlast=g.out_end(to[i]);

for(;first!=last;++first)

=

min(l[to[i]],1[first->head()]-first->weight());

}

cp->resize(n);

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

(*cp)[i]=e[i]==1[i];

}

41

最小代價生成樹

定義19(生成樹，最小代價生成樹)假設圖G=(V,E)

為連通圖.稱圖T=(V,A)為G的生成樹,如

果T為G的極小連通子圖.即AUE,T是連通

的并且對任何A的子集H,圖T=(V,H)不再連

通.

假設圖G的每一個弧邊均帶有權(quán)值.記W(G)=

￡蚱石伙(6).其中?(e)為弧邊e的權(quán)值.稱G的某

個生成樹T為G的最小代價生成樹,如果W(T)=

min{W(S):S為G的生成樹}.如果T為G的最

小代價生成樹,記MST(G)=印(T).

所謂最小代價生成樹就是指權(quán)值之和最小的那個生成

樹.連通圖的生成樹一定是存在并且有限的.所以最

小代價生成樹一定是存在的.

43

定理20假設圖T=(V,A)為G=(V,E)的子圖,

則以下結(jié)論等價:

1.T是G的生成樹.

2T是連通的并且兇=凹―L

3.T是連通的并且T中沒有圈.

4.T是連通的并且刪除T中的任意一個弧邊,剩余

的圖不再連通.

5T是連通的,并且給T中添加一個弧邊,生成的

圖中就存在圈.

6.|川=|V|-1并且T中沒有圈.

44

定義21（分割）假設將V劃分為兩個互不相交的集

合之并:V=匕□生，相應的將弧邊集合劃分為三

個互不相交的集合E=Eo□Ei□石2?其中

石1={eeE：e的兩個頂點均屬于V1}

52—{eEE：e的兩個頂點均屬于V2}

EQ=E—（石1U石2）

稱EQ中的弧邊為跨越邊.稱

Gi=（%,Ei）,G2=（正,石2）

為圖G的一個分割.

定義22（生成樹弧邊確定的分割）假設T為G=

（V,E）的生成樹,則刪除T中的任意一個弧邊,將T

劃分為兩個連通分量從而給出了頂點集合V

的一個劃分,V=匕□匕.其中Vi,V2分別為屬

于T1,T2的頂點.把這樣的分割稱之為由生成樹的一

個弧邊所確定的分割.

定義23（橋邊，非橋邊）假設圖G=（V