PowerPoint 演示文稿

Transcription

1 第十讲图 郑渤龙

2 10.1 图 : 基本概念

3 本节概要 本节较为简单, 主要为后续的图的学习奠定基础 我们将在无向 / 有向图上定义一系列概念, 并讨论如何在计算机中表示它们

4 要点回顾 无向图 无向图由一对集合 (V,E) 定义 V 是节点元素的集合 E 是 V 中元素构成的二元组 (u,v) 的集合 其中,u 和 v 是不同的节点 ; 如果 (u,v) 在集合 E 中, 则 (v,u) 也在集合 E 中, 我们称节点 u 与节点 v 之间存在一条边,E 为边的集合 节点也可被称为顶点 我们称 V 为图的顶点集或节点集,E 为边集

5 举例 右图为无向图, 包含了 5 个顶点 v 1, v 2,, v 5 和 5 条边 e 1, e 2,, e 5

6 要点回顾 有向图 有向图由一对集合 (V,E) 定义 V 是节点元素的集合 E 是 V 中节点构成的二元组 (u,v) 的集合 我们称从 u 到 v 存在一条 ( 有向 ) 边 节点也可被称为顶点 我们称 V 为图的顶点集或节点集,E 为边集 一条 ( 有向 ) 边 (u, v) 是节点 u 的出边, 节点 v 的入边 相应地,v 是 u 的外邻节点,u 是 v 的内邻节点

7 举例 右图为有向图 (V,E), 包含了 5 个顶点 v 1, v 2,, v 5 和 7 条边 e 1, e 2,, e 7 注意每条边都有一个方向 例如, 边 e 6, 是节点 v 5 的出边, 节点 v 4 的入边

8 要点回顾 度 在无向图中, 顶点 u 的度为 u 的边数 在有向图中, 顶点 u 的出度为 u 的出边数, 入度为 u 的入边数 举例 左图中,v 5 的度为 2; 右图中,v 3 的出度为 2, 入度为 1

9 图的存储 接下来, 我们讨论两种常用的存储图的方法 : 邻接表和邻接矩阵 在这两种情形下, 我们均用唯一的下标 1,2,, V 来表示 V 中的每一个顶点

10 邻接表 - 无向图 V 中的每一个顶点 u 均与一个链表相关联, 该链表枚举了连接到 u 的所有顶点 举例 存储空间为 O( V + E )

11 邻接表 - 有向图 V 中的每一个顶点 u 均与一个链表相关联, 该链表枚举了所有存在从 u 到 v 的边的顶点 v(v V) 举例 存储空间为 O( V + E )

12 邻接矩阵 - 无向图 一个 V V 的矩阵 A, 若 (u,v) E, 则 A[u,v] = 1; 否则, A[u,v] = 0 举例 A 肯定为对称矩阵 存储空间为 O( V 2 )

13 思考 如何存储 A 才能够在常数时间内判断任意顶点 u 和顶点 v (u V,v V) 之间是否存在边?

14 邻接矩阵 - 有向图 定义与无向图情况下相同 举例 A 可能不是对称矩阵 存储空间为 O( V 2 )

15 10.2 广度优先搜索

16 本节概要 本节我们讨论一个简单的算法, 称为广度优先搜索 一次遍历图中所有的节点和边 我们的讨论将集中于有向图, 因为对于无向图的拓展是明确的 为了让讨论更有趣, 我们将把它放在一个具体的问题中 : 具有单位权重的单源最短路径 (SSSP)

17 定义 : 最短路径 假设 G = (V, E) 是一个有向图 G 中的一条路径是边 (v 1, v 2 ), (v 2, v 3 ),, (v l, v l+1 ) 的序列, 称整数 l (l 1) 为路径的长度 该路径被称为从 v 1 到 v l+1 有时, 也将路径记为 v 1 v 2 v l+1 给定两个顶点 u,v V, 从 u 到 v 的最短路径是从 u 到 v 的所有路径中长度最小的路径 如果从 u 到 v 没有路径, 则称节点 v 是从节点 u 不可达的

18 举例 从节点 a 到节点 g 有许多路径 : a b c d g( 长度 :4) a b c e d g( 长度 :5) a d g( 长度 :2) 最后一个为最短路径 该例子中, 最短路径是唯一的 注意, 节点 h 是从节点 a 不可达的

19 定义 具有单位权重的单源最短路径 Single Source Shortest Path (SSSP) 假设 G = (V, E) 是一个有向图,s 是 V 中的一个顶点 SSSP 问题的目标是为每个其他顶点 t(t V \ {s}) 找到从 s 到 t 的最短路径, 除非 t 是从 s 不可达的

