计算机算法基础 第2版 课件 第8章 图的周游算法

1第8

章

图的周游算法什么是图的周游

2图的表示

3广度优先搜索及应用

5

无向图的二着色问题

124. 深度优先搜索及应用

17拓扑排序

32无回路有向图中最长路径问题及应用

36有向图的强连通分支的分解

43无向图的双连通分支的分解

522许多应用问题用图来描述，因而产生许多与图有关的算法问题。例如图的着色问题，最短路径问题等。对一个图的每个点及每条边按某种顺序进行逐一访冋的算法称为图的周游算法，是最重要的图的算法。图的周游本身不是目的，而是为解决应用问题提供快速有效的访问框架和顺序。在解决具体问题时，往往需要在周游时加入其他的操作从而得到结果。介绍两个周游算法，它们有线性复杂度，所以是最优的。如能用周游算法直接解决应用问题，算法往往是最优的。1.什么是图的周游算法3邻接表示例153241432565541533212412123544466642212354552.图的表示

无向图

有向图4

邻接矩阵示例1532414325612354101010101010101110100101112345123540101100000010000110100000001000000006123456

无向图

有向图5广度优先搜索(BFS)策略初始，取图中一点s开始，访问s。第1步，逐一访问Adj(s)中所有点，v1，v2，…，vk。第2步，依次访问Adj(v1)，Adj(v2)，…，Adj(vk)中的点。访问Adj(u)中顶点v时，如果v还未被访问过，称首次访问，否则是后续访问。首次访问建立父子关系，

(v)=u。第3步，逐一访问前一步被首次访问的点的前向邻居。重复第3步直到某一步没有首次被访问的点为止。显然，第k步中被首次访问的点到点s的(最短)距离是k条边。如果从s开始的一轮BFS不能访问到图中所有点，则取一个未访问过的点，再做一轮BFS，直到所有点都被访问到。3.广度优先搜索及应用6BFS算法简介用白、灰、黑三种颜色表示每个顶点被访问的三个阶段：即还未被访问，刚被访问，和它的所有前向邻居都已被访问。每个顶点v附两个变量，即s到v的(不加权)距离d(v)，和v的父亲指针

(v)。初始置d(v)=

，

(v)

=nil，但置d(s)

=0。用队列来顺序存储被首次访问的点。一开始是点s。每次循环取出队首u，并逐个访问Adj(u)中每个点v。如果v是白色，则是首次访问，置

(v)

=u，d(v)=d(u)+1，把v变灰色后入队。Adj(u)中点全部访问后，u变黑色。BFS本身在后续访问时不做任何操作，但解具体问题时，可能需要一些操作。7BFS(G(V,E),s)foreachvertexu

V–{s} //初始化开始

color(u)

White；d(u)

；(u)

nilendforcolor(s)

Gray；d(s)

0；Q

//先把队列清空Enqueue(Q,s) //将s进队，初始化完成while

Q

u

Dequeue(Q) //取出队列首项 foreachv

Adj(u)

if

color(v)

=White

then

color(v)

Gray

d(v)

d(u)

+1

(v)

u Enqueue(Q,v)

endif

endfor

color(u)

Black

endwhileEnd8

9例：101112无向图的二着色问题(BSF应用举例)：

把一个无向图着色就是给每个顶点一个颜色(一个号码)使得每两个相邻点的颜色不同。一个图如果可以用k个颜色来着色，则称它可k-着色。当k

3时，

判断一个图能否k-着色是NP-完全问题。2-着色问题有多项式算法。BFS可解。13图2-着色的算法简介假设被着色的图G是个连通图。用红(Red)、蓝(Blue)两色为图着色。原BFS中灰色不用，红、蓝色表示顶点已不是白色了。原BFS中黑色不用，红点或蓝点出队后不可能再入队。距离d(u)与本题无关，省略。起始点s的颜色着为红色，即color(s)=Red.Adj(u)中点v被首次访问时，着色为与父亲u相反颜色，用not(color(u))表示。Adj(u)中点v被后续访问时，检查是否color(u)

=color(v)。如相同，停止着色并报告不可二着色，否则继续。14Two-Color(G(V,E),s)1 foreachu

V2 color(u)

White //每个顶点初始化为白色3 endfor4 Q

5 color(s)

Red6 Enqueue(Q,s) //初始化完成，s是队列中唯一元素，红色7 whileQ

8

u

Dequeue(Q)9 foreachv

Adj(u)10 ifcolor(v)

=White //v是首次访问11 then

