算法设计与分析 第三章 图与遍历算法.doc

第三章 图与遍历算法

§1 图的基本概念和术语
l 无向图(undirected graph)

哥尼斯堡七桥

Euler 图

无向图，简称图，是一个用线（边）连接在一起的节点（顶点）的集合。严格地说，图是一个三元组G=( V, E, I ), 其中，V是顶点的集合，E是边的集合，而I 是关联关系，它指明了E中的每条边与V中的每个顶点之间的关联关系：每条边必定连接两个而且只有两个顶点，它们称为该边的端点。连接顶点v的边的条数称为v的度，记做d(v). 图G=( V, E, I )中顶点的度与边数有如下关系
（3.1.1）
由公式（1）可知，图中奇度顶点的个数一定是偶数。
没有重边的图称为简单图，n阶完全图是指具有n个顶点而且每两个顶点之间都有边连接的简单图，这样的图的边数为n(n-1)/2.以下是1－4阶的完全图：

K1
K4
K3
K2

另一类特殊的图是偶图（也叫二分图），它的顶点集分成两部分V1，V2，同一部分的顶点之间不相连（没有边连接）。
V1

V2

一个偶图

设图G的顶点集是V={v1, v2, …,vn}，边集是E={e1, e2, …,em}，则顶点与顶点之间的邻接关系、顶点与边之间的邻接关系可以列表如下：

v1 v2 … vn
v1 a11 a12 … a1n 邻接矩阵
v2 a21 a22 … a2n A=(aij)n×n
。 。 。 … 。
。 。 。 … 。
。 。 。 … 。
vn an1 an2 … ann

其中

e1 e2 … em
v1 c11 c12 … c1m 关联矩阵
v2 c21 c22 … c2m M=(cij)n×m
。 。 。 … 。
。 。 。 … 。
。 。 。 … 。
vn cn1 cn2 … cnm

其中

e1
1
e2
e3
3
2
e5
e6
e7
e4
6
4
5
7

图3-1-1
一个具有7
5 个顶点的图

图3-1的邻接矩阵为，关联矩阵是：

图的另一个重要概念是路径，途径、迹、路。
途径：顶点与边交叉出现的序列
v0 e1 v1 e2 v2 ··· el vl (3.1.2)
其中ei的端点是vi－1和vi 。 迹是指边不重复的途径，而顶点不重复的途径称为路。路是要求最严的。
V1
V2
V3
V4
V5
V6
V7
V8
e1
e2
e3
e5
e6
e7
e8
e9
e10
e11
e12
e4

一条途径：
v1e1v2e10v4e5v3e9v1e1v2e2v8
一条迹：
v1e1v2e10v4e5v3e9v1e4v7
一条路：
v1e1v2e10v4e5v3e8v5e12v7

图3-1-2 立方体 H
起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。没有圈的图称为森林。如果存在一条以u为起点、v为终点的途径，则说顶点u可达顶点v。如果图G中任何两个顶点之间都是可达的，则说图G是连通。如果图G不是连通的，则其必能分成几个连通分支。图3-2是连通的，而图3-1不是连通的，它有两个连通分支。
不含圈的连通图称为树，森林的连通分支是树，也就是说，森林是由树组成的。森林即是不含圈的图。适当去掉连通图中的一些边后，会得到一个不含圈、而且包含所有顶点的连通图，它是一棵树，称为原图的生成树。生成树是其所在的图中边数最少的连通生成子图，因此，具有n个顶点的连通图的边数至少是 n-1 .不连通图没有生成树，但有生成森林。如果不连通图G有k个连通分支，则G的边数至少是n-k.
定理3.1.1 如果G是具有n个顶点、m条边的图，下列结论成立：
1． 若G是树， 则m = n-1；
2． 若G是连通图，而且满足m = n-1，则G是树；
3． 若G不包含圈，而且满足m = n-1，则G是树；
4． 若G是由k棵树构成的森林，则m = n-k ；
5． 若G有k个连通分支，而且满足m = n-k，则G是森林。

