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

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

第十章：圖

2009年

第十章：圖

?定義和術(shù)語

?圖的表示法

?圖的標(biāo)準(zhǔn)界面

?遍歷及其應(yīng)用

?有向無圈圖，關(guān)鍵路徑

?最小代價(jià)生成樹

?最短路徑

?最大流問題

1

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

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

頂點(diǎn)集合,稱V中的元素為頂點(diǎn)，簡(jiǎn)稱為點(diǎn);稱E為

圖G的弧邊集合,稱E中的元素為弧邊,簡(jiǎn)稱為邊

或者孤.

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

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

中〃eV,。eV.稱u為e的弧尾或者起點(diǎn),

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

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

弧邊e的兩個(gè)頂點(diǎn),用符號(hào)u^v表示.這時(shí)

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

頂點(diǎn).

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

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

中〃eV,0e匕稱為弧邊e的兩個(gè)頂

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

明弧邊的兩個(gè)頂點(diǎn),用符號(hào)uMv表示.這時(shí)稱

頂點(diǎn)u,v互為相鄰頂點(diǎn).

2

無向圖有向圖

3

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

圖,如果沒有兩個(gè)弧邊具有相同的起點(diǎn)和終點(diǎn).否則

就稱圖G為多重圖.

路徑，簡(jiǎn)單路徑，圈（circle）,連通圖，強(qiáng)連通圖：

定義3如果圖G中存在頂點(diǎn)和弧邊交替序列

vev

Oll',,vn_^envn

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

則ei的兩個(gè)頂點(diǎn)為｛3-1,3｝），則稱這個(gè)交替的序

列為從VQ到vn的一個(gè)路徑.稱n為路徑長(zhǎng)度.

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

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

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

路徑,則稱從“到。可達(dá).如果圖中任意兩個(gè)頂點(diǎn)都

可達(dá),則稱其為連通的（如果G為無向圖）或者為強(qiáng)

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

4

單重圖的鄰接矩陣表示法

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

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

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

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

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

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

則奇異值可以是0,00,-00,還可以是NaN.當(dāng)然也

可以用另加標(biāo)志位的方法來表示不存在某個(gè)弧邊.如

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

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

在邊”一。.

5

無向圖有向圖

鄰接矩陣表示法

ABCDABCDE

010000

00010

01000?

00100

00011

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

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

6

有向圖的鄰接表表示法

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

鄰接表表示法存儲(chǔ).在這種表示法中，每個(gè)頂點(diǎn)維護(hù)

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

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

如下：

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

7

有向圖的逆鄰接表表示法

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

表示法下，每個(gè)頂點(diǎn)維護(hù)一個(gè)到達(dá)它的所有弧邊的集

合.這個(gè)集合通常用單鏈表存儲(chǔ).上面的有向圖的逆

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

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

8

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

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

在這種表示法中，每個(gè)弧邊用一個(gè)對(duì)象表示.每個(gè)弧

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

如下：

UulinkweightVvlink

其中小。分別是弧邊的兩個(gè)頂點(diǎn).vEg也為弧邊的

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

指的弧邊對(duì)象也有一個(gè)頂點(diǎn)為u.類似的，vlink為

指針域，指向另一個(gè)以。為頂點(diǎn)的弧邊對(duì)象.上面的

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

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

9

弧邊的界面

structArc

{

//返回有向圖弧邊的起點(diǎn).

inttail(void);

//返回有向圖弧邊的終點(diǎn)

inthead(void);

//返回?zé)o向圖弧邊的一個(gè)頂點(diǎn).

intvl(void);

//返回?zé)o向圖弧邊的與el不同的另一個(gè)頂點(diǎn)

intv2(intel);

〃返回弧邊的兩個(gè)頂點(diǎn)

pair<int,int>ends(void);

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

Weight_type&weight(void);

}；

10

tempiate<typenameVT,typenameWT>

