第9章 基本图算法 本章内容将包含基本的图形表示法,以及先深搜寻,先广搜寻,拓朴排序,Strongly Connected Components。

Slides:



Advertisements
Similar presentations
算法分析(3) 重要的数据结构.
Advertisements

总结-图 基础知识 基本方法 2017年3月6日 西南石油大学..
動畫與遊戲設計 Data structure and artificial intelligent
Chapter 10 Graphs.
第7章 图论 7.1 图的基本概念 7.6 树 7.2 路与圈 7.7 根树及其应用 7.3 图的矩阵表示 7.8 偶图与匹配
Network Optimization: Models & Algorithms
贪婪算法.
ACM/ICPC暑期集训讲座 二分图匹配 cnhawk
图论算法 ---最大流问题 长沙市雅礼中学 朱 全 民.
Chapter 12 圖形結構 12.1 圖形的一些專有名詞 12.2 圖形資料結構表示法 12.3 圖形追蹤 12.4 擴展樹
Chapter 07 Graph 第七章 图 Prof. Qing Wang.
資料結構與C++程式設計進階 資料結構概論 講師:林業峻 CSIE, NTU 6/ 7, 2010.
第7章 图论基础与应用 PART A 《可视化计算》.
Minimum Spanning Trees
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
7.5 擴張樹 (Spanning Tree) 一個無向相連圖 G 的子圖 G’ 如果可用最少的邊來連接G 的
Chap5 Graph.
第五章 图论 5.6平面图 例 考虑把三座房和三种 设施每种都连接起来的问题, 如图7-64所示,是否有可能使 得这样的连接里不发生交叉?
第8章 圖形結構(Graphs) 8-1 圖形的基本觀念 8-2 圖形的表示法 8-3 圖形的走訪 8-4 擴張樹
Chapter 6 Graph Chang Chi-Chung
第八章 图 图的基本概念 图的存储结构 图的遍历与连通性 最小生成树 最短路径 活动网络.
复习.
The Greedy Method.
演算法方式總覽 The Divide-and-Conquer Strategy (個各擊破)(binary Searching、Quick Sort…. ) The Greedy Method(貪婪演算法) (Prim MST、Kruskal MST、Djikstra's algorithm) Dynamic.
圖論 (Graph Theory) B 電機四 大鳥 B 電機四 酋長 B 電機四 炫大
Graph 2 Michael Tsai 2012/5/1 連載: 學生上課睡覺姿勢大全
Course 9 NP Theory序論 An Introduction to the Theory of NP
101北一女中 資訊選手培訓營 最短路徑 Shortest Path Nan.
Chapter 7 圖形與網路 資料結構導論 - C語言實作.
第16讲 图的矩阵表示, 赋权图与最短路径 主要内容: 1.图的矩阵表示. 2.赋权图与最短路径..
§7.4.2 最小生成树( Minimum Spanning Tree)
XT9-1 circuit data 元件 支路 开始 终止 控制 元 件 元 件 类型 编号 结点 结点 支路 数 值 数 值 V R L
Chapter12 Graphs Definitions Applications Properties
Ch07 圖形與網路 淡江大學 周清江
感謝同學們在加分題建議. 我會好好研讀+反省~
运筹学 图与网络分析 1.
第六节 最小生成树.
数据结构概论 第7章 图 董黎刚 浙江工商大学信电学院 2019年4月8日.
算法设计复习 内容提要: 算法设计思想回顾(递归和分治、动态规划、贪心算法、回溯法、分支限界法) 经典例子讲解 2019/4/9.
算法导论第三次习题课
圖論的介紹 第二組 徐榮德 鄭又齊 陳俊嘉.
第15讲 路与回路, 图的连通性 主要内容: 1.路与回路. 2.图的连通性..
算法导论第三次习题课.
生成树.
图 (三).
第8章 图 8.1 图的基本概念和基本操作 8.2 图的邻接矩阵存储结构 8.3 图的邻接表存储结构 8.4 图的其他存储结构
鄧姚文 資料結構 第八章:圖(Graph) 鄧姚文
本节内容 Lua基本语法.
最短通路问题.
网络模型 Network Modeling Operations Research 运 筹 学
第三章 贪心方法 (Greedy Technique)
第九章 直流暫態 基本電學II 第九章 直流暫態.
Elementary Graph Algorithms
计算机问题求解 – 论题3-8 - 单源最短通路算法
第三章 树 3.1 树的有关定义 给定一个图G=(V,E), 如果它不含任何回路, 我们就叫它是林, 如果G又是连通的, 即这个林只有一个连通支, 就称它是树. 定义3.1.1 一个不含任何回路的连通图称为树, 用T表示. T中的边称为树枝, 度为1的节点称为树叶.
生成树 离散数学─树 南京大学计算机科学与技术系.
Advanced Competitive Programming
Advanced Competitive Programming
第六章 图.
圖形結構 Graph Structure chapter 9 德明科技大學資訊科技系.
第四部分 图论 主要内容 图的基本概念:图、通路和回路、图的连通性、图的矩阵表示 图的可行遍性:欧拉图、哈密顿图、带权图及其应用
第7章 图.
Maximum Flow.
11506: Angry Programmer ★★★★☆ 題組:Contest Set Archive with Online Judge
Graph 1 Michael Tsai 2012/4/24 連載: 學生上課睡覺姿勢大全
算法基础习题课2 助教:刘倩玉.
南昌大学研究生数学建模竞赛教学案例(库)
10801: Lift Hopping ★★★☆☆ 題組:Problem Set Archive with Online Judge
JAVA 程式設計與資料結構 第二十一章 Graph.
Presentation transcript:

第9章 基本图算法 本章内容将包含基本的图形表示法,以及先深搜寻,先广搜寻,拓朴排序,Strongly Connected Components。

图数据 图是目前数据科学研究中最重要的数据类型之一 应用1:朋友圈中的三元闭包与SimRank 应用2:因特网图与Pagerank算法 应用3:微博上的影响力计算与传播模型

图的表示 要表示一个图G={V,E},有两种方法 邻接表 这种方法表示稀疏图比较简洁紧凑 邻接矩阵 这种方法适合稠密图 必须很快判别两个顶点是否相 邻的情况

图的表示:无向图的邻接链表 可由邻接链表表示,将每个点相邻的点集合用一个链表存起来。 2 5 1 3 4 1 2 3 5 4

图的表示:有向图的邻接链表 图可由邻接链表表示,将每个点所指向的点集合存在链表中。 1 2 2 5 3 4 1 3 5 4

图的表示:邻接链表 邻接表中的顶点按照任意次序存储,每个顶点的邻接顶点也是按 照任意次序存储。 权重图:直接将边 (u,v) 的权重值 w(u,v) 存放在 u 的邻接链表 里。 邻接表中的顶点数即图中的节点数|V|,若G是无向图,那么所有 邻接表的长度和为2|E|,若G是有向图,所有邻接表的长度和为 |E|。 无论有向图还是无向图,所需要的存储容量为O(|V|+|E|)。 不足:确定边是否存在需要在顶点的邻接表中搜索所有顶点。

图的表示:邻表矩阵 在图G=(V,E)的邻接矩阵表示法中,我们假定按任意某种方式对其顶 点编号为1, 2,...,|V|,那么G的邻接矩阵为一个|𝑉|×|𝑉|矩阵𝐴= ( 𝑎 𝑖𝑗 ),且满足 𝑎 𝑖𝑗 = 1, 若(𝑖,𝑗)∈𝐸 &0, 若(𝑖,𝑗)∉𝐸 1 2 3 4 5 1 2 3 5 4

图的表示:邻表矩阵 在图G=(V,E)的邻接矩阵表示法中,我们假定按任意某种方式对其顶 点编号为1, 2,...,|V|,那么G的邻接矩阵为一个|𝑉|×|𝑉|矩阵𝐴= ( 𝑎 𝑖𝑗 ),且满足 𝑎 𝑖𝑗 = 1, 若(𝑖,𝑗)∈𝐸 &0, 若(𝑖,𝑗)∉𝐸 1 2 3 4 5 1 2 3 5 4

图的表示:邻表矩阵 一个图的邻接矩阵需要占用Θ( 𝑛 2 )的存储容量,与边数无关。 在无向图的有些应用中,为了节省存储空间可以只存储上三角或者 下三角矩阵; 权重图: 边的权重可以用矩阵元素存储; 对于非加权图用一个二进制位来表示是否有边可以节省存储空间。

广度优先的搜索算法 给定一个图G=(V, E)和源点s, 广度优先搜索算法系统地探寻G所 有的边,从而发现从s可达的所有 的顶点,并计算s到所有这些顶 点的距离(最少边数)。 该算法同时生成一棵根为s且包含所有可达顶点的广度优先树。 对于从s出发的任意节点,广度优先树中从s到v的路径对应G中从 s到v的最短路径。 算法对有向图和无向图都同样有效。

BFS(G,s) for each vertex u in G. V ={s} u. color = WHITE u. d = MAX u BFS(G,s) for each vertex u in G.V ={s} u.color = WHITE u.d = MAX u. π = NIL s.color = GRAY s.d = 0 s. π = NIL Q = NULL ENQUEUE(Q,s) while Q != NULL u = DEQUEUE(Q) for each v in G.Adj[u] if v.color == WHITE v.color = GRAY v.d = u.d + 1 v. π = u ENQUEUE(Q,v) u.color = BLACK 起始点是s。 初始化时,将所有的点涂成白色。 已经发现的点,涂成灰色。 已经展开所有相邻节点的点,涂成黑色。 v.d储存s到v的距离。 v.π储存自s到v的最短路径中,u之前的一 个点。 第一个循环,初始化除s外所有的节点成白色,距离无限大,前一个点为空。 之后初始化s为绿色,距离0,前一个点是空。至此花去O(|V|) 接下来将s放入Q中,之后反复执行Dequeue,直到Q空了为止。 每个Dequeue出来的点u,均将其白色的邻居放入Q中, 并且将他们涂成绿色,距离设定成d[u]+1以及将前一个点设定为u。 处理完所有的邻居之后,就将u涂成红色。 因此每个点被放入Q一次,并且一个点被检验是不是白色的总次数为|E|, 故此部分花费O(|E|+|V|)的时间。

广度优先的搜索算法示例 ∞ r s t u v w x y (a) Q 1 (b) 2 (c) 绿色,已经探索过的。 红色,已经展开过的。 r s t u v w x y (a) Q 1 (b) 2 (c) 绿色,已经探索过的。 红色,已经展开过的。 以s为探索起点。 节点上的数字代表跟s的最短距离。

广度优先的搜索算法示例 r s t u Q 1 2 ∞ (d) t x v 2 2 2 2 1 2 ∞ v w x y r s t u Q 2 ∞ (d) t x v 2 2 2 2 1 2 ∞ v w x y r s t u Q 1 2 3 (e) x v u 2 2 3 2 1 2 ∞ v w x y r s t u Q 1 2 3 (f) v u y 2 3 3 2 1 2 3 v w x y

广度优先的搜索算法示例 r s t u Q 1 2 3 (g) u y 3 3 2 1 2 3 v w x y r s t u Q 1 2 2 3 (g) u y 3 3 2 1 2 3 v w x y r s t u Q 1 2 3 (h) y 3 2 1 2 3 v w x y r s t u Q 1 2 3 (i) empty 2 1 2 3 v w x y

BFS算法的性质 执行过BFS之后,自s可达的点都被涂成黑色。 如v是s可达的点,则d[v]代表s到v的最短路径长。 如v是s可达的点,则(v.π,v)是某条自s到v最短路径的一个边。 v自s可达就是代表存在一个路径,起点是s终点是v。

BFS算法的性质 最短路径距离: δ(s,v)为从源点s到结点v之间所有路径里面最少 的边数。称从源点s到结点v的长度为δ(s,v)的路径为最短路径。 引理 给定有向图或无向图G=(V,E),任意结点s∈V,则对于任意边 (u,v)∈E,δ(s,v)≤δ(s,u)+1。 δ(s,v)可以从δ(s,u)经过(u,v)到v r s t u 1 2 3 (i) 2 1 2 3 v w x y

BFS算法的性质:最短距离 最短路径距离: δ(s,v)为从源点s到结点v之间所有路径里面最少 的边数。称从源点s到结点v的长度为δ(s,v)的路径为最短路径。 引理 给定有向图或无向图G=(V,E),任意结点s∈V,则对于任意边 (u,v)∈E,δ(s,v)≤δ(s,u)+1。 引理 给定有向图或无向图G=(V,E),任意结点v∈V,v.d≥δ(s,v)。 归纳法: 设u.d≥δ(s,u),从u出发找到白色节点v, 则v.d = u.d +1 ≥ δ(s,u) + 1 ≥ δ(s,v)

BFS算法的性质:最短距离 最短路径距离: δ(s,v)为从源点s到结点v之间所有路径里面最少 的边数。称从源点s到结点v的长度为δ(s,v)的路径为最短路径。 引理 给定有向图或无向图G=(V,E),任意结点s∈V,则对于任意边 (u,v)∈E,δ(s,v)≤δ(s,u)+1。 引理 给定有向图或无向图G=(V,E),任意结点v∈V,v.d≥δ(s,v)。 引理 设BFS的队列Q为 <v1,v2,…,vr>,则 vr.d≤v1.d+1,并且对于 i=1,2,…,r-1,vi.d≤vi+1.d+1。即队列中前面的 d 不大于后面的,且 首位差距不超过 1。 归纳法: 1. v1出队,vr.d≤v1.d+1 ≤ v2.d+1 2. vr+1入队,设(u, vr+1)发现vr+1, 此时u已被删除, vr+1.d = u.d+1≤ v1.d+1

BFS算法的性质:最短距离 最短路径距离: δ(s,v)为从源点s到结点v之间所有路径里面最少 的边数。称从源点s到结点v的长度为δ(s,v)的路径为最短路径。 引理 给定有向图或无向图G=(V,E),任意结点s∈V,则对于任意边 (u,v)∈E,δ(s,v)≤δ(s,u)+1。 引理 给定有向图或无向图G=(V,E),任意结点v∈V,v.d≥δ(s,v)。 引理 设BFS的队列Q为 <v1,v2,…,vr>,则 vr.d≤v1.d+1,并且对于 i=1,2,…,r-1,vi.d≤vi+1.d+1。即队列中前面的 d 不大于后面的,且 首位差距不超过 1。 定理 给定有向图或无向图G=(V,E),BFS将发现所有从源点s可到达 的结点v,且对任意 v∈V,v.d = δ (s,v)。s 到 v. π 的最短路径加上 边(v.π,v) 为一条 s 到 v的最短路径。

BFS算法的性质:广度优先树 前驱子图:Gπ=(Vπ,Eπ),其中 Vπ={v∈V| v.π≠NIL}∪{s}, Eπ=(v.π,v): v∈Vπ−{s}。 引理 给定有向图或无向图G=(V,E),BFS过程建造出来的π属性使得 前驱子图 Gπ=(Vπ,Eπ) 称为一棵广度优先树。 1 2 3 r s t u v w x y

Print path算法 PRINT-PATH(G,s,v) if v == s print s elseif v. π == NIL 可在执行过BFS算法的图上印出s到v的最短路径。如无路径也会 印出没有路径的讯息。 PRINT-PATH(G,s,v) if v == s print s elseif v. π == NIL print "no path from" s "to" v "exists" else PRINT-PATH(G,s,v. π) print v 此算法利用BFS建立的表格π,并利用递归的方式, 利用之前提过的BFS性质, (π[v],v)是某一条最短路径上的一边, 找出一条path并且打印出来。

广度优先搜索的应用 垃圾回收:Cheney's algorithm 无权图上计算单源最短路 测试二部图 Ford–Fulkerson最大流算法 Aho–Corasick模式匹配算法

深度优先的搜索算法 Depth-first search(简称DFS,深度优先搜寻)是最简单的图形搜寻 算法之一。同样用于搜寻图G中,所有自点s开始出发,有路径可 以到达的点。 通过“回溯”搜索前驱结点 深度优先搜索会在每个结点盖上两个时间戳:第一个时间戳 v.d 记录v第一次被发现的时间(涂上灰色);第二个时间戳 v.f 记录 完成对 v 的邻接链表扫描的时间(涂上黑色)。 DFS输入G是无向图或有向图,time为全局变量用来计算时间戳

点做完DFS-Visit的时候,涂成黑色。 v.d储存v被发现的时间。 v.f储存v做完DFS-Visit的时间。 v.d<v.f DFS(G) for each vertex u in G.V u.color = WHITE u. π = NIL time = 0 if u.color == WHITE DFS-VISIT(G,u) time++ u.d = time u.color = GRAY for each v in G:Ajd[u] if v.color == WHITE v. π = u DFS-VISIT(G,v) u.color = BLACK u.f = time 初始化时,将所有的点涂成白色。 点初次被发现的时候,涂成灰色。 点做完DFS-Visit的时候,涂成黑色。 v.d储存v被发现的时间。 v.f储存v做完DFS-Visit的时间。 v.d<v.f 第一个循环,初始化除s外所有的节点成白色,距离无限大,前一个点为空。 之后初始化s为绿色,距离0,前一个点是空。至此花去O(|V|) 接下来将s放入Q中,之后反复执行Dequeue,直到Q空了为止。 每个Dequeue出来的点u,均将其白色的邻居放入Q中, 并且将他们涂成绿色,距离设定成d[u]+1以及将前一个点设定为u。 处理完所有的邻居之后,就将u涂成红色。 因此每个点被放入Q一次,并且一个点被检验是不是白色的总次数为|E|, 故此部分花费O(|E|+|V|)的时间。

DFS运作范例 (a) (b) 1/ 1/ 2/ (c) (d) 1/ 2/ 1/ 2/ 3/ 4/ 3/ u v w u v w x y 发现时间 (a) u v w (b) u v w 1/ 1/ 2/ x y z x y z (c) u v w (d) u v w 1/ 2/ 1/ 2/ 飙上浅蓝色的是Tree edge 3/ 4/ 3/ x y z x y z

DFS运作范例 (e) (f) 1/ 2/ 1/ 2/ 4/ 3/ 4/5 3/ (g) (h) 1/ 2/ 1/ 2/7 4/5 3/6 u v w (f) u v w 1/ 2/ 1/ 2/ B B 4/ 3/ 4/5 3/ x y z x y z (g) u v w (h) u v w 1/ 2/ 1/ 2/7 虚线+B的是代表Back edge B B 4/5 3/6 4/5 3/6 x y z x y z

DFS运作范例 (i) (j) 1/ 2/7 1/8 2/7 4/5 3/6 4/5 3/6 (k) (l) 1/8 2/7 9/ 1/8 u v w (j) u v w 1/ 2/7 1/8 2/7 B F B F 4/5 3/6 4/5 3/6 x y z x y z (k) u v w (l) u v w 1/8 2/7 9/ 1/8 2/7 9/ B 虚线加上F的是Forward edge 虚线加上C的是Cross edge F B C F 4/5 3/6 4/5 3/6 x y z x y z

DFS运作范例 (m) (n) 1/8 2/7 9/ 1/8 2/7 9/ 4/5 3/6 10/ 4/5 3/6 10/ (o) (o) u v w (n) u v w 1/8 2/7 9/ 1/8 2/7 9/ B C F B C F B 4/5 3/6 10/ 4/5 3/6 10/ x y z x y z (o) u v w (o) u v w 1/8 2/7 9/ 1/8 2/7 9/12 B C B C F F B B 4/5 3/6 10/11 4/5 3/6 10/11 x y z x y z

深度优先搜索的性质 DFS算法的时间复杂度为O(|V|+|E|)。 执行过DFS算法之后,所有的点都是黑色的。 t z v u y DFS算法的时间复杂度为O(|V|+|E|)。 执行过DFS算法之后,所有的点都是黑色的。 深度优先搜索的前驱子图:Gπ=(V,Eπ) 其中 Eπ={(v.π, v)| v∈V and v.π≠NIL} Gπ形成一个深度优先森林,也就是一个元素为深度优先树的集合。 如u到v之间在深度优先森林中有一路径,则称u是v的祖先,称v 是u的后代。 w x 时间复杂度由每个点执行过一次DFS-Visit而所有的DFS-Visit正巧把所有边都浏览过一次。

深度优先搜索的性质 定理(括号化定理) 在对有向图或无向图 G=(V,E) 进行DFS时,对任 意结点 u 和 v:以下三种情况只有一种成立: 1. [u.d,u.f]与[v.d,v.f]完全分离:深度优先森林中,u与v互相不为 对方后代 2. [u.d,u.f]完全包含于[v.d,v.f]:深度优先森林中,u是v的后代 3. 与2相反的情况 s t z v u y w x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ( s (z (y (x x) y) (w w) z) s) (t (v v) (u u) t)

深度优先搜索的性质 定理 在对有向图或无向图 G=(V,E) 进行DFS时,对任意结点 u 和 v:以下三种情况只有一种成立: 1. [u.d,u.f]与[v.d,v.f]完全分离:深度优先森林中,u与v互相不为 对方后代 2. [u.d,u.f]完全包含于[v.d,v.f]:深度优先森林中,u是v的后代 3. 与2相反的情况 推论 在深度优先森林中,v是u的真后代当且仅当 u.d<v.d<v.f<u.f。 白色路径定理:在G的深度优先森林中,v是u的后代当且仅当发 现u时,存在u到v的由全部由白色结点构成的路径。

边的分类 树边(tree): 若初次发现v时是由(u,v),即π[v]=u,则称此边为树 边。 后向边(backward): 若v是u的祖先,则此边称作后向边。 前向边(forward): 若v是u的后代,且(u,v)不是树边,则此边称作 前向。 横向边(cross): 不属于前三类的边均称为横向边。 s z y x w v u t B C F 3/6 2/9 1/10 4/5 7/8 12/13 y z s x w v B C 14/15 u 11/16 t F 下页有范例,将一个图进行DFS之后,所建成的Depth-first forest。

边的分类 v 为白色:(u,v) 为树边 v 为灰色:(u,v) 为后向边 v 为黑色:(u,v) 为前向边或横向边 3/6 2/9 定理 对无向图G进行DFS时,每条边要么是树边,要么是后向边。 有向图中的横向边在无向图中成为树边或后向边。 s z y x w v u t B C F 3/6 2/9 1/10 4/5 7/8 12/13 y z s x w v B C 14/15 u 11/16 t F 下页有范例,将一个图进行DFS之后,所建成的Depth-first forest。

深度优先搜索应用1:拓扑排序 有向无环图DAG (Directed acyclic graph) G=(V,E): Topological sort(拓朴排序)是一种对点集V的排序,满足若(u,v) ∈ E 则在排序中u必须排在v之前。 常用于决定排程。 上面的图是一个DAG。 下面则是此DAG对应的一个Topological sort。 上图是一个穿衣服的优先级,穿内裤(undershorts)之后才能穿长裤(pants), 穿袜子(socks)之后才能穿鞋子(shoes)等等。

一个表示穿衣服先后顺序的图 经拓朴排序后,可依此顺序穿上所有衣物。 内裤 袜子 长裤 鞋子 皮带 衬衫 领带 夹克 手表 袜子 内裤 长裤

拓扑排序算法 TOPOLOGICAL-SORT(G) call DFS(G) to compute finishing times v.f for each vertex v as each vertex is finished, insert it onto the front of a linked list return the linked list of vertex 利用DFS算法,计算出每一个点u的结束时间v.f。 当一个点执行完毕DFS-Visit时,将该点放入一个公用链表前端。 最后此链表存放的顺序即为一拓扑排序。

拓扑排序算法示例 每个点旁的数字代表Discover time/Finish Time 以上为公用链表在执行完DFS之后的顺序。 内裤 袜子 长裤 鞋子 皮带 衬衫 领带 夹克 手表 11/16 12/15 6/7 1/8 2/5 3/4 17/18 13/14 9/10 每个点旁的数字代表Discover time/Finish Time 袜子 内裤 长裤 鞋子 手表 衬衫 皮带 领带 夹克 11/16 12/15 6/7 1/8 3/4 13/14 17/18 9/10 2/5 以上为公用链表在执行完DFS之后的顺序。

拓扑排序算法性质 引理 有向图G是无环的当且仅当对其DFS不产生后向边。 定理 TOPOLOGICAL-SORT算法生成的排序是拓扑排序 有后向边:有环 无后向边:假设有环,白色路径定理证明必须产生后向边 定理 TOPOLOGICAL-SORT算法生成的排序是拓扑排序 需证明:若(u,v)有边,则v.f <=u.f

深度优先搜索应用2:分解强连通分量 对一个有向图G=(V,E),一个强连通分量(Strongly Connected Component) C为一个最大结点集合 C⊂V,对于该集合中任意两点 可以互相到达。。

Strongly connected components算法 STRONGLY-CONNECTED-COMPONENTS(G) { call DFS(G) to compute finishing times u.f for each vertex u compute G^T call DFS(G^T), but in the main loop of DFS, consider the vertices in order of decreasing u.f output the vertices of each tree in the DFS forest formed in line 3 as a separate strongly connected component }

Strongly connected components算法 对所有点u运行DFS(G),计算结束时间u.f。 计算出转置图GT,即点集合与G相同,而边连接方向相反的 图。 运行DFS(GT),但在DFS主循环中,选择点的顺序是先挑取u.f值 较大的点u。(即以u.f递减顺序选取。) 在DFS(GT)的深度优先森林中,每一个树均是一个强连通分 量。

G: GT: 收缩分量图 13/14 11/16 12/15 3/4 1/10 2/7 8/9 5/6 a b c d e f g h abe cd h fg 13/14 11/16 12/15 3/4 1/10 2/7 8/9 5/6 a b c d e f g h GT:

强连通分量算法性质 引理 C和C′为G的两个不同的强连通分量,u,v∈C, u′, v′∈C′。 如果G包含u到u′的路径,则不可能包含 v′到 v的路径。 引理 定义d(U)和f(U)为U中所有结点最早和最晚发现时间。C和 C′为G的两个不同的强连通分量,如果存在边 (u,v)∈E, u∈C, v∈C′, 则 f(C)>f(C′)。 推论 C和C′为G的两个不同的强连通分量,如果存在边 (u,v)∈ET, u∈C, v∈C′, 则 f(C)<f(C′)。 定理 Strongly connected components算法能正确计算有向图 G的所有强连通分量

强连通分量算法性质 引理 C和C′为G的两个不同的强连通分量,u,v∈C, u′, v′∈C′。 如果G包含u到u′的路径,则不可能包含 v′到v的路径。 反证法:若有v′到v的路径,则C与C′将变为一个连通分量

强连通分量算法性质 引理 C和C′为G的两个不同的强连通分量,u,v∈C, u′, v′∈C′。 如果G包含u到u′的路径,则不可能包含 v′到 v的路径。 引理 定义d(U)和f(U)为U中所有结点最早和最晚发现时间。C和 C′为G的两个不同的强连通分量,如果存在边 (u,v)∈E, u∈C, v∈C′, 则 f(C)>f(C′)。 1. 若d(C)<d(C′),设x是C中第一个被发现的节点。x.f比C与C′中任 何节点都要晚 2. 若d(C)>d(C′),设y是C′中第一个被发现的节点,y无法到达C (否则C与C′互通)。即y.f时,C中点仍为白色

强连通分量算法性质 引理 C和C′为G的两个不同的强连通分量,u,v∈C, u′, v′∈C′。 如果G包含u到u′的路径,则不可能包含 v′到 v的路径。 引理 定义d(U)和f(U)为U中所有结点最早和最晚发现时间。C和 C′为G的两个不同的强连通分量,如果存在边 (u,v)∈E, u∈C, v∈C′, 则 f(C)>f(C′)。 推论 C和C′为G的两个不同的强连通分量,如果存在边 (u,v)∈ET, u∈C, v∈C′, 则 f(C)<f(C′)。 关键性质:第二次DFS不会访问结束时间晚于自身的连通分量

强连通分量算法性质 引理 C和C′为G的两个不同的强连通分量,u,v∈C, u′, v′∈C′。如果G包 含u到u′的路径,则不可能包含 v′到 v的路径。 引理 定义d(U)和f(U)为U中所有结点最早和最晚发现时间。C和C′为G的 两个不同的强连通分量,如果存在边 (u,v)∈E, u∈C, v∈C′, 则 f(C)>f(C′)。 推论 C和C′为G的两个不同的强连通分量,如果存在边 (u,v)∈ET, u∈C, v∈C′, 则 f(C)<f(C′)。 定理 Strongly connected components算法能正确计算有向图G的所 有强连通分量 关键:第二次DFS新产生一棵深度优先树时,该连通分量所有节点 都是白色的

深度优先搜索的其他应用 垃圾回收:Cheney's algorithm 无权图上计算单源最短路 测试二部图 Ford–Fulkerson最大流算法 Aho–Corasick模式匹配算法

作业 作业:22.2-8,22.3-11,22.5-3 无习题课 无上机 思考题:22-2

最小生成树问题

最小生成树 a b c d e f g h 3 5 1 9 4 7 2 考虑加权连同无向图G=(V,E) 我们希望找到一个无环子集 T∈E,既能将所有结点连接起来,又 具有最小的权重 由于T无环,T必然是一棵树,称为图G的生成树,求取该生成树的 问题为最小生成树问题。 a b c d e f g h 3 5 1 9 4 7 2

最小生成树的形成 在每一时刻生长最小生成树的一条边,并维护如下循环不变式: 在每次循环之前,边集合A是某棵最小生成树的一个子集。 这样不破坏循环不变式的的边(u,v)称为集合A的 安全边。

最小生成树的性质 无向图G=(V,E)的一个 切割(S, V-S)是集合V的一个划分。 如果一条边 (u,v)∈E的一个端点位于S,另一个端点位于V-S,则称 该边横跨该切割。 如果集合A中不存在横跨该切割的边,则称该切割尊重集合A。 在横跨一个切割的所有边中,权重最小的边称为轻量级边。 b 3 4 f a 5 2 1 1 e 5 7 2 c 9 d 3 g 4 h 切割({a,b,c}, {d,e,f,g,h}),轻量级边(b,f);设集合A为蓝色边集合,则切割尊重A

最小生成树的性质 定理 设G=(V,E)是一个在边E上定义了实数权重函数w的连通无向 图。A为边集E的子集,且在G的某棵最小生成树中。(S,V-S)为尊 重集合A的任意一个切割。(u,v)是横跨该切割的一条轻量级边。 则边(u,v)对于集合A是安全的。 假设(u.v)不在最小生成树T中,因u v必然在树中相连,故(u,v)与树中两者 的连线构成环。至少有两边横跨该切割,一边为(u,v),设另一边为(x,y)。 考虑新的一棵生成树:T'=T-{(x,y)}+{(u,v)},因(u,v)是轻量级边,故w(T')不 大于w(T),即T'也是最小生成树。显然(x,y)不在A中,于是A与(u,v)都在T'中, 即(u,v)对于集合A是安全的。 b 3 4 f (b,f)加入MST,形成环 去掉(b,e),重新形成MST 得出w(b,f)<=w(b,e) a 5 2 1 1 e 5 7 2 c 9 d 3 g 4 h