单向
单向
单向
单向
街道1
街道3
街道2
大街1
大街2
2
3
4
5
6
1
l 有向图

2
3
4
5
6
1

图3-1-3
一个有向图及其
双向连通分支

描述单行道系统就不能用无向图，因为它不能指明各条路的方向。所谓有向图实际上是在无向图的基础上进一步指定各条边的方向。在有向图中，顶点v的出度是指由顶点v出发的有向边的条数，记做d＋(v)；而入度则是指向顶点v的有向边的条数, 记做d-(v)。此外也有顶点度的概念，它是该顶点的出度与入度的和: d(v)=d＋(v)+d-(v)。
在有向图中，许多概念都可以通过无向图的相关概念加“有向”二字得到，如 有向边、有向途径、有向迹、有向路、有向圈，等等。有向图和无向图可以相互转化：将一个无向图的每条边都规定方向后，即得到有向图，其称为原无向图的一个定向图；将一个有向图的各条有向边的方向去掉，即得到一个无向图，其称为原有向图的基础图。
有向图中也有一些概念不能由无向图通过简单地附加“有向”一词而得到。如，连通，有向图D说是连通的是指其基础图是连通的。如果D中任意两个顶点都是可达的，则说有向图D是双向连通的（或叫强连通）。这里，顶点u可达顶点v是指存在一条以u为起点、v为终点的有向路。这里的起点、终点不能互为替换。有向图3-3就是连通的，但不是双向连通的，因为从任何顶点出发，都没有到达顶点3的有向途径。不是双向连通的有向图可以分解成几个双向连通分支。图3-3共有5个双向连通分支，分别用不同的颜色标出。

l 加权图与网络
一般的加权图是指对图的每条边e赋予一个实数值W(e)。如架设连接各城镇的交通路网，需考虑各段线路的修建费用；在运输网络中要考虑网络各段线路的容量，等等。
61
2
6
3
7
2
3
1
3
6
8
3

图3-1－4 一个交通路网

网络是一个这样的加权有向图，其指明了收点集和发点集，在图3-5中分别用粉色和黄色标出。其余的顶点称为内点（绿色）。

V2
V4
V1
V3
X1
X2
Y1
Y2
Y3
1
2
3
2
6
5
1
4
5
3
6
4
2
4
1

2

图3-1－5 网络

§2 图的遍历(搜索)算法

l 二叉树的遍历
J
A
B
C
D
E
F
G
H
I
K
M
O
N
L
A
B
C
D
E
F
G
H
I

一棵完全的二叉树 一棵完整的二叉树

对于二叉树的搜索按照子树的根的优先访问次序分为：先跟次序搜索、中根次序搜索和后跟次序搜索三种方式，如下图所示。
1
A
B
D
F
H
G
I
C
E
4
2
3
7
6
9
8
5
后根次序搜索
4
A
B
D
F
H
G
I
C
E
5
6
7
2
8
1
9
3
先根次序搜索
1
A
B
D
F
H
G
I
C
E
4
3
5
6
7
8
9
2
中根次序搜索

二叉树的中根次序遍历算法伪代码
InOder(T) // T是一棵二叉树，T的每个顶点有三个信息段：
//Lchild,Data,Rchild
if T≠0 then
InOrder(Lchild(T));
Visit(T);
InOrder(Rchild(T));
endif
endInOrder

二叉树的先根次序遍历算法伪代码
PreOder(T) // T是一棵二叉树，T的每个顶点有三个信息段：
//Lchild,Data,Rchild
if T≠0 then
Visit(T);
PreOrder(Lchild(T));
PreOrder(Rchild(T));
endif
endPreOrder