structDigraph(或者Graph){

typedefVTVertex_type;

typedefWTWeight.type;

typedef/*與實(shí)現(xiàn)相關(guān)*/Arc_type;

explicitGraph_type(intn=0);

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

voidset_vtx(intu,VTconstfeinfo);

voidset.arc(intu,intv,WTconstfewt);

voiderase_arc(intu,intv);

intV(void);//返回頂點(diǎn)個(gè)數(shù)

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

VT&v(inti)〃返回對(duì)第i個(gè)頂點(diǎn)的引用

｝；

11

有向圖弧邊迭代子

template<typenameVT,typenameWT>

structDigraph{

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

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

typedef/*實(shí)現(xiàn)相關(guā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/*實(shí)現(xiàn)相關(guān)*/Arc_iterator;

typedef/*實(shí)現(xiàn)相關(guā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

圖的遍歷

用某種次序訪問頂點(diǎn).有兩種方式：

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

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

15

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

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

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

dfs(Digraphfeg,intv)

{

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

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)先遍歷及其應(yīng)用（續(xù)）

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

dfs(Graphfeg,intv)

{

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

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)先遍歷及其應(yīng)用（續(xù)）

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

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

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

頂點(diǎn)u,V可達(dá)（在有向圖中記為Us2,在無向圖中

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

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

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

于以u(píng)為根的子樹中.

18

訪問所有的頂點(diǎn)

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

照尋根次序確定下一個(gè)根.然后再做深度優(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}的

一個(gè)排列.

19

生成森林

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

深度優(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)先遍歷時(shí)走過的弧邊.在上圖中的

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

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

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

為返回邊(2,1).

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

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

下邊.

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

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

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

21

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

其進(jìn)行深度優(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向量是新引入的，用來判別頂點(diǎn)是否已

經(jīng)被訪問過.

上面的程序假設(shè)尋根序?yàn)?,1,...,n-l.

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

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

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

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

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

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

Kosaraju算法：求有向圖的強(qiáng)連通分量是問題

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

先遍歷圖，使得生成森林中的每一棵樹對(duì)應(yīng)于圖中的

一個(gè)強(qiáng)連通分量.

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

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

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

森林中的每一棵樹代表一個(gè)強(qiáng)連通分量.G中兩個(gè)頂

點(diǎn)u.v屬于同一個(gè)強(qiáng)連通分量的充要條件是在

生成森林的同一棵樹中.

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

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

其生成森林中的一棵樹對(duì)應(yīng)于G的一個(gè)強(qiáng)連通分量.

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

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

在G中相互可達(dá)，只需證明任意T頂點(diǎn)u均和T

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

自力至U〃的路徑，所以在G中存在自u(píng)到t的路

25

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

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

個(gè)路徑為u-'t.

R生成森林中的一顆樹

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

將其分為四個(gè)部分.B中的頂點(diǎn)為〃的祖先頂

點(diǎn)，C中的頂點(diǎn)為“的子孫頂點(diǎn).A中的頂點(diǎn)處

在”的左邊，D中頂點(diǎn)處在u的右邊.由于ir⑴>

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

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

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

在自力到珀勺路徑Lt,而且在訪問力時(shí)，這個(gè)路徑

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

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

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

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

徑.

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

一個(gè)強(qiáng)連通分量.不難證明，同一強(qiáng)連通分量中的頂

點(diǎn)必然屬于同一棵樹.證畢.

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

量來表示圖的強(qiáng)連通分量.

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的兩個(gè)

頂點(diǎn)U,v屬于同一個(gè)強(qiáng)連通分量的充要條件.

Tarjan算法

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

程中找出圖的強(qiáng)連通分量.

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

生成森林.

對(duì)于任意的ve匕記

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

S。：G中包含。的強(qiáng)連通分量.

代表頂點(diǎn)：設(shè)s為圖G的一個(gè)強(qiáng)連通分量，稱〃e

S為S的代表頂點(diǎn)，如果

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

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

先訪問到的S中的頂點(diǎn).

26

Tarjan方法基于這樣的觀察：

如果頂點(diǎn)〃不是的代表頂點(diǎn)，則必然存在一個(gè)弧

邊

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?)就是頂點(diǎn)V通過返回邊或者某些跨越

邊所能到達(dá)的最高層.

27

定理9u為Su的代表頂點(diǎn)的充要條件是

pr(u)=Zow(u)

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

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

中的頂點(diǎn).所以u(píng)不是代表頂點(diǎn).

反之，設(shè)〃不是S”的代表頂點(diǎn)，不妨設(shè)Su的代表頂

點(diǎn)為x,由于u,x屬于同一個(gè)強(qiáng)連通分量，所以u(píng)e

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

的所有頂點(diǎn)均屬于S”.在這個(gè)路徑上必然存在一個(gè)

弧邊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。).這說

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

28

low(a)滿足遞歸式：

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

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

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

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

即找到了一個(gè)代表頂點(diǎn)，馬上記錄這個(gè)強(qiáng)連通分量,

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

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

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

值.由于生成森林中一個(gè)子樹中可能包含多個(gè)強(qiáng)連通

分量，

Tarjan方法還使用一個(gè)堆棧來記錄強(qiáng)連通分量.

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;〃供記錄強(qiáng)連通分量使用

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

intsent=-1;〃強(qiáng)連通分量計(jì)數(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)代表頂點(diǎ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)先遍歷

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

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

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

A；0123456

ABCDEFG

0123456

6105324

0120006

無向圖生成森林A,B,D為關(guān)節(jié)點(diǎn)

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

31

定義10(關(guān)節(jié)點(diǎn)(articulationpoints),重連通圖)

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

一個(gè)頂點(diǎn)Vev以及所附屬的弧邊后不再連通,則稱

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

則稱其為重連通圖.

重連通圖的任意兩個(gè)頂點(diǎn)之間至少存在兩條(不同

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

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

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

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

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

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

有兩個(gè)孩子.其他頂點(diǎn)。為關(guān)節(jié)點(diǎn)的充要條件是存

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

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

子通過一個(gè)返回邊能夠到達(dá)的最高層次.定理的證明

32

略去.以上面的圖為例，頂點(diǎn)A為關(guān)節(jié)點(diǎn)，因?yàn)樗?/p>

有兩個(gè)孩子；頂點(diǎn)B為關(guān)節(jié)點(diǎn)，因?yàn)锽的孩子C,

而low(C)>pr(B)；D為關(guān)節(jié)點(diǎn)，因?yàn)橛衅浜⒆禹?/p>

點(diǎn)G,Zow(G)>pr(D).

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

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

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

無向圖時(shí)，有一個(gè)問題需要注意，即每一個(gè)弧邊都被遍

歷兩次.所以，當(dāng)?shù)诙伪闅v同一個(gè)弧邊時(shí)，不能更

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

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

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

中還考慮了自環(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īng)用

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

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

首先訪問。的還沒有被訪問的鄰接點(diǎn)，然后再訪問所

有這些鄰接點(diǎn)中沒有被訪問過的鄰接點(diǎn).以此類推.

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

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

列，則可以訪問到所有的頂點(diǎn)，并且對(duì)應(yīng)得到寬度優(yōu)

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

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

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

有向圖生成森林

34

寬度優(yōu)先遍歷可以用隊(duì)列實(shí)現(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(入度，出度，源點(diǎn)，匯點(diǎn)，s-t圖，有向無圈圖)

設(shè)G為有向圖,而v為其一個(gè)頂點(diǎn).定義v的入度

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

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

點(diǎn)為源點(diǎn)，出度為零的頂點(diǎn)為匯點(diǎn).如果G中只有一

個(gè)源點(diǎn),一個(gè)匯點(diǎn),則稱其為s-t圖.如果G中不存

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

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

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

36

集合上的偏序

定義13稱集合X上的關(guān)系RCXxX為偏序,如

果

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

則（力,z）GR

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

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

序關(guān)系一定是反對(duì)稱的.即1Y%gY力中最多只能

有一個(gè)成立.有向無圈圖可以誘導(dǎo)出頂點(diǎn)集合上的一

個(gè)偏序關(guān)系.

定理14假設(shè)G=（V,E）為有向無圈圖.對(duì)寸叫wG

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

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

37

定義15(拓?fù)湫蛄?，逆拓?fù)湫蛄?有向無圈圖G=

(V,石)拓?fù)渑判蚴侵笇㈨旤c(diǎn)集合V重新排序?yàn)閂=

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

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

圖G的拓?fù)湫蛄?稱｛。九一1,…，。o｝為圖G的逆拓

撲序列.

拓?fù)渑判蚺c調(diào)度問題有關(guān).將任務(wù)看成為圖的頂點(diǎn).

任務(wù)與任務(wù)之間的次序關(guān)系看作為弧邊.例如大學(xué)生

選修的課程，有些課程之間存在次序關(guān)系.假設(shè)一個(gè)學(xué)

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

所有課程排序.下面的算法求DAG的拓?fù)渑判?

while(g不是空?qǐng)D)

1x求

7—g中入度為0的頂點(diǎn)v,

2x將

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

3X相H

71u

輸出的頂點(diǎn)序列就是圖g的拓?fù)渑判?為了實(shí)現(xiàn)上面

的算法，需要計(jì)算圖的頂點(diǎn)的入度.如果圖用逆鄰接表

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

38

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

邊迭代子.對(duì)圖的存儲(chǔ)沒有特別的要求.其復(fù)雜度仍

然為線性的.

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()];

}

下面就是求有向無圈圖的拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn).注意

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

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

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

的麻煩，還需要一個(gè)容器來存放所有入度為零的頂點(diǎn).

它可以是向量，鏈表，堆?；蛘哧?duì)列.下面的實(shí)現(xiàn)選擇

隊(duì)列.

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)，關(guān)鍵路徑

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

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

始，則在圖中添加一個(gè)頂點(diǎn)心即在圖中，頂點(diǎn)。代表

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

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

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

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

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

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

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

需要的最少時(shí)間.從源點(diǎn)到匯點(diǎn)的加權(quán)最長(zhǎng)路徑的長(zhǎng)

度就是完成整個(gè)工程所需的最少時(shí)間.當(dāng)人力物力充

沛，任務(wù)之間可以與任意程度的并行時(shí)，整個(gè)工程的確

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

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

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

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

40

邊使得其只剩下一個(gè)源點(diǎn).同理，也可以在兩個(gè)匯點(diǎn)

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

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

達(dá).任何一個(gè)頂點(diǎn)都可以到達(dá)匯點(diǎn).

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

加權(quán)最長(zhǎng)路徑為關(guān)鍵路徑.

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

點(diǎn)到匯點(diǎn)的路徑都為關(guān)鍵路徑.所以要表示所有的關(guān)

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

示簡(jiǎn)單，可以求出所有在關(guān)鍵路徑上的頂點(diǎn).這個(gè)問

題可以用下面幾個(gè)定義解決.

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

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

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

義源點(diǎn)的最早方生時(shí)間為零.即e（源點(diǎn)）=0.定義

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

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

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

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

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

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

證明留給讀者.式。)可以按照?qǐng)D的拓?fù)湫蛄幸来吻?/p>

出.Z(。)可以按照?qǐng)D的逆拓?fù)湫蛞源饲蟪?

求I⑺示意圖

如上左圖，以。為終點(diǎn)的弧邊有三個(gè).所以源點(diǎn)到。的

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

么經(jīng)過C.而的拓?fù)渑判驊?yīng)該在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的拓?fù)湫蛄?/p>

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

最小代價(jià)生成樹

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

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

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

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

通.

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

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

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

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

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

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

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

小代價(jià)生成樹一定是存在的.

43

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

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

1.T是G的生成樹.

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

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

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

的圖不再連通.

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

圖中就存在圈.

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

44

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

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

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

石1={eeE：e的兩個(gè)頂點(diǎn)均屬于V1}

52—{eEE：e的兩個(gè)頂點(diǎn)均屬于V2}

EQ=E—（石1U石2）

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

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

為圖G的一個(gè)分割.

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

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

劃分為兩個(gè)連通分量從而給出了頂點(diǎn)集合V

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

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

個(gè)弧邊所確定的分割.

定義23（橋邊，非橋邊）假設(shè)圖G=（V