最小生成树的性质 推论 设G=(V,E)是一个在边E上定义了实数权重函w的连通无向 图。A为E的子集,且在G的某棵最小生成树中。设 C=(VC,EC)为森 林 GA=(V,A)中的一棵树。如果边(u,v)是连接C 和 GA中其他树的一 条轻量级边,则该边对于A是安全的。

Prim算法 集合A中的边总是构成一棵树,每次选择一条轻量级边加入A。 Prim算法属于贪心算法。 所有不在A中的结点存放于以key为权值的最小优先队列Q中。对 每一个结点v,v.key保存连接v和树中结点的所有边中最小边的权 重。

最小生成树 边带权值 找到无向图G=(V,E)的 最小生成树T Prim方法: 点集V初始为空,每次选择 距离V最近的点加入 时间复杂度O(ElogV)

最小生成树 找到图G=(V,E)的 最小生成树T。 Prim方法: 点集V初始为空,每次选择 距离V最近的点加入

最小生成树 找到图G=(V,E)的 最小生成树T。 Prim方法: 点集V初始为空,每次选择 距离V最近的点加入

最小生成树 找到图G=(V,E)的 最小生成树T。 Prim方法: 点集V初始为空,每次选择 距离V最近的点加入

最小生成树 找到图G=(V,E)的 最小生成树T。 Prim方法: 点集V初始为空,每次选择 距离V最近的点加入