二叉树的后根次序遍历算法伪代码
PostOder(T) // T是一棵二叉树，T的每个顶点有三个信息段：
//Lchild,Data,Rchild
if T≠0 then
PostOrder(Lchild(T));
PostOrder(Rchild(T));
Visit(T);
endif
endPostOrder

l 一般树的遍历算法
我们可以将二叉树的父与子之间的关系推广到树上，这样每个父亲的儿子可以有许多个，而且可以排出顺序。于是，关于二叉树的三种遍历算法完全可以移置到一般的树上来。
树的先根次序遍历算法：
i. 若T为空，则返回；
ii. 访问T的根；
iii. 按树的先根次序遍历T的第一棵子树；
iv. 按树的先根次序依次遍历T的其余子树。
树的中根次序遍历算法：
v. 若T为空，则返回；
vi. 按树的中根次序遍历T的第一棵子树；
vii. 访问T的根；
viii. 按树的中根次序依次遍历T的其余子树。
树的后根次序遍历算法：
ix. 若T为空，则返回；
x. 按树的先根次序遍历T的第一棵子树；
xi. 按树的先根次序依次遍历T的其余子树。
xii. 访问T的根；
l 一般图的遍历
无论是二叉树还是一般的树，由于其不含有圈，所以属于同根的各个子树之间是相互独立的（树中去掉一点以及与之关联的所有边后，出现若干棵树，均称之为以这点为根的子树）。因此遍历过程是对各个子树的分别遍历和对根遍历以及把这些遍历有机地组合起来。一般的图没有这种独立性，所以上述方法不能施行。但是，上述方法的思想可以借鉴，于是产生了深度优先搜索方法和宽度优先搜索方法。
问题：在一个给定的图G=(V,E)中是否存在一条起于顶点v而终于顶点u的路径？确定与某一起点v有路相通的所有顶点。
1。宽度优先搜索算法（BFS）
开始：起点v和一个空的待访队列Q。
从顶点v开始访问，并将v标记为已访问的顶点。然后顺序（这个顺序通常是图的顶点存储顺序）搜索邻接于顶点v的未被访问的顶点，并把这些顶点依次放在待访队列Q的尾部。
用队列Q的首元素u替换v（并从队列Q中去掉首元素u），重复以上过程，直到队列Q空为止。

图的宽度优先搜索算法伪代码
BFS(v) //宽度优先搜索G，从顶点v开始执行
// 所有已搜索的顶点i都标记为Visited(i)=1.
//Visited的初始分量值全为0
1. Visited(v)=1;
2. Q=[];//将Q初始化为只含有一个元素v的队列
3. while Q非空 do
4. u=DelHead(Q);
5. for 邻接于u的所有顶点w do
6. if Visited(w)=0 then
7. AddQ(w,Q); //将w放于队列Q之尾
8. Visited(w)=1;
9. endif
10. endfor
11. endwhile
12. end BFS
这里调用了两个函数：AddQ(w,Q)是将w放于队列Q之尾；DelHead(Q)是从队列Q取第一个顶点，并将其从Q中删除。
定理3.2.1 图G的宽度优先搜索算法能够访问G中由v可能到达的所有顶点。如果记t(,e)和s(,e)为算法BFS在任意一个具有个顶点和条边的图G上所花的最大时间和最大空间。则
t(,)=Θ(+), s(,)=Θ() 当G由邻接链表表示时；
t(,)=Θ(2), s(,)=Θ() 当G由邻接矩阵表示时；
证明略。
由定理2可知，宽度优先搜索算法能够遍历图G的包含v的连通分支中的所有顶点。对于不连通的图，可以通过在每个连通分支中选出一个顶点作为起点，应用宽度搜索算法于每个连通分支，即可遍历该图的所有顶点。
图的宽度优先遍历算法伪代码
BFT(G, ) //图G的宽度优先遍历
for i from 1 to do
Visited(i)=0; //将所有的顶点标记为未被访问
endfor
for i from 1 to do
if Visited(i)==0 then BFS(i); endif
endfor
end BST