color(v)

not(color(u))

12

Enqueue(Q,v)13 else if

color(v)

=color(u)//后续访问v14

thenreturn(not2-colorable)15 endif

16 endif17 endfor18 endwhile19 return(2-colorable)20 End15二着色算法正确性证明：两种情形：算法顺利完成。

这种请况下，每个点必定被访问到并着色。取任一条边(u,v)。考虑算法访问Adj(u)中点v时情形。如果点v是白色，那么，v是首次访问。算法第11行保证必有color(u)

color(v)。如果点v不是白色，那么，

这次访问是后续访问。算法必定要检查color(v)。因为算法未中断，必有color(u)

color(v)。所以，

如果算法顺利完成，图必定被正确地二着色。(2) 算法中断运行。这种情况下，必有边(u,v)被检测出

color(u)=

color(v)。

(接下页)16二着色算法正确性证明

(继续)如果color(u)=

color(v)=Red，那么一条从根s到u的路径上点的颜色是红蓝相间，从而有偶数条边。同理，也有一条从s到v的有偶数条边的路径。所以，这两条路径加上边(u,v)形成一个奇回路从而图不可二着色。如果color(u)=

color(v)=Blue，那么一条从s到u的路径有奇数条边。同理，也有一条从s到v的有奇数条边的路径。所以，这两条路径加上边(u,v)也形成一个奇回路。所以图G也不可2-着色。这就证明了，如果算法中断运行，那么图不可能2-着色。。算法的正确性得证。17深度优先搜索(DFS)策略：与BFS同，初始时，取一个尚未访问过的点u

，访问点u。然后：逐一访问Adj(u)中点，直到发现一个还未访问过的邻居v。这是首次访问，建立父子关系，置

(v)=u。置

(v)=u后，暂时不顾u的余下邻居，而从v出发去访问v的邻居Adj(v)，并遵循一样的策略：顺序访问Adj(v)中点直到发现一个还未访问过的邻居。这是一个递归的过程。

如果v没有邻居，Adj(v)=

，或者所有邻居都已在先前被访问过了，那么DFS又回到u，称为回溯(backup)。从v回溯到u后，DFS再继续访问Adj(u)中余下邻居，直到找到下一个尚未访问的点，然后重复第1,2步。当Adj(u)中所有点都被访问完，一轮DFS完成。4.深度优先搜索及应用18DFS算法简介与BFS同，用白、灰、黑三色表示顶点被访问的三阶段。访问Adj(u)中v时，如v是白色，为首次访问，置

(v)=u，v由白变灰。否则为后续访问，DFS本身无操作，解应用问题时会有操作。每个点u有两个事件点，一个是首次访问u时，点u由白变灰，称为发现时刻d(u)。另一个是Adj(u)中点全部访问完毕，u由灰变黑，称为完成时刻f(u)。

d(u)和f(u)称为时间戳。有n个顶点的图有2n个事件点，按发生顺序从1到2n编号。既使图需要多轮DFS，这编号是统一并连续的。这样编号有妙用。分为主程序和子程序。主程序DFS(G)取图中一个未访问过的点u(白色)，并调用子程序DFS(G,u)进行新一轮DFS搜索。当图中所有点都被访问，算法结束。19主程序伪码DFS(G(V,E))for

eachu

V

color(u)

White //初始化每个点为白色

(u)

nilendfortime

0 //时间戳初始化为0foreachvertexu

V

if

color(u)

=White //如果白点，则调用子程序

then

DFS-Visit(u)

endifendforEnd20递归形式的DFS子程序DFS-Visit(s)color(s)

Gray //顶点s

由白变灰time

time+1 d(s)

time //顶点s的发现时刻foreachv

Adj(s)

ifcolor(v)

=White

then

(v)

s

DFS-Visit(v) //递归访问v

endifendforcolor(s)

Black //对s的访问完成

f(s)

time

time+1 //顶点s的完成时刻

End21定理8.1(区间套定理)

点u的访问区间[d(u),f(u)]包含v的访问区间[d(v),f(v)]当且仅当u是v的祖先。点u和v没有直系关系，当且仅当它们的访问区间不相交。证明：由伪码知，如果v是u的儿子，则有d(u)<d(v)<f(v)<f(u)。

所以有[d(v),f(v)]

[d(u),f(u)]。显然，如果

u是v的祖先，那么也有[d(v),f(v)]

[d(u),f(u)]。反之，如果[d(v),f(v)]

[d(u),f(u)]，则有