最小生成树 找到图G=(V,E)的 最小生成树T。 Prim方法: 点集V初始为空,每次选择 距离V最近的点加入

最小生成树 找到图G=(V,E)的 最小生成树T。 Prim方法: 点集V初始为空,每次选择 距离V最近的点加入

堆与优先队列 利用二叉最小堆构建优先队列 斐波拉契堆 EXTRACT-MIN: O(log n) DECREASE-KEY: O(log n) INSERTION: O(log n) FINDMIN: O(1) 斐波拉契堆 DECREASE-KEY: O(1)

Prim算法 建造堆的时间为 O(V);EXTRACT-MIN的时间为 O(lg V),遍历结点 循环次数为O(V) 修改key用到的DECREASE-KEY在二叉最小堆的时间为 O(lg V),在 斐波那契堆的时间为 O(1),遍历边循环次数为O(E) 故算法MST-PRIM的运行时间为 O(V + V lgV + E lgV)=O(E lgV)(最小 二叉堆实现)或者 O(E + V lgV)(斐波那契堆实现)。

Kruskal算法 在所有连接森林中两棵不同树的边里面,找到权重最小的加入最 小生成树。Kruskal算法属于贪心算法。 FIND-SET(u)用来返回包含u的集合的代表元素,UNION过程对两棵 树进行合并,判断FIND-SET(u)==FIND-SET(v)可知两点是否在同一 集合。