关于BST算法的时间和空间复杂性与BFS同样估计，略。
如果G是连通图，则G有生成树。注意到BFS算法中，由5～10行，将所有邻接于顶点u但未被访问的顶点w添加到待访队列中。如果在添加w的同时将边(u,w)收集起来，那么算法结束时，所有这些边将形成图G的一棵生成树。称为图G的宽度优先生成树。为此，在BFS算法的第1行增加语句T={}；在第7行增加语句T=T∪{(u,w)}即可。

B 0
C 0 0
A 0
D 0
E 0 0
D 0
E 0
F 0
G 0 0
A 0
F 0
G 0 0
C 0
H 0 0
B 0
H 0 0
B 0
H 0 0
C 0
H 0 0
A
B
C
D
E
F
G
H
A
B
C
E
F
D
G
H

图G及其邻接链表

1
2
3
4
5
6
7
8
A
B
C
E
F
D
G
H
图的宽度优先搜索
1
2
7
3
5
6
8
4
A
B
C
E
F
D
G
H
图的深度优先搜索

2。图的深度优先搜索
深度优先搜索是沿着顶点的邻点一直搜索下去，直到当前被搜索的顶点不再有未被访问的邻点为止，此时，从当前辈搜索的顶点原路返回到在它之前被搜索的访问的顶点，并以此顶点作为当前被搜索顶点。继续这样的过程，直至不能执行为止。
图的深度优先搜索算法伪代码
DFS(v) //访问由v到达的所有顶点
1. Visited(v)=1;
2. for邻接于v的每个顶点w do
3． if Visited(w)=0 then
4. DFS(w);
5. endif
6. endfor
7．end DFS

§3 双连通与网络可靠性
通信网络的抽象模型可以是一个无向图：顶点代表通信站，边代表通信线路。下面的两个图代表两个通信网络：
E
I
J
D
C
A
F
G
B
H

A
B
E
D
F
G
C

图3-9一个非双连通图
图3-8一个双连通图

直观可知，图3-8的通信网络可靠性较高，因为即使有一个网站出现问题，其他网站之间的通信仍能够继续进行。而图3-9所示的网络则不能，只要网站B发生故障，位于其左右两部分的网站之间就无法连通了。在图中，象B点这样的顶点称为割点，。
定义3.3.1 连通无向图G中的顶点v称为割点，如果在G中去掉v及其关联的边，剩下的图就不再连通。没有割点的连通图称为双连通的（也称为块、2－连通等）。图G中极大的双连通子图称为G的一个双连通分支。
在图3-9中除了B以外，C和E也都是割点。这个图有5个双连通分支（参见图3-10）.图3-8是双连通的。

I
C
E
F
J
C
E
G
B
H
D
C
A
B
图3-3-3所示图的5个双连通分支

就通信网络而言，当然希望没有割点，如果现有的网络有割点，则设法增加一些线路（当然希望尽量少的增加），使之成为双连通的。

1
8
2
a
7
6
c
d
9
3
4
5
10
b
E
I
J
D
C
A
F
G
B
H
E
I
J
D
C
A
F
G
B
H

深度优先搜索树
添加边以形成双连通图

添加边的算法：
E1： for每个割点u do
E2： 设B1，B2，… ，Bk，是包含割点u的全部双连通分支
E3： 设 Vi是Bi的一个顶点，且Vi≠u，1≤i≤k。
E4： 将(Vi, Vi+1)添加到G，1≤i≤k。
E5：endfor
问题：设计算法测试一个连通图是否双连通；若不是，算法将识别出割点。
解决方法：以深度优先遍历算法为基础，加以割点识别步骤。
当采用深度优先遍历算法时，顶点v被访问的序数称为v的深度优先数，记做DFN(v).
按照深度优先树将图中的顶点分层，使得上层是下层的祖先，而同层之间是兄弟关系：
A
D