20 BFS 接下来, 我们将描述在 O( V + E ) 时间内求解该问题的广度优先搜索 (BFS) 算法, 这显然是最优的 ( 因为在最坏的情况下, 任何算法至少必须看到每个顶点和每条边一次 ) 乍一看, 这可能令人惊讶, 因为所有最短路径的总长度都可能达到 Ω( V 2 ), 即使 E = O( V ) 那么, 在最坏的情况下, 算法不应该需要 Ω( V 2 ) 时间来输出所有的最短路径吗? 有趣的是, 答案是否定的 正如将看到的,BFS 将 BFS 树中的所有最短路径紧凑编码, 仅使用 O( V ) 空间, 并且可以在 O( V + E ) 时间内输出

21 BFS 首先, 将图中所有的顶点着色为白色, 创建一个空的 BFS 树 T 创建一个队列 Q 将源顶点 s 插入 Q, 并将其着色为灰色 ( 意味着顶点在队列中 ) 使 s 成为 T 的根节点

22 举例 假设源顶点为 a Q = (a).

23 BFS 重复以下操作直到 Q 为空 : 1. 从队列 Q 中删除第一个顶点 v 2. 对于 v 的每一个外邻节点 u 仍为白色的 : 2.1 节点 u 入队列 Q, 并将节点 u 着色为灰色 2.2 在 BFS 树 T 中, 使 u 为 v 的孩子节点 3. 节点 v 着色为黑色 ( 意味着节点 v 已经完成 ) 正如我们将从运行实例中看到的,BFS 如同病毒传播

24 运行实例 节点 a 出队之后 Q = (b,d)

25 运行实例 节点 b 出队之后 Q = (d,c)

26 运行实例 节点 d 出队之后 Q = (c,g)

27 运行实例 节点 c 出队之后 Q = (g,e) 注意, 节点 d 不会再次入队, 因为它是黑色的

28 运行实例 节点 g 出队之后 Q = (e,f,i)

29 运行实例 节点 e,f,i 出队之后 Q = () 这是 BFS 的结束 注意 h 仍为白色 - 我们可以得出结论,h 是从节点 a 不可达的

30 运行实例 最短路径在哪里? 从 a 到任何节点的最短路径, 比如说节点 x, 就是 BFS 树中节点 a 到节点 x 的路径!

31 时间分析 当顶点 v 出队时, 我们花费 O(1+d + (v)) 时间 (d + (v) 为节点 v 的出度 ) 显然, 每个顶点最多进入队列一次 因此,BFS 总的运行时间为 : O(σ v V (1 + d + (v))) = O( V + E )

32 10.3 深度优先搜索 郑渤龙

33 本节概要 我们已经学习了广度优先搜索 (BFS) 今天, 我们将讨论它的 姐妹版本 : 深度优先搜索 (DFS) 算法 我们的讨论将再一次集中于有向图, 因为对于无向图的拓展是明确的 DFS 是一个出人意料的强大算法, 它巧妙地解决了几个经典的问题 在本节课中, 我们将看到这样一个问题 检测输入图是否包含环路

34 定义 : 路径与环路 假设 G = (V, E) 是一个有向图 回顾 : G 中的一条路径是边 (v 1, v 2 ), (v 2, v 3 ),, (v l, v l+1 ) 的序列 ( 整数 l 1) 我们也可将路径记为 v 1 v 2 v l+1 我们现在定义 : 一条路径 v 1 v 2 v l+1, 如果 v l+1 =v 1, 则称该路径为环路

35 环路 : d g f e d. 另一环路 : d g i f e d. 举例

36 定义 有向无环图 / 循环图 如果一个有向图不包含环路, 我们称其为有向无环图 Directed Acyclic Graph(DAG) 否则,G 为循环图 举例 : 循环图 有向无环图

37 环路检测问题 设 G = (V,E) 是一个有向图 确定它是否是 DAG

38 DFS 接下来, 我们将描述在 O( V + E ) 时间内求解该问题的深度优先搜索 (DFS) 算法, 这显然是最优的 ( 因为在最坏的情况下, 任何算法至少必须看到每个顶点和每条边一次 ) 同 BFS 一样,DFS 算法也输出一棵树 称为 DFS 树 此树包含关于输入图的重要信息, 这些信息使我们决定输入图是否为 DAG

39 DFS 首先, 将图中所有的顶点着色为白色, 创建一个空的 DFS 树 T 创建一个栈 S 选择任意顶点 v 将 v 入栈 S, 并将 v 着色为灰色 ( 意味着顶点 在栈中 ) 使 v 成为 T 的根节点

40 举例 假设我们从节点 a 开始 : S = (a)

