第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算法的实现与复杂度分 析。