B
I
E
J
C
G

g
F
H
8
d
1
a
b
c
6
4
5
1
1
6
6
1

深度优先树的性质：
1．关于深度优先树T，图G的每一条边(u,v)的两个端点u、v
之间，或u是v的祖先，或v是u的祖先。
2．树T的根顶点是图G的割点当且仅当其在T中至少有两个儿子；不是T的根的顶点u不是G的割点当且仅当u在T中的每个儿子w都至少有一个子孙（或w本身）关联着一条边e，e的另一个端点是u的某个祖先（e一定是树T的余边）。
根据性质2，深度优先树T的非根顶点u是G的割点当且仅当u至少有一个儿子w，w及其子孙都不与u的任何祖先相邻。注意到u的深度优先数一定小于其子孙的深度优先数，所以深度优先数DFN并不能反映一个顶点是否是割点的情况。为此，我们递归地定义最低深度优先数L：
定义3.3.2 顶点u 的最低深度优先数L(u)定义为
L(u)=min{DFN(u),min{L(w)|w是u的儿子}，
Min{DFN(x)|(u,x)是T的余边}}
可见，如果L(u)≠DFN(u),则必定L(u)< DFN(u),因而L(u)是u通过一条子孙路径且至多后跟一条T的余边所可能到达的最低深度优先数。如果u不是根顶点，则u是图G的割点当且仅当u有某个儿子w，其最低深度优先数不小于u的深度优先数：L(w)≥DFN(u)。看来要想识别图G的所有割点，需先获得深度优先生成树T，然后按后根优先次序遍历T计算出各个顶点的最低深度优先数。但是，从函数L的定义可知这两步工作可以同时完成。
计算DFN和L的算法伪代码
DFNL(u,v) //一个深度优先搜索算法，u是开始顶点,
//在深度优先树中，若u有父亲，则v即是。数组
//DFN初始化为0，num初始化为1，n是图G的顶
//点数。
global DFN[n]，L[n]，num，n
1． DFN(u)=num; L(u)=num; num=num+1;
2． for 每个邻接于u的顶点w do
3． If DFN(w)==0 then DFNL(w,u) //还未访问w
4． L(u)=min(L(u),L(w));
5． else
6． if w≠v then L(u)=min(L(u),DFN(w)); endif
7． endif
8． endfor
9．end DFNL

为了得到图G的双连通分支，需对DFNL作一些修改。注意到，在第3行调用DFNL时，如果出现情况：L(w)≥DFN(u)，就可以断定u或是T的根，或是图G的割点。不论那种情况，都将边(u,w)和对DFNL这次调用期间遇到的所有树边和余边加在一起（除了包含在子树w中其它双连通分支中的边以外），就构成图G的一个双连通分支。鉴于此，将DFNL做如下修改：
ü 引进一个存放边的全程栈S；
ü 在2到3行之间加：
2．1 if v≠w and DFN(w)<DFN(u) then
2.2 将(u,w)加到S的顶部；
2.3 endif
ü 在3到4行之间加下列语句：
3.1 if L(w)≥DFN(u) then
3.2 print（’new biconnected component’）;
3.3 loop
3.4 从栈S的顶部删去一条边；
3.5 设这条边是(x,y)
3.6 print(‘(‘,x,’,’,y,’)’);
3.7 until ((x,y)=(u,w) or(x,y)=(w,u));
3.8 endif
如果G是有n个顶点m条边连通图，且G有邻接链表表示，
那么DFN的计算时间是O(n+m).一旦算出L[1:n],G的割点就能在O(n)时间识别出来，因此，识别全部割点总的时间不超过O(n+m).当DFNL增加了上述语句之后，其计算时间仍然是O(n+m).
定理3.3.1 设G是至少有两个顶点的连通图，则算法DFN增加了语句2.1-2.3和3.1-3.8的算法DFNL能正确生成G的全部双连通分支。
证明：略。