d(u)<d(v)<f(v)<f(u)。说明访问u的过程中访问了v，那么v必定是u的后代。如u和v没有直系关系，设d(u)<d(v)，因无直系关系，u完成前，不会访问v。故有

f(u)<d(v)，它们的区间必不相交。反之，如区间不相交，设

f(u)<d(v)，那么点v不可能成为u的后代。

22定理8.2

(白路径定理)

顶点v成为u的后代，当且仅当在时刻d(u)，图中存在一条从u到v的由白色顶点构成的路径。证明：如果v是u的后代，那么有路径u，u1，u2，…，,uk，v。其中uk=v。路径上，u是u1的父亲，u1是u2的父亲，…，uk-1

是uk的父亲。由定理8.1，有d(u)<d(u1)<d(u2)<…<d(uk)<d(v)。这说明在时刻d(u)时，路径上所有点还没被访问，因而是白色的。反之，如果在d(u)时，有一条从u到v的白路径

u，u1，u2，…，uk，其中uk=v。用归纳法证明，所有点都必然成为u的后代。(接下页)23定理8.2

(证明继续)归纳基础：

因为在d(u)时，u1是白色的，而当u完成时，u不可以有未访问的邻居，所以u1必然是u的后代。归纳步骤：

假设u1，u2，…，up(1

p

k-1)都是u的后代，我们证明顶点up+1也必须是u的后代。

为了用反证法，假设up+1不是u的后代。由定理8.1，顶点up+1的访问区间在u的访问区间之后。所以，在up完成时刻，顶点up+1必定仍然是白色的点。这表明，在up完成时，它还有个白色的邻居未访问，这与算法矛盾。因此，顶点up+1也必须是u的后代，归纳成功。

24非递归子程序DFS-Visit(s)简介用堆栈保存灰色顶点，s先被访问、入栈并改灰色。然后每一步都是访问栈顶S中顶点u的下一个邻居直到S=

。设栈顶是u，DFS访问Adj(u)中的下一个顶点。有3种情况：(1) Adj(u)中的所有顶点都己访问过了。说明DFS-Visit(u)完成，弹出u，u变黑色并赋以f(u)。(2) Adj(u)中的下一个顶点v是白色的。v被首次访问，压入堆栈、变灰色并赋以d(v)，置

(v)=u。可见，堆栈中仼何二个相邻元素构成父子关系。所以，堆栈中从底到顶的元素于对应的顶点序列是DFS树中由根开始的一条路径。(3)

Adj(u)中的下一个顶点v不是白色的。这是对v的后续访问，DFS本身并不做任何操作，但在解决具体应用问题时，须结合具体问题而设计相应的操作。25

26DFS导致的图中边的分类在我们完成DFS时，除了DFS树或森林，图中其他的边往往被忽略。因为这些边在某些应用中有用，我们对它们进行分类。在一个有向图中，如果(u,v)不在DFS树里，v

Adj(u)。它被称为以下3种边之一，并且可以在DFS进行中被判定：

反向边(backedge)如果v是u的一个祖先。判断条件：v是灰色，或DFS树中有从v到u的路径。

前向边(forwardedge)如果v是u的一个后代。判断条件：v是黑色且d(u)<d(v)。

交叉边(crossedge)如果u和v无直系关系。判断条件：v是黑色且d(u)>d(v)。注：无向图只可能有反向边。27例8.1

对下面的有向图进行从顶点a开始的DFS搜索并标出各点的发现时刻和完成时刻。当搜索中有多个选择时，用字母顺序确定。DFS搜索完成后，画出DFS树或DFS森林。同时，对非树边标出它的类别。28解：下面图逐步显示DFS搜索的过程。当DFS发现顶点u时，我们在u的旁边标以d(u)/，而在u的完成时刻在u的边上标以d(u)/f(u)。2930层3132拓扑排序(Topologicalsort)将一个无回路的有向图(DirectedAcyclicgraph,DAG)中的顶点排序，使得该序列的顺序和图中每一条边都一致：只要(a,b)是图中一条边，在序列中，顶点a就一定出现在b的前面。一个无回路有向图的例子(图8-8)离散数学计算机原理操作系统体系结构计算机算法知识产权数据结构逻辑设计C++语言汇编语言33上例描述了计算机系研究生应修的10门课之间的关系。边(a,b)表明，必须先完成课程a才可以选b。假设某研究生每学期只能上一门课，他应该按照什么顺序来选这10门课程使得他能在10个学期内完成所有课程并且在每学期上课时，所有前序课程都已完成？拓扑排序算法Topological-Sort(G(V,E))建一个空的链表L。调用DFS(G(V,E))对图G进行深度优先搜索。DFS进行中的附加操作是，在每个顶点的完成时刻，将该顶点插入到链表L的头部。顺序输链表L中各顶点。5