并查集 维护k个不相交的集合{S1, S2, …, Sk},每个集合用它的一个元素来 代表(representative) 操作 MAKE-SET(x): 建立一个新的集合,其唯一元素为x UNION(x, y): 将包含x和y的两个集合合并为一个集合 FIND-SET(x): 返回包含x的唯一集合

最小生成树 Kruskal方法: 每次选择两个端点不在同 一连通分量的边加入 时间复杂度O(ElogE)

最小生成树 Kruskal方法: 每次选择两个端点不在同 一连通分量的边加入

最小生成树 Kruskal方法: 每次选择两个端点不在同 一连通分量的边加入

最小生成树 Kruskal方法: 每次选择两个端点不在同 一连通分量的边加入

最小生成树 Kruskal方法: 每次选择两个端点不在同 一连通分量的边加入

最小生成树 Kruskal方法: 每次选择两个端点不在同 一连通分量的边加入

最小生成树 Kruskal方法: 每次选择两个端点不在同 一连通分量的边加入

Kruskal算法 共有O(E)个FIND-SET和UNION操作,|V|个MAKE-SET操作 总运行时间为 O(|E| lg|V| + |V| lg|V|) = O(|E| lg|E|)(对于连通 图:|E|≥|V|−1) 注意到 |E|<|V|2,运行时间为O(|E| lg|V|)。

