第三章图与遍历算法 §1图的基本概念和术语 ●无向图( undirected graph) 哥尼斯堡七桥 Euler 图 无向图,简称图,是一个用线(边)连接在一起的节点(顶点)的集合。严 格地说,图是一个三元组G=(V,E,I),其中,V是顶点的集合,E是边的集 合,而I是关联关系,它指明了E中的每条边与V中的每个顶点之间的关联关 系:每条边必定连接两个而且只有两个顶点,它们称为该边的端点。连接顶点v 的边的条数称为v的度,记做d(v).图G=(V,E,I)中顶点的度与边数有如下 关系 ∑d(v)=2|E (3.1.1) 由公式(1)可知,图中奇度顶点的个数一定是偶数。 没有重边的图称为简单图,n阶完全图是指具有n个顶点而且每两个顶点之 间都有边连接的简单图,这样的图的边数为n(n-1)/2.以下是1-4阶的完全图
第三章 图与遍历算法 §1 图的基本概念和术语 z 无向图(undirected graph) 哥尼斯堡七桥 Euler 图 无向图，简称图，是一个用线（边）连接在一起的节点（顶点）的集合。严 格地说，图是一个三元组 G=( V, E, I ), 其中，V 是顶点的集合，E 是边的集 合，而 I 是关联关系，它指明了 E 中的每条边与 V 中的每个顶点之间的关联关 系：每条边必定连接两个而且只有两个顶点，它们称为该边的端点。连接顶点 v 的边的条数称为 v 的度，记做 d(v). 图 G=( V, E, I )中顶点的度与边数有如下 关系 d(v) 2 | E | v V ∑ = ∈ （3.1.1） 由公式（1）可知，图中奇度顶点的个数一定是偶数。 没有重边的图称为简单图，n 阶完全图是指具有 n 个顶点而且每两个顶点之 间都有边连接的简单图，这样的图的边数为 n(n-1)/2.以下是 1－4 阶的完全图：
另一类特殊的图是偶图(也叫二分图),它的顶点集分成两部分V1,V2,同 一部分的顶点之间不相连(没有边连接)。 一个偶图 设图G的顶点集是v={v,V2,…,w},边集是E={e,e2,…,ea},则顶点 与顶点之间的邻接关系、顶点与边之间的邻接关系可以列表如下 anan2·an 邻接矩阵 a if vi and v i are adjacent 其中aj-10 otherwise 关联矩阵 M(ciinxa
另一类特殊的图是偶图（也叫二分图），它的顶点集分成两部分 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 其中 = otherwise if v and v are adjacent a i j ij 0 1 e1 e2 … em v1 c11 c12 … c1m 关联矩阵 v2 c21 c22 … c2m M=(cij)n×m 。 。 。 … 。 。 。 。 … 。 。 。 。 … 。 vn cn1 cn2 … cnm K1 K4 K3 K2 V1 V2
其中C I if vi is one of the end points of o otherwise 图3-1 一个具有7 个顶点的图 7 图3-1的邻接矩阵为A,关联矩阵是M: 0110000 01000 1000000 10000 1000000 011000 A=0000100M=000100 00000 0001011 000111 0000 01 000010 0000110 000001 图的另一个重要概念是路径,途径、迹、路。 途径:顶点与边交叉出现的序列 Vo el vi e2 v2 其中e的端点是v1-1和v1。迹是指边不重复的途径,而顶点不重复的途径称为 路。路是要求最严的 条途径: 一条迹: V VIelvee10vaesv3e9v1e4V7 ov6 一条路: e12 图3-1-2立方体H 起点和终点重合的途径称为闭途径,起点和终点重合的迹称为闭迹,顶点不
其中 = otherwise if v is one of the end po of e c i j ij 0 1 ints 图 3-1-1 一个具有 7 5 个顶点的图 图 3-1 的邻接矩阵为 A，关联矩阵是M ： = 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 A = 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 M 图的另一个重要概念是路径，途径、迹、路。 途径：顶点与边交叉出现的序列 v0 e1 v1 e2 v2 ··· el vl (3.1.2) 其中 ei的端点是 vi－1和 vi 。 迹是指边不重复的途径，而顶点不重复的途径称为 路。路是要求最严的。 一条途径： v1e1v2e10v4e5v3e9v1e1v2e2v8 一条迹： v1e1v2e10v4e5v3e9v1e4v7 一条路： v1e1v2e10v4e5v3e8v5e12v7 图 3-1-2 立方体 H 起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不 V1 V2 V3 V4 V5 V6 V7 V8 e1 e2 e3 e5 e6 e7 e8 e9 e10 e12 e11 e4 e5 e6 e7 e4 6 4 5 7 e1 1 e2 e3 3 2
重复的闭迹称为圈。没有圈的图称为森林。如果存在一条以u为起点、V为终点 的途径,则说顶点u可达顶点va如果图G中任何两个顶点之间都是可达的,则 说图G是连通。如果图G不是连通的,则其必能分成几个连通分支。图3-2是连 通的,而图3-1不是连通的,它有两个连通分支。 不含圈的连通图称为树,森林的连通分支是树,也就是说,森林是由树组 成的。森林即是不含圈的图。适当去掉连通图中的一些边后,会得到一个不含圈 而且包含所有顶点的连通图,它是一棵树,称为原图的生成树。生成树是其所在 的图中边数最少的连通生成子图,因此,具有n个顶点的连通图的边数至少是 n-1.不连通图没有生成树,但有生成森林。如果不连通图G有k个连通分支 则G的边数至少是n-k 定理3.1.1如果G是具有n个顶点、m条边的图,下列结论成立 若G是树,则m=n-1 2.若G是连通图,而且满足m=n-1,则G是树; 3.若G不包含圈,而且满足m=n-1,则G是树; 4.若G是由k棵树构成的森林,则皿=n-k 5.若G有k个连通分支,而且满足m=n-k,则G是森林 有向图 街道1 街道2 街道3 大街 单向 大街2 单向 单向 单向 图3-1-3 个有向图及其 双向连通分支
重复的闭迹称为圈。没有圈的图称为森林。如果存在一条以 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 是森林。 z 有向图 图 3-1-3 一个有向图及其 双向连通分支 2 3 4 5 6 1 单向 单向 单向 单向 街道 1 街道 2 街道 3 大街 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个双向连通分支,分别用不同的颜色标出。 加权图与网络 般的加权图是指对图的每条边e赋予一个实数值W(e)。如架设连接各城 镇的交通路网,需考虑各段线路的修建费用;在运输网络中要考虑网络各段线路 的容量,等等。 图3-1-4一个交通路网 网络是一个这样的加权有向图,其指明了收点集和发点集,在图3-5中分别 用粉色和黄色标出。其余的顶点称为内点(绿色)
描述单行道系统就不能用无向图，因为它不能指明各条路的方向。所谓有 向图实际上是在无向图的基础上进一步指定各条边的方向。在有向图中，顶点 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 个双向连通分支，分别用不同的颜色标出。 z 加权图与网络 一般的加权图是指对图的每条边 e 赋予一个实数值 W(e)。如架设连接各城 镇的交通路网，需考虑各段线路的修建费用；在运输网络中要考虑网络各段线路 的容量，等等。 图 3-1－4 一个交通路网 网络是一个这样的加权有向图，其指明了收点集和发点集，在图 3-5 中分别 用粉色和黄色标出。其余的顶点称为内点（绿色）。 6 6 2 3 7 2 3 1 3 6 8 3
图3-1-5网络 §2图的遍历(搜索)算法 ●二叉树的遍历 BOOboO 一棵完全的二叉树 棵完整的二叉树 对于二叉树的搜索按照子树的根的优先访问次序分为:先跟次序搜索、中根 次序搜索和后跟次序搜索三种方式,如下图所示 中根次序搜索 先根次序搜索 后根次序搜索
图 3-1－5 网络 §2 图的遍历(搜索)算法 z 二叉树的遍历 一棵完全的二叉树 一棵完整的二叉树 对于二叉树的搜索按照子树的根的优先访问次序分为：先跟次序搜索、中根 次序搜索和后跟次序搜索三种方式，如下图所示。 2 V2 V4 V1 V3 X1 X2 Y1 Y2 Y3 1 2 3 2 6 5 1 5 4 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 L M N O 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 ifT≠0then InOrder (Lchild (T)) Visit(t) InOrder(Rchild (T)) ndif endInOrder 叉树的先根次序遍历算法伪代码 PreOder(T)∥T是一棵二叉树,T的每个顶点有三个信息段: //Lchild, Data, Rchild ifT≠0then Visit(t) PreOrder (Lchild (T) PreOrder(Rchild(T)) endif endPreOrder 叉树的后根次序遍历算法伪代码 Postoder(T)//T是一棵二叉树,T的每个顶点有三个信息段: //Lchild, Data, Rchild ifT≠0then PostOrder(Lchild(T) PostOrder(Rchild (T)) Visit(t) endif endPostOrder ●一般树的遍历算法
二叉树的中根次序遍历算法伪代码 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 z 一般树的遍历算法
我们可以将二叉树的父与子之间的关系推广到树上,这样每个父亲的儿子 可以有许多个,而且可以排出顺序。于是,关于二叉树的三种遍历算法完全可以 移置到一般的树上来。 树的先根次序遍历算法 i.若T为空,则返回 访问T的根 ii.按树的先根次序遍历T的第一棵子树; iv.按树的先根次序依次遍历T的其余子树。 树的中根次序遍历算法 V.若T为空,则返回 按树的中根次序遍历T的第一棵子树 vi.访问T的根; vii.按树的中根次序依次遍历T的其余子树。 树的后根次序遍历算法 若T为空,则返回 x.按树的先根次序遍历T的第一棵子树; xi.按树的先根次序依次遍历T的其余子树。 访问T的根; 般图的遍历 无论是二叉树还是一般的树,由于其不含有圈,所以属于同根的各个子树之 间是相互独立的(树中去掉一点以及与之关联的所有边后,出现若干棵树,均称 之为以这点为根的子树)。因此遍历过程是对各个子树的分别遍历和对根遍历以 及把这些遍历有机地组合起来。一般的图没有这种独立性,所以上述方法不能施 行。但是,上述方法的思想可以借鉴,于是产生了深度优先搜索方法和宽度优先 搜索方法。 问题:在一个给定的图G=(V,E)中是否存在一条起于顶点v而终于顶点u 的路径?确定与某一起点ⅴ有路相通的所有顶点 1。宽度优先搜索算法(BFS) 开始:起点v和一个空的待访队列Q。 从顶点ⅴ开始访问,并将v标记为已访问的顶点。然后顺序(这个顺序通 常是图的顶点存储顺序)搜索邻接于顶点v的未被访问的顶点,并把这些顶点依 次放在待访队列Q的尾部。 用队列Q的首元素u替换ⅴ(并从队列Q中去掉首元素u),重复以上过程, 直到队列Q空为止。 图的宽度优先搜索算法伪代码
我们可以将二叉树的父与子之间的关系推广到树上，这样每个父亲的儿子 可以有许多个，而且可以排出顺序。于是，关于二叉树的三种遍历算法完全可以 移置到一般的树上来。 树的先根次序遍历算法： i. 若 T 为空，则返回； ii. 访问 T 的根； iii. 按树的先根次序遍历 T 的第一棵子树； iv. 按树的先根次序依次遍历 T 的其余子树。 树的中根次序遍历算法： v. 若 T 为空，则返回； vi. 按树的中根次序遍历 T 的第一棵子树； vii. 访问 T 的根； viii. 按树的中根次序依次遍历 T 的其余子树。 树的后根次序遍历算法： ix. 若 T 为空，则返回； x. 按树的先根次序遍历 T 的第一棵子树； xi. 按树的先根次序依次遍历 T 的其余子树。 xii. 访问 T 的根； z 一般图的遍历 无论是二叉树还是一般的树，由于其不含有圈，所以属于同根的各个子树之 间是相互独立的（树中去掉一点以及与之关联的所有边后，出现若干棵树，均称 之为以这点为根的子树）。因此遍历过程是对各个子树的分别遍历和对根遍历以 及把这些遍历有机地组合起来。一般的图没有这种独立性，所以上述方法不能施 行。但是，上述方法的思想可以借鉴，于是产生了深度优先搜索方法和宽度优先 搜索方法。 问题：在一个给定的图 G=(V,E)中是否存在一条起于顶点 v 而终于顶点 u 的路径？确定与某一起点 v 有路相通的所有顶点。 1。宽度优先搜索算法（BFS） 开始：起点 v 和一个空的待访队列 Q。 从顶点 v 开始访问，并将 v 标记为已访问的顶点。然后顺序（这个顺序通 常是图的顶点存储顺序）搜索邻接于顶点 v 的未被访问的顶点，并把这些顶点依 次放在待访队列 Q 的尾部。 用队列 Q 的首元素 u 替换 v（并从队列 Q 中去掉首元素 u），重复以上过程， 直到队列 Q 空为止。 图的宽度优先搜索算法伪代码
BFS(v)//宽度优先搜索G,从顶点ⅴ开始执行 //所有已搜索的顶点i都标记为 Visited(i)=1. // Visited的初始分量值全为0 1. Visited (v=1 2.Q=[;/将Q初始化为只含有一个元素v的队列 3. while Q非空do 4. u=DelHead (Q) for邻接于u的所有顶点wdo if Visited (w)=0 then AdQ(w,Q);//将w放于队列Q之尾 Visited (w)=1 9. endif ndf 11. endwhile 12. end BFS 这里调用了两个函数:AddQ(w,Q)是将w放于队列Q之尾; Delhead(Q)是从队列 Q取第一个顶点,并将其从Q中删除。 定理3.2.1图G的宽度优先搜索算法能够访问G中由v可能到达的所有顶 点。如果记t(v,e)和s(v,e)为算法BFS在任意一个具有v个顶点和E条边的图 G上所花的最大时间和最大空间。则 t(v,E)=6(v+E),s(v,E)=(v)当G由邻接链表表示时 t(v,E)=(v2),s(v,E)=6(v)当G由邻接矩阵表示时 证明略。 由定理2可知,宽度优先搜索算法能够遍历图G的包含ⅴ的连通分支中的所 有顶点。对于不连通的图,可以通过在每个连通分支中选出一个顶点作为起点, 应用宽度搜索算法于每个连通分支,即可遍历该图的所有顶点。 图的宽度优先遍历算法伪代码 BFT(G,v)//图G的宽度优先遍历 for i from 1 to y do Visited(i)=0;/将所有的顶点标记为未被访问 dfo f if Visited (i)==o then BFS (i): endif end bst
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=TU{(u,w)}即可 B A+D□E0 ABCDEFG A+Go B C HO 图G及其邻接链表 HLEDIEFGo 图的宽度优先搜索 图的深度优先搜索 2。图的深度优先搜索 深度优先搜索是沿着顶点的邻点一直搜索下去,直到当前被搜索的顶点不 再有未被访问的邻点为止,此时,从当前辈搜索的顶点原路返回到在它之前被搜 索的访问的顶点,并以此顶点作为当前被搜索顶点。继续这样的过程,直至不能
关于 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 D E F G H 1 2 7 3 5 6 8 4 A B C D E F G H 图的深度优先搜索 1 2 3 4 5 6 7 8 A B C D E F G H 图的宽度优先搜索