End该算法实际上是把顶点按它们的完成时刻，从大到小排序。34例:对上面有向图作拓扑排序的结果如下：离散数学计算机原理逻辑设计计算机算法C++语言汇编语言操作系统体系结构知识产权数据结构12/194/75/61/82/313/1815/169/1011/2014/17数据结构计算机原理汇编语言C++语言离散数学(1)(2)(3)(4)(5)操作系统计算机算法逻辑设计体系结构知识产权(6)(7)(8)(9)(10)35拓扑排序算法正确性证明：我们只需证明，一条边(u,v)中的两顶点u和v，一定会先输出v，后输出u，即f(v)<f(u)。我们分两种情况讨论：(1) d(u)<d(v)。发现u时，v是u的一个白色的邻居。由白路径定理，v将是u的后代，所以有f(v)<f(u)。(2) d(v)<

d(u)。发现v时，u是v的一个白色的邻居。由于图G无回路，不存在从v到u的路径，更没有白路径。所以，在DFS完成对v的访问之后，即时刻f(v)之后，才有可能去发现u。所以有f(v)<f(u)。因此，算法Topological-Sort(G(V,E))是正确的。36无回路有向图中最长路径问题及应用许多应用问题需要找图中两点间的最短或最长的简单路径。找最短路径是个比较容易的问题。不加权的图，一次BFS搜索就可以找到。加权的图，第10章会讨论两个知名算法。找图中最长路径是一个NP-完全问题，既使图不加权。但是，如果图没有回路，那么无论是有向图或无向图，加权或不加权，权值为正或为负，找最长或最短路径的问题都可以在线性时间O(|V|+|E|)=O(n+m)里解决。因为无回路的无向图是棵树或森林，问题显然可在O(n)时间里解决，所以我们假定图G是一个加权的有向图。下面的算法计算从顶点s到图G中其他各点的最长简单路径。37Longest-Path-for-DAG(G(V,E),s) for

eachv

V

d(v)

-

，

(v)

nil

//初始化endforTopological-Sort(G(V,E),s) //从s开始的拓扑排序Letv1(=s),v2,v3,....,vk,

bethesequencefromtopologicalsortd(s)

0for

i

1tok-1 foreachu

Adj(vi)

if

(d(vi)+w(vi,u))>d(u)

then

d(u)

d(vi)+w(vi,u)

(u)

vi

endif

endforendforEnd

38无回路有向图中最长路径的应用例子剧场内有两个电影院X和Y。在t

=0开始的一周内，X会顺序放映长短不一的电影x1，x2，…，xn，其每场开始和结束时间顺序为(a1，b1)，(a2，b2)，…，(an，bn)。同一周内，Y会连续放映m个电影，y1，y2，…，ym。其每场开始和结束时间顺序为(c1，d1)，(c2，d2)，…，(cm，dm)。每位观众必须准时入场并不得中途退场。又假定两电影院之间距离极近，覌众从一个影院走到另一个影院所需时间为零。现在，我们要从两个影院中选出一组时间互不冲突的电影使得一个观众可以一个接一个地看完这些电影，并且使得这个观众看电影的总时间最长。请设计一个O(m+n)的算法。39解：

构造有向图G(V,E)如下：V

={x1，x2，…，xn，y1，y2，…，ym，s，t}。xi代表电影xi(1

i

n)，yj

代表电影yj(1

j

m)。顶点s和t代表起点和终点。边由下面7部分组成：(xi，xi+1)(1

i

n-1)，权值为w(xi，xi+1)=bi-ai。(yj,yj+1)(1

j

m-1)，权值为w(yj,yj+1)=dj–cj。(xi,yj)(1

i

n-1)，权值为w(xi,yj)=bi-ai，如果yj是第一个满足bi

cj的电影。(yj，xi)(1

j

m-1)，权值为w(yj，xi)=dj–cj，如果xi是第一个满足dj

ai的电影。从顶点s分别有一条到x1和y1的边并有权值0。从顶点xn有一条到t的边(xn，t)并有权值w(xn，t)=bn–an。从顶点ym有一条到t的边(ym，t)并有权值w(ym，t)=dm–cm。40构造有向图G(V,E)的算法Construction-G(X,Y,A,B,C,D,m,n)V