单源最短路径问题

单源最短路径 在最短路径问题中,给定一个带权重的有向图G=(V,E)和权重函数 𝜔: 𝐸→𝑹 ,该函数将每条边映射到实数值的权重。 图中一条路径𝑝=< 𝑣 0 , 𝑣 1 ,…, 𝑣 𝑘 >的权重 w(p) 是构成该路径的所 有边的权重之和: 𝜔 𝑝 = 𝑖=1 𝑘 𝑤(𝑣 𝑖−1 , 𝑣 𝑖 ) 从结点u到结点 v的 最短路径权重: 𝛿 𝑢,𝑣 = min 𝜔 𝑝 | 𝑝:𝑢→𝑣 , ∞ 如果存在𝑢到𝑣的路径 否则 最短路径的最优子结构性质:两个结点之间的一条最短路径包含 着其他的最短路径。

最短路径问题的几个变体 单源最短路径问题:给定一个图G=(V,E),找到从给定 源点 s∈V到 每个结点 v∈V的最短路径。 单目的地最短路径问题:找到从每个结点 v 到给定目的地结点 t 的最短路径。 单结点对最短路径问题:找到给定结点 u 到给定结点 v 的最短路 径。 所有结点对最短路径问题:对于每对结点 u 和 v,找到从结点 u 到结点 v 的最短路径。