41 DFS 重复以下操作直到 S 为空 : 1. 假设 v 目前是栈 S 的栈顶元素 ( 不要从 S 中移除 v) 2. 节点 v 是否仍有白色的外邻节点? 2.1 如果有 : 假设其为 u 将 u 压入栈 S, 并将 u 着色为灰色 在 DFS 树 T 中, 使 u 为 v 的孩子节点 2.2 如果没有, 将 v 从栈 S 中弹出, 并将 v 着色为黑色 ( 意味着节点 v 已经完成 ) 如果仍然存在白色顶点, 则从任意白色顶点 v 重新开始来重复上述步骤, 创建一棵新的根节点为 v 的 DFS 树 正如我们接下来看到的,DFS 如同 浏览网页一次一点击

42 运行实例 栈顶元素 :a, 拥有白色的外邻节点 b,d 假设我们先访问 b 将节点 b 压入栈 S S = (a,b)

43 运行实例 节点 c 入栈 S 之后 S = (a,b,c)

44 运行实例 现在 c 是栈顶元素 它有白色的外邻节点 d 和 e 假设我们先访问 d 将节点 d 压入栈 S S = (a,b,c,d)

45 运行实例 节点 g 入栈 S 之后 S = (a,b,c,d,g)

46 运行实例 假设我们先访问 g 的白色外邻节点 f 将节点 f 压入栈 S S = (a,b,c,d,g,f)

47 运行实例 节点 e 入栈 S 之后 S = (a,b,c,d,g,f,e)

48 运行实例 节点 e 没有白色的外邻节点 所以将其从 S 中弹出, 并将其着色为黑色 相似地,f 没有白色的外邻节点 将其也从 S 中弹出, 并将其着色为黑色 S = (a,b,c,d,g)

49 运行实例 现在,g 再一次为栈顶元素 它仍有一个白色的外邻节点 i 所以, 将节点 i 压入栈 S S = (a,b,c,d,g,i)

50 运行实例 节点 i,g,d,c,b,a 出栈之后 S = ()

51 运行实例 现在仍然有一个白色节点顶点 h 所以我们从 h 开始执行另一个 DFS S = (h)

52 运行实例 节点 h 出栈 结束 S = () 注意, 我们创建了一个 DFS 森林, 它包含两棵 DFS 树

53 时间分析 DFS 可以有效的实现, 如下 : 以邻接表形式存储 G 对于每一个顶点 v, 记得其外邻顶点来探索下一个 栈操作 :O( V + E ) 使用一个数组来存储所有顶点的颜色 因此,DFS 总的运行时间为 :O( V + E )

54 DFS 回想一下, 我们之前说过 DFS 树 ( 也许是 DFS 森林 ) 编码了关于输入图的有价值的信息, 接下来, 我们将使这一点具体化, 并解决边检测问题

55 定义 边分类 假设我们已经构建了一个 DFS 森林 T 假设 (u,v) 是图 G 中的一条边 ( 记得边是有向的 - 从 u 到 v) 可分为 : 前向边 : 在 T 中的 DFS 树,u 是 v 的固有祖先 后向边 : 在 T 中的 DFS 树,u 是 v 的后代 横叉边 : 以上两者均不适用

56 举例 前向边 :(a,b),(a,d),(b,c),(c,d),(c,e),(d,g),(g,f),(g,i),(f,e) 后向边 :(e,d) 横叉边 :(i,f),(h,d),(h,g)

57 边分类 在获得 DFS 森林 T 之后, 我们可以在常数时间内确定每一条边 (u,v) 的类型 只需要通过记住每个顶点何时进入和离开栈来略微增强 DFS 算法

58 定义 略微增强 DFS 保持一个计数器 c, 其初始值为 0 每次在栈上执行压入或弹出操作时, 我们将 c 增加 1 对于每一个顶点 v, 定义 : 它的发现时间 d-tm(v) 是 v 被压入栈之后 c 的值 它的结束时间 f-tm(v) 是 v 从栈中弹出之后 c 的值 定义 l(v) = [d-tm(v),f-tm(v)] 很显然, 通过在 DFS 的运行时间上增加额外的时间开销 O( V ) 就能够获得所有 v 的 l(v)(v V)

59 l(a) = [1,16] l(b) = [2,15] l(c) = [3,14] l(d) = [4,13] l(g) = [5,12] l(f) = [6,9] l(e) = [7,8] l(i) = [10,11] l(h) = [17,18] 举例

60 定义 括号定理 定理 : 下列所有都为真 : 在 T 的 DFS 树中, 如果 u 是 v 的固有祖先, 那么 l(u) 包含 l(v) 在 T 的 DFS 树中, 如果 u 是 v 的固有后代, 那么 l(u) 被 l(v) 包含 否则,l(u) 和 l(v) 是不相交的 证明 : 直接从栈的先进后出属性得出

61 定义 环路定理 定理 : 假设 T 为任意 DFS 森林 当且仅当存在关于 T 的后向边时, G 包含环路 证明 : 充分性 是显而易见的 证明 必要性 是更为重要的, 稍后将进行