{x1，x2，…，xn，y1，y2，…，ym，s，t}E

for

i

1to

n-1

E

E

{(xi,xi+1)withw(xi,xi+1)=(bi-ai)}endforfor

j

1to

m-1

E

E

{(yj,yj+1)withw(yj,yj+1)=(dj–cj)}endforE

E

{(s,x1)withw(s,x1)=0,(s,y1)withw(s,y1)=0}E

E

{(xn,t)withw(xn,t)=bn–an,(ym,t)withw(ym,t)=dm–cm}

i

j

1 //开始构造从影院X到影院Y的边

(接下页)41构造有向图G(V,E)的算法(继续)while

i

nand

j

m

if

bi

cj

then

E

E

{(xi,yj)withw(xi,yj)=(bi-ai)，i

i+1

else

j

j+1

endifendwhilej

i

1 //开始构造从影院Y到影院X的边while

j

mand

i

n

if

dj

ai

then

E

E

{(yj,xi)withw(yj,xi)=(dj–cj)，j

j+1

else

i

i+1

endifendwhilereturnG(V,E)End42算法Construction-G的复杂度分析第3行和第6行的两个for循环分别有复杂度O(n)和O(m)。上页(书上第12行)的while循环有复杂度O(n+m)，这是因为每循环一次，指针i或j就要加1，因此总共最多有m+n次循环。同理，另一个(书上第20行)的while循环有复杂度O(n+m)。

所以，算法Construction-G的复杂度是O(n+m)。看电影问题的解：图G(V,E)构造好之后，任何一个合理的解对应着一条从起点s到终点t的一条路径，反之亦然。这里，“合理”意味着不故意跳过一个可看电影，因为这样做显然不会最优。所以，图中一条最长路径对应最佳解。因为无回路并且顶点和边的个数分别都是O(n+m)，我们可用Longest-Path-for-DAG(G(V,E),s)算法在O(n+m)时间内找到最佳解。43有向图的强连通分支分解如果任一顶点都有一条通向其他任一顶点的路径，那么这个有向图称为一个强连通图(StronglyConnectedGraph)。如果一个有向图的子图是个强连通图，则称为强连通子图(StronglyConnectedSubgraph)。如果一个强连通子图已最大化，即不能再加入其他任何一个顶点而仍然强连通，那么这个子图称为强连通分支(StronglyConnectedComponent)。有向图的强连通分支问题就是把一个有向图的顶点划分为不相交的若干个强连通分支。44例bcefgda(a)一个有向图bcefgda(b)分解为两个强连通分支强连通分支分解算法见下页45Strongly-Connected-Component(G(V,E))对G进行DFS搜索并按完成时刻，从大到小，排序为

f(v1)

>f(v2)

>…>f(vn)。2 构造G的转置图GT(V,E’)，其中，V不变，边的集合E’是把E中每条边反向后得到，即E’={(u,v)|(v,u)

E}。把所有GT中顶点着以白色。顺序检查序列v1，v2，…，vn。如果vk

(1

k

n)仍是白色，则从vk开始，对图GT进行一轮DFS搜索。所有在这一轮首次访问到的顶点，也就是在这一轮变黑色的顶点，形成一个强连通分支，将其输出。继续第4步直到所有点都被输出。End //算法的复杂度显然是O(m+n)46例8.4

对例8.1中有向图顶点进行强连通分支分解。顶点序列： a，g，h，s，k，e，d，b，p，m，f，c，j。474849强连通分支算法证明：先介绍强连通分支图，简称分支图。分支图GC(VC,EC)中每个顶点u

VC

代表一个强连通分支。边(u,v)

EC

当且仅当在原图G(V,E)中有一条从分支u中顶点到分支v中顶点的边。分支图无回路，否则回路上的所有分支都应属于同一连通分支。例前面例子的分支图（不是GT的分支图）：a,d,

ep,f,

mg,s,

h,kb,j,

c(接下页)50强连通分支算法证明

(继续1)现在证明，如果图G的分支图中有边(u,v)，那么，分支u和分支v的所有顶点中，有最大完成时刻的点必定落在分支u中。分两种情况讨论：这些顶点中，最先发现的顶点x在分支u中。因u和v强连通，又有边(u,v)，x有路径到达u

和v中任何一个点。所以，在时刻d(x)，x有白路径到达u

和v中任何一点。因此，这些点都是x的后代，因而对x的访问最后完成。这些顶点中，最先被发现的顶点x在分支v中。因为分支图无回路，所以x没有到分支u中点的路径。当分支v中点都完成时，u中的点仍然都是白色的。所以，最后完成的点也必定落在分支u中。证毕。(接下页)51强连通分支算法证明(继续2)设算法对图G的DFS最后完成的顶点x在分支u，那么在图G中只有从分支u出去的边而没有进来的边。由于强连通分支的划分在转置图GT中不变，所以分支u在GT中只有进来的边而没有出去的边。所以，从x开始对GT作DFS搜索时，分支u中所有点会被访问到，但跑不出分支u。所以，第一轮DFS正好把分支u分离出来。第二轮DFS从分支u以外的点中最后完成的顶点y开始。也就是算法第一步产生的序列f(v1)>f(v2)>…>f(vn)中，第一个仍然还是白色的顶点。那么，除分支u以外(u中点已黑色)，点y所在的分支在GT中只有进来的边而没有出去的边。这样，第二轮DFS便正确地分离了这个分支。依次类推，每一轮DFS正确分离一个强连通分支，直止所有点被访问到。

52无向图的双连通分支的分解一个顶点称为断点，如果把这个点及与之相关联的边从图中删去后，这个图不连通。没有断点的图称为双连通图。一个子图称为双连通子图，如果它是双连通的。一个子图称为双连通分支，如果它是双连通的并且最大化。双连通分支的分解是对边的一种划分。例53上图(a)可分解为两个双连通分支。下面的观察可帮助我们把断点识别出来。(1)

DFS树中任一个叶子顶点不可能是断点。(2) DFS树的根是断点，当且仅当它有两个或更多的儿子。(3) DFS树中根以外的内结点u是一个断点，当且仅当它的某个子树中的点没有反向边指向u的祖先(u本身不算)。54下图帮助解释上面第3条55双连通分支分解算法简介用DFS，但不记录完成时刻，发现时刻d(u)从1到n标记。用变量back(u)记录点u的一个反向边，或者u的任一个后代x的一个反向边能达到的最高祖先的高度。

back(u)=min{d(w)|w=u

或u的后代x有反向边(x,w)}。u本身也算作它自己的后代，所以有back(u)≤d(u)。计算和更新back(u)的做法：当u被发现时，置back(u)

d(u)。当发现一条反向边(u,a)时，更新back(u):

back(u)

min{d(a)，back(u)}当u的一个儿子v回溯到u时，如果back(v)<d(u)，那么back(u)

min{back(v)，back(u)}。56断点识别与分支的切割当v回溯到u时，如果back(v)

d(u)，那么，u是断点。把以v为根的子树T(v)以及边(u,v)从当前的DFS树中割开(一裂为二)。由于DFS的递归性，从u裂开时，子树T(v)中其他断点都已在早先被识别，而相应的双连通分支也已被切割。当前切下的分支所包含的边是，从访问边(u,v)开始，到v回溯到u为止，除去已切割的分支，DFS访问过的所有边。我们专门用一个堆栈S’来保留访问过的边。当一个分支被切割时，它的边被弹出。当v回溯到u时，如果发现back(v)

d(u)，弹出堆栈S’中边直到边(u,v)被弹出。当u是DFS树根时以上做法也正确，它会把DFS树根的每一个子树从根裂开并形成一个双连通分支。(算法见下页)57Bi-Connected-Component(G(V,E),s) //G为连通图，s可任取for

eachu

V

//DFS初始化开始

color[u]

White；

[u]

nilendforcolor(s)

Gray；

time

1 //时间戳从1开始back(s)

d(s)

timek

0 //双连通分支编号，将从1开始

S

S’

；

//DFS所用堆栈和边的堆栈清空Push(S,s) //初始化完成，点s入栈while

S≠

u

Top(S) //不是弹出，而是建立指针 v

u’snextneighborinAdj(u) //u的下一个邻居v

if

v≠nil

//u还有邻居未被访问

thenifcolor(v)

=White //

首次访问v，v是白色的

(接下页)58Bi-Connected-Component

(继续)

then

time

time+1;

d(v)

time

back(v)

d(v)

//初始化back(v)

(v)

u,

color(v)

=Gray

Push(S,v)，Push(S’,(u,v))

else back(u)

min{back(u),d(v)}//反向边

Push(S’,(u,v))

endif

else

color(u)

Black,

Pop(S)

ifS≠ //u有父亲

then

w

Top(S) //父亲是w

if

back(u)<d(w)