最短路径的最优子结构 引理(最短路径的子路径也是最短路径)给定带权重的有向图 G=(V,E)和权重函数 ω: E→R 。设 p=<v0, v1, .., vk>为从结点 v0到结点 vk的一条最短路径,并且对于任意i和j,0≤i≤j≤k,设pij=<vi, vi+1, .., vj>为路径p中从结点 vi 到结点 vj 的子路径。那么 pij是从结点 vi 到 结点 vj的一条最短路径。 v0 vk vi vj

最短路径:负权重 负权重的边 如果图G不包含从源点s可到达的权重为负的环路, 则对所有结点,最短路径权重都有精确定义;如果从结点s到结 点v的某条路经上存在权重为负的环路,我们定义δ(s,v)=−∞。 负权重对最短路的影响:

最短路径:环路 环路 最短路径不能包含权重为负值的环路。 最短路径同样不能包含权重为正值的环路。 将环路删除会获得一条更短的路径 最短路径不需包含权重为0的环路。 不失一般性,我们假设找到的路径上都没有环路。

最短路径的表示 前驱子图 Gπ=(Vπ,Eπ),其中 点集Vπ={v∈V| v.π≠NIL}∪{s},边集 Vπ={(v.π,v)∈E| v∈Vπ/{s}}。 算法终止时,Gπ是一棵“最短路径树”:有根结点的树,包括了从 源结点s到每个可以从s到达的结点的一条最短路径。 最短路径树是否唯一?