62 定义 环路检测了解了环路定理之后, 我们知道, 在获得一个 DFS 森林 T 之后, 可以很容易地检测 G 中是否有环路 : 对于每一条边 (u,v), 在 O(1) 时间内确定它是否有后向边 如果没有发现后向边, 确定 G 为 DAG; 否则,G 至少有一个环路 仅需要额外的时间 :O( E ) 我们现在可以得出结论, 环路检测问题能够在 O( V + E ) 时间内解决

63 环路定理 环路定理仍有待证明 我们首先证明另外一个重要的定理, 然后能够推论出环路定理

64 定义 白色路径定理 定理 : 假设 u 是图 G 中的顶点 考虑在 DFS 算法中 u 节点被压入栈中的时刻 然后, 在 DFS 森林中顶点 v 成为 u 的固有后裔当且仅当以下条件为真 : 我们能够通过仅走白色顶点从节点 u 走到节点 v 证明 : 留作练习 换言之, 定理阐明了只有在发现了所有仍然可以发现的顶点之后, 在 u 处的搜索才会停住

65 举例 考虑我们之前的例子中, 节点 g 刚被压入栈中的时刻 S= (a,b,c,d,g) 我们能够看到节点 g 通过仅走白色节点可以到达节点 f,e,i 因此, 在 DFS 森林中节点 f,e,i 均为 g 的固有后裔,g 没有其他的后裔

66 证明 证明环路定理的 必要性 我们现在将证明如果 G 包含环路, 那么在 DFS 森林中必然存在一条后向边 假设环路为 v 1 v 2 v l v 1 设 v i (i [1, l]) 为环路中第一个压入栈的顶点 然后, 由白色路径定理可得, 在 DFS 森林中, 环路中的所有其他顶点均为顶点 v i 的固有后裔 这意味着在环路中指向 v i 的边为后向边 这样我们就完成了环路定理的全部证明

67 10.4 DAG 上的拓扑排序

68 本节概要 如上所述, 深度优先搜索 (DFS) 算法出人意料的强大 事实上, 我们已经使用它来有效地检测有向图中是否包含任何环路 在本节课中, 我们将使用它来解决另一个经典问题 线性时间内的拓扑排序 该算法非常巧妙, 简单到足以使本节非常简短

69 定义 拓扑次序 设 G = (V,E) 是一个有向无环图 (DAG) G 的拓扑次序是满足以下条件的 V 中顶点的次序 : 对于任意边 (u,v), 在次序中必须保持 u 先于 v

70 举例 下面是两个可能的拓扑次序 : h,a,b,c,d,g,i,f,e. a,h,b,c,d,g,i,f,e. 不是拓扑次序 : a,h,d,b,c,g,i,f,e( 由于边 (c,d))

71 注意 有向循环图没有拓扑次序 ( 思考 : 为什么?) 每一个 DAG 都有一个拓扑次序 这将从我们随后的讨论中推论得出

72 定义 拓扑排序问题 设 G = (V,E) 是一个有向无环图 (DAG) 拓扑排序的目标是生成 G 的拓扑次序 算法非常简单 : 创建一个空的链表 L 在 G 上运行 DFS 每当顶点 v 变为黑色 ( 即从栈中弹出 ), 将其追加到 L 输出 L 的倒序总的运行时间为 :O( V + E ).

73 举例 1 假设我们从 a 节点运行 DFS 以下是顶点变黑的一个可能的次序 : e,f,i,g,d,c,b,a,h 因此, 我们输出 h,a,b,c,d,g,i,f,e 作为拓扑次序

74 举例 2 假设我们从 d 节点运行 DFS 然后从节点 h 重新开始, 然后从节点 a 开始 以下是顶点变黑的一个可能的次序 : e,f,i,g,d,h,c,b,a. 因此, 我们输出 a,b,c,h,d,g,i,f,e 作为拓扑次序

75 证明 我们现在证明算法的正确性 取任意边 (u,v) 我们将展示节点 u 在节点 v 之后变黑, 证明即完成 考虑 u 压入栈的时刻 我们认为 v 目前不在栈中 假设 v 在栈中 因为必须有一个从底向上的链接栈中顶点的路径, 因此我们知道有一条从 v 到 u 的路径 然后, 加上边 (u,v) 就形成了环路, 这与 G 是一个 DAG 相矛盾 现在继续思考 : v 目前是黑色的 : 很明显,u 将在 v 之后变黑 v 是白色的 : 然后利用 DFS 的白色路径定理, 我们知道在 DFS 森林中,v 将会变成 u 的固有后裔 因此,u 将在 v 之后变黑

76 证明 算法的正确性也证明了 : 每一个 DAG 都有一个拓扑次序