第三章 图与遍历算法 §1 图的基本概念和术语 null 无向图(undirected graph) 哥尼斯堡七桥 Euler 图 无向图，简称图，是一个用线（边）连接在一起的节点（顶点）的集合。严 格地说，图是一个三元组 G=( V, E, I ), 其中，V 是顶点的集合，E 是边的集 合，而 I 是关联关系，它指明了 E 中的每条边与 V 中的每个顶点之间的关联关 系：每条边必定连接两个而且只有两个顶点，它们称为该边的端点。连接顶点v 的边的条数称为v的度，记做d(v). 图G=( V, E, I )中顶点的度与边数有如下 关系 ||2)( Evd Vv = ∑ ∈ （3.1.1） 由公式（1）可知， 图中奇度顶点的个数一定是偶数 。 没有重边的图称为简单图，n 阶完全图是指具有 n 个顶点而且每两个顶点之 间都有边连接的简单图，这样的图的边数为n(n-1)/2.以下是1－4阶的完全图： 另一类特殊的图是偶图（也叫二分图） ，它的顶点集分成两部分 V 1 ，V 2 ，同 一部分的顶点之间不相连（没有边连接） 。 一个偶图 设图 G 的顶点集是 V={v 1 , v 2 , …,v n }，边集是 E={e 1 , e 2 , …,e m }，则顶点 与顶点之间的邻接关系、顶点与边之间的邻接关系可以列表如下： v 1 v 2 … v n v 1 a 11 a 12 … a 1n 邻接矩阵 v 2 a 21 a 22 … a 2n A=(a ij ) n×n 。 。 。 … 。 。 。 。 … 。 。 。 。 … 。 v n a n1 a n2 … a nn 其中 ? ? ? = otherwise adjacentarevandvif a ji ij 0 1 e 1 e 2 … e m v 1 c 11 c 12 … c 1m 关联矩阵 v 2 c 21 c 22 … c 2m M=(c ij ) n×m 。 。 。 … 。 。 。 。 … 。 。 。 。 … 。 v n c n1 c n2 … c nm K 1 K 4 K 3 K 2 V 1 V 2 其中 ? ? ? = otherwise eofpoendtheofoneisvif c ji ij 0 1 ints 图3-1-1 一个具有7 5 个顶点的图 图3-1的邻接矩阵为 A，关联矩阵是 M ： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 0110000 1010000 1101000 0010000 0000001 0000001 0000110 A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 1100000 1010000 0111000 0001000 0000110 0000011 0000101 M 图的另一个重要概念是路径，途径、迹、路。 途径 ：顶点与边交叉出现的序列 v 0 e 1 v 1 e 2 v 2 ··· e l v l (3.1.2) 其中e i 的端点是v i－1 和v i 。 迹 是指边不重复的途径，而顶点不重复的途径称为 路 。路是要求最严的。 一条途径： v 1 e 1 v 2 e 10 v 4 e 5 v 3 e 9 v 1 e 1 v 2 e 2 v 8 一条迹： v 1 e 1 v 2 e 10 v 4 e 5 v 3 e 9 v 1 e 4 v 7 一条路： v 1 e 1 v 2 e 10 v 4 e 5 v 3 e 8 v 5 e 12 v 7 图3-1-2 立方体 H 起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不 V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 e 1 e 2 e 3 e 5 e 6 e 7 e 8 e 9 e 10 e 11e12 e 4 e 5 e 6 e 7 e 4 6 4 5 7 e 1 1 e 2 e 3 3 2 重复的闭迹称为 圈 。没有圈的图称为 森林 。如果存在一条以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是森林。 null 有向图 图3-1-3 一个有向图及其 双向连通分支 2 3 4 5 6 1 单向 单向 单向单向 街道 1 街道 3街道 2 大街 1 大街 2 2 3 4 5 6 1 描述单行道系统就不能用无向图，因 为它不能指明各条路的方向。所谓有 向图实际上是在无向图的基础上进一步指定各条边的方向。在有向图中，顶点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个双向连通分支，分别用不同的颜色标出。 null 加权图与网络 一般的加权图是指对图的每条边e赋予一个实数值W(e)。如架设连接各城 镇的交通路网，需考虑各段线路的修建费用；在运输网络中要考虑网络各段线路 的容量，等等。 图3-1－4 一个交通路网 网络是一个这样的加权有向图，其指明了 收点集 和 发点集， 在图3-5中分别 用粉色和黄色标出。其余的顶点称为内点（绿色） 。 6 26 3 7 2 3 1 3 6 8 3 图3-1－5 网络 §2 图的遍历(搜索)算法 null 二叉树的遍历 一棵完全的二叉树 一棵完整的二叉树 对于二叉树的搜索按照子树的根的优先访问次序分为：先跟次序搜索、中根 次序搜索和后跟次序搜索三种方式，如下图所示。 2 V 2 V 4 V 1 V 3 X 1 X 2 Y 1 Y 2 Y 3 1 2 3 2 6 5 1 45 3 6 4 2 4 1 A B C D E F G H I J A B C D E F G H I K M O NL 1 A B D F H G I C E 4 3 5 6 7 8 9 2 中根次序搜索 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 先根次序搜索 二叉树的中根次序遍历算法伪代码 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 null 一般树的遍历算法 我们可以将二叉树的父与子之间的关系推广到树上，这样每个父亲的儿子 可以有许多个，而且可以排出顺序。于是，关于二叉树的三种遍历算法完全可以 移置到一般的树上来。 树的先根次序遍历算法 ： i. 若T为空，则返回； ii. 访问T的根； iii. 按树的先根次序遍历T的第一棵子树； iv. 按树的先根次序依次遍历T的其余子树。 树的中根次序遍历算法 ： v. 若T为空，则返回； vi. 按树的中根次序遍历T的第一棵子树； vii. 访问T的根； viii. 按树的中根次序依次遍历T的其余子树。 树的后根次序遍历算法 ： ix. 若T为空，则返回； x. 按树的先根次序遍历T的第一棵子树； xi. 按树的先根次序依次遍历T的其余子树。 xii. 访问T的根； null 一般图的遍历 无论是二叉树还是一般的树，由于其不含有圈，所以属于同根的各个子树之 间是相互独立的（树中去掉一点以及与之关联的所有边后，出现若干棵树，均称 之为以这点为根的子树） 。因此遍历过程是对各个子树的分别遍历和对根遍历以 及把这些遍历有机地组合起来。一般的图没有这种独立性，所以上述方法不能施 行。但是，上述方法的思想可以借鉴，于是产生了深度优先搜索方法和宽度优先 搜索方法。 问题 ： 在一个给定的图 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)}即可。 图G及其邻接链表 2。图的深度优先搜索 深度优先搜索是沿着顶点的邻点一直搜索下去，直到当前被搜索的顶点不 再有未被访问的邻点为止，此时，从当前辈搜索的顶点原路返回到在它之前被搜 索的访问的顶点，并以此顶点作为当前被搜索顶点。继续这样的过程，直至不能 B C 0 A D E 0 D E F G 0 A F G 0 C H 0 B H 0 B H 0 C H 0 A B C D E F G H A B C E FD G H 1 2 7 3 5 6 8 4 A B C E FD G H 图的深度优先搜索 1 2 3 4 5 6 7 8 A B C E FD G H 图的宽度优先搜索 执行为止。 图的深度优先搜索算法伪代码 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 双连通与网络可靠性 通信网络的抽象模型可以是一个无向图： 顶点代表通信站， 边代表通信线路。 下面的两个图代表两个通信网络： 直观可知，图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是双连通的。 A B E D F G C E I J D C A F GB H 图3-3-1 一个双连通图 图3-3-2 一个非双连通图 就通信网络而言，当然希望没有割点，如果现有的网络有割点，则设法增加 一些线路（当然希望尽量少的增加） ，使之成为双连通的。 添加边的算法： E1： for每个割点u do E2： 设B 1 ，B 2 ，… ，B k ，是包含割点u的全部双连通分支 E3： 设 V i 是B i 的一个顶点，且V i ≠u，1≤i≤k。 E4： 将(V i , V i+1 )添加到G，1≤i≤k。 E5： endfor 问题 ： 设计算法测试一个连通图是否双连通；若不是，算法将识别出割点。 解决方法：以深度优先遍历算法为基础，加以割点识别步骤。 当采用深度优先遍历算法时，顶点 v 被访问的序数称为 v 的深度优先数，记 做DFN(v). 按照深度优先树将图中的顶点分层，使得上层是下层的祖先，而同层之间是 I C E F J C E GB H D C A B 图3-3-3 所示图的5个双连通分支 E I J D C A F GB H 1 8 2 a 7 6 c d 9 3 4 5 10 b E I J D C A F GB H 添加边以形成双连通图 深度优先搜索树 兄弟关系： 深度优先树的性质： 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的定义可知这两步工作可以同时完成。 计算DF N和L的算法伪代码 A D BI E J C G F H 8 d 1 a b c6 4 5 1 1 6 6 1 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做如下修改： null 引进一个存放边的全程栈S； null 在2到3 行之间加： 2．1 if v≠w and DFN(w)<DFN(u) then 2.2 将(u,w)加到S的顶部； 2.3 endif null 在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的全部双连通分支。 证明：略。