松弛操作 对每个结点维护一个属性 v.d,记录从源结点 s 到结点 v 的最短路 径权重的上界。称为 最短路径估计。 使用 Θ(V)运行时间的算法 对最短路径估计和前驱结点初始化: 对一条边(u,v)的 松弛操作:

Bellman-Ford算法 Bellman-Ford算法解决的是一般情况下的单源最短路径问题。该 算法返回TRUE当且仅当输入图不包含可以从源结点到达的权重为 负值的环路。 每次For循环做一次松弛操作 运行时间:O(VE)

Bellman-Ford算法 松弛顺序: (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)

Bellman-Ford算法 推论 设G=(V,E)为一个带权重的源结点为s的有向图,其权重函数 为 ω: E→R。图G不包含从 s 可以到达的权重为负值的环路,则对 于所有结点 v,存在一条从 s 到 v 的路径当且仅当 BELLMAN-FRD 算法终止时有 v.d<∞。 定理(Bellman-Ford算法的正确性)设BELLMAN-FORD算法运行在 一带权重的源结点为 s 的有向图 G=(V,E) 上,该图的权重函数为 ω: E→R。如果图G不包含从 s 可以到达的权重为负值的环路,则 算法返回 TRUE,且对于所有结点 v,前驱子图 Gπ是一棵根为 s 的 最短路径树。如果G包含一条从 s 可以到达的权重为负值的环 路,则算法返回FALSE。

有向无环图中的单源最短路径问题 根据结点的拓扑排序次序来对带权重的有向无环图 G=(V,E) 进行边的松 弛操作,便可以在 Θ(V+E) 时间内计算出从单个源结点到所有结点之间 的最短路径。每次对一个结点进行处理时,我们对从该结点发出的所有 边进行松弛操作。 算法的总运行时间为Θ(V+E)。 定理 如果带权重无环路的有向图G=(V,E)有一个源结点s,则在算法DAG- SHORTEST-PATHS终止时,对于所有结点v,我们有 v.d=δ(s,v),且前驱子 图 Gπ 是一棵最短路径树。

算法运行过程

Dijkstra 算法 Dijkstra算法解决的是带权重的有向图上单源最短路径问题,该算 法要求所有边的权重都为非负值。Dijkstra 算法在运行过程中维 持的关键信息是一组结点集合S:从源结点 s 到该集合中每个结 点之间的最短路径已经被找到。

算法运行过程

Dijkstra算法 定理(Dijkstra算法的正确性)Dijkstra算法运行在带权重的有向图 G=(V,E)时,如果所有权重为非负值,则在算法终止时,对于所有 结点 u,有 u.d=δ(s,u)。 可通过循环不变式证明:4~8行的while语句每次循环开始前,对于每个结 点 v∈S,有 v.d=δ(s,v)。 > Q中最小结点所有连接到S的路径已被探测过,且 pi已经标记为最短路径上的前驱结点。 推论 如果在带权重的有向图G=(V,E)上运行Dijkstra算法,其中的权 重皆为非负值,源点为s,则在算法终止时,前驱子图 Gπ是一棵 根结点为 s 的最短路径树。 Dijkstra算法的时间复杂度同最短路径的 Prim 算法,依赖于最小 优先队列的实现: 数组实现:O(V2+E)=O(V2) 最小二叉堆实现:O((V+E)lgV)=O(ElgV) 斐波那契堆实现:O(VlgV+E)

所有节点对的最短路径问题

所有结点对的最短路径问题 假定输入图的节点编号为1, 2, …, |V|, 输入图可以看成一个n*n的 矩阵W=(wij): 算法输出也可以看成一个矩阵:D=(dij),其中dij为节点i到节点j的 一条最短路径的权重(长度) 如果要打印出任意两个节点的最短路径,则还需要输出前驱节点 矩阵Π=(πij),其中 πij 在 i=j 或 i到j不存在路径时为 NIL,其他情况 为 i 到 j 最短路径上j的前驱结点。

所有结点对的最短路径问题 对每个结点 i,定义图G对于结点 i 的 前驱子图为 Gπ,i=(Vπ,i, Eπ,i), 其中Vπ,i={j∈V| πi,j≠NIL}∪{i}, Eπ,i={(πij,j)| j∈Vπ,i−{i}}如果 Gπ,i是一棵最 短路径树,如下算法将打印 i 到 j 的一条最短路径。

最短路径与矩阵乘法 递归解: 定义 𝑙 𝑖𝑗 (𝑚) 为 i 到 j 的至多包含 m 条边的所有路径中最小的 权重,则 最终,最短路径由以下公式给出

最短路径的矩阵相乘算法 时间复杂度:Θ(𝑛3)

算法运行过程

Floyd-Warshall算法 假设可以有负权重的边,但是不能存在负权重的环。 递归解:

Floyd-Warshall算法原理 考虑中间点取值集合为{1,…,k}。 如k不在i到j最短路径上,则中间点仅可能为{1,…,k-1},故此时: d(k)(i,j)=d(k-1)(i,j)。 如k在i到j最短路径上,则将i到k及k到j两段分开看,这两个路径 必然不可能有中间点为k,否则依照无负循环的假定,i到k或k到j 不是最短路径,违背最短路径的性质。故此时: d(k)(i,j)=d(k-1)(i,k)+d(k-1)(k,j)。 中间点仅有 {1,…,k-1} i k j 中间点仅有 {1,…,k-1}

Floyd-Warshall算法 算法描述 标记最短路径

All-Pairs Shortest Paths Floyd-Warshall算法示例 1 3 -4 8 7 5 2 6 2 4 1 4 3 -5 All-Pairs Shortest Paths

All-Pairs Shortest Paths Floyd-Warshall算法示例 All-Pairs Shortest Paths

All-Pairs Shortest Paths Floyd-Warshall算法示例 All-Pairs Shortest Paths

All-Pairs Shortest Paths Floyd-Warshall算法示例 All-Pairs Shortest Paths

All-Pairs Shortest Paths Floyd-Warshall算法示例 All-Pairs Shortest Paths

All-Pairs Shortest Paths Floyd-Warshall算法示例 All-Pairs Shortest Paths

All-Pairs Shortest Paths Floyd-Warshall算法示例 All-Pairs Shortest Paths

用于稀疏图的 Johnson 算法 Johnson算法使用的技术成为 重新赋予权重: 如果图G的所有边权重为非负值,对每个结点运行一次 Dijkstra 算 法得到最短路径。使用斐波那契堆时的算法运行时间为 V2lgV+VE。 如果图G包含权重为负的边,但没有负值环路,那么只有计算出 一组非负权重值,然后使用同样的方法。 > 新赋予的权重应满足 下面两个性质: > 1. 对所有结点对,其最短路径不能因权重的变 化而变化。 > 2. 对所有边,新权重 w′(u,v)非负。

用于稀疏图的 Johnson 算法 定义新的权重 定义 w′(u,v)=w(u,v)+h(u)−h(v),则路径权重 w′(p)=∑ki=1w′(vi−1,vi)=w(p)+h(v0)−h(vk)。即对于同样的结点对, 各路径权重增加一个常数,其大小关系不发生变化。 定义图 G’ = (V’,E’),其中 V′=V∪s(s 为新结点),E′=E∪(s,v): v∈V。 对所有结点 v∈V′,定义 h(v)=δ(s,v),则根据三角不等式 h(v)≤h(u)+w(u,v),即新的权重 w′(u,v)=w(u,v)+h(u)−h(v)≥0。

算法描述 时间复杂度: O(V2lgV+VE)

Johnson’s algorithm算法示例 4 3 7 8 -5 1 -4 2 6 All-Pairs Shortest Paths

Johnson’s algorithm算法示例 加入一个点s,以及自s拉一条weight为0的边到每一点。 4 3 7 8 s -5 1 -4 2 6 All-Pairs Shortest Paths

Johnson’s algorithm算法示例 -1 执行Bellman-Ford算法,得到自s出发每一点的最短距离。 4 3 7 8 s -5 -5 1 -4 2 -4 6 All-Pairs Shortest Paths

Johnson’s algorithm算法示例 -1 做完reweighting 4 10 13 -5 2 -4 2 All-Pairs Shortest Paths

Johnson’s algorithm算法示例 2/1 红线部分是Shortest-paths tree。 点的数字a/b代表自出发点(绿色点)出发,到达该点的最短路径(Reweighting后的图/原图)。 4 10 13 0/0 2/-3 2 0/-4 2/0 2 All-Pairs Shortest Paths

Johnson’s algorithm算法示例 0/0 4 10 13 2/3 0/-4 2 2/-1 0/1 2 All-Pairs Shortest Paths

Johnson’s algorithm算法示例 0/4 4 10 13 2/7 0/0 2 2/3 0/5 2 All-Pairs Shortest Paths

Johnson’s algorithm算法示例 0/-1 4 10 13 2/2 0/-5 2 2/-2 0/0 2 All-Pairs Shortest Paths

Johnson’s algorithm算法示例 2/5 4 10 13 4/8 2/1 2 0/0 2/6 2 All-Pairs Shortest Paths

Johnson’s algorithm复杂度分析 执行一次Bellman-Ford:O(|V||E|)。 执行|V|次Dijkstra: 使用Fibonacci heap,总计O(|V|2log|V|+|V||E|) 。 使用Binary heap,总计O(|V||E|log|V|)。 当|E|足够小,比Warshall-Floyd快。 All-Pairs Shortest Paths

作业 作业:24.1-3,24.3-8 习题课:大作业指导1 上机:实现Bellman-Ford算法与Dijkstra算法 思考题:阅读书上斐波拉契堆与并查集内容,并给出基于斐波拉 契堆得PRIM算法与基于并查集的KRUSKAL算法的实现与复杂度分 析。