【Algorithms 4】算法（第4版）学习笔记 16 - 4.2 有向图

前言

本篇主要内容包括：有向图 API、有向图搜索、拓扑排序 以及 强连通分量。

强烈建议在学习本篇之前先行学习或回顾上一篇无向图的内容。

参考目录

• B站 普林斯顿大学《Algorithms》视频课
  （请自行搜索。主要以该视频课顺序来进行笔记整理，课程讲述的教授本人是该书原版作者之一 Robert Sedgewick。）
• 微信读书《算法（第4版）》
  （本文主要内容来自《4.2 有向图》）
• 官方网站
  （有书本配套的内容以及代码）

学习笔记

注1：下面引用内容如无注明出处，均是书中摘录。
注2：所有 demo 演示均为视频 PPT demo 截图。
注3：如果 PPT 截图中没有翻译，会在下面进行汉化翻译，因为内容比较多，本文不再一一说明。

1：介绍

1.1：有向图简介

书中有向图图解：

1.2：应用举例

1.3：相关问题

问题	描述
s → t path	从 s 到 t 的路径是否存在？
shortest s → t path	从 s 到 t 的最短路径是什么？
directed cycle	图中是否存在有向环？
topological sort （拓扑排序）	能否将有向图绘制为所有边都指向上的拓扑排序形式？
strong connectivity （强连通性）	图中任意两点之间是否存在方向任意的有向路径？
transitive closure （传递闭包）	对于哪些顶点 v 和 w，存在从 v 到 w 的有向路径？
PageRank （页面排名算法）	网页的重要性是什么？

2：有向图 API

2.1：有向图表示

2.1.1：邻接表数组 Adjacency-list

2.1.2：Java 实现：邻接表数组

（可参考对比无向图 Graph 实现）

edu.princeton.cs.algs4.Digraph

edu.princeton.cs.algs4.Digraph#Digraph

edu.princeton.cs.algs4.Digraph#addEdge

edu.princeton.cs.algs4.Digraph#adj

2.2：实际应用

**在实际应用中：**我们采用邻接表的方式来表示图结构。

• 许多算法都是基于从顶点 v 出发逐个遍历其指向的所有其他顶点。
• 实际应用中的有向图数据结构往往具有稀疏特性。（虽然顶点数量可能非常庞大，但平均每个顶点所连接的边数相对较少。）

2.3：小结

注：边的数组 list of edges 以及 邻接矩阵 adjacency matrix 没有详细说明，可以参考无向图 #2.4 相关内容。

3：有向图搜索

3.1：可达性

3.2：深度优先搜索 depth-first search

与无向图方法相同：

• 每一个无向图都可以视为一个有向图（每条边都有两个方向）。
• 深度优先搜索（DFS）是一个应用于有向图的算法。

3.2.1：demo 演示

访问一个顶点 v 时：

• 将顶点 v 标记为已访问状态。
• 递归地访问从顶点 v 出发的所有未标记的顶点。

初始状态：

同样地，v 代表顶点，marked[] 保存标记状态，edgeTo[] 保存边信息。

访问第一个顶点 0：

依次检查 与顶点 0 相邻且由此出发所指向的 顶点：分别是 5、1。

检查顶点 5：

检查与顶点 5 相邻且由此出发所指向的顶点：4。

检查顶点 4：

检查与顶点 4 相邻且由此出发所指向的顶点：分别是 3、2。

检查顶点 3：

检查与顶点 3 相邻且由此出发所指向的顶点：分别是 5、2。

检查顶点 5，已经被标记。

检查顶点 2：

检查与顶点 2 相邻且由此出发所指向的顶点：分别是 0、3。

检查顶点 0，已经被标记。

检查顶点 3，已经被标记。

完成顶点 2 的搜索：

返回顶点 3，完成顶点 3 的搜索：

返回顶点 4 继续搜索：

检查顶点 2，已经被标记。

完成顶点 4 的搜索：

返回顶点 5，完成顶点 5 的搜索：

返回顶点 0 继续搜索：

搜索顶点 1，没有需要搜索的相邻节点，完成顶点 1 的搜索：

完成顶点 0 的搜索：

完成了所有顶点 0 可达的顶点搜索：

3.2.2：Java 实现

（与无向图完全相同，只是替换了方法名称以及对象类型）

edu.princeton.cs.algs4.DirectedDFS

edu.princeton.cs.algs4.DirectedDFS#dfs

edu.princeton.cs.algs4.DirectedDFS#marked

3.3：可达性应用

3.3.1：程序控制流分析

每个程序都可以表示为一个有向图。

• 顶点（Vertex）：表示一组连续执行的指令集（基本块）。
• 边（Edge）：表示程序控制流中的跳转关系。

死代码消除。
寻找并移除不可达（永远不会被执行）的代码。

无限循环检测。
判断程序是否存在无法到达退出点的情况。

3.3.2：标记-清除垃圾回收

每种数据结构都可以表示为一个有向图。

• 顶点（Vertex）：表示对象（Object）。
• 边（Edge）：表示引用（Reference）。

根对象（Roots）。
指那些可以直接被程序访问的对象（例如，栈中的对象）。

可达对象（Reachable objects）。
指那些通过程序可以从根对象间接访问到的对象（从某个根开始，沿着一系列指针链进行跟踪）。

标记-清除算法（由麦卡锡于 1960 年提出）：

• 标记阶段（Mark）：标记所有能够被程序访问到的对象。
• 清除阶段（Sweep）：若对象未被标记，则判定其为垃圾对象（从而将它加入到空闲列表中释放）。

内存成本：
该算法对每个对象需要额外占用 1 个标记位，并且还需要使用深度优先搜索栈（这会增加一定的内存开销）。

标记-清除算法 是学习 JVM 的时候一个很重要的算法。

3.4：小结

深度优先搜索（DFS）能够直接解决一些简单的有向图问题。

• 可达性（判断图中两个顶点间是否存在可达路径。）
• 路径查找（找到一条从起点到终点的路径。）
• 拓扑排序（对有向无环图中的顶点进行排序，使得对于任意指向顶点 u 的边，顶点 u 都在顶点 v 之前。）
• 有向循环检测（判断有向图中是否存在环路。）

深度优先搜索是解决复杂有向图问题的基础方法。

• 二元可满足性问题求解（在逻辑运算中判断给定的布尔公式是否能通过真值赋值使其结果为真的问题。）
• 有向欧拉路径（在有向图中寻找一条经过每条边恰好一次的路径。）
• 强连通分量（识别出有向图中互相可达的所有顶点集合，这些集合内的顶点两两之间都存在可达路径。）

3.5：广度优先搜索 breadth-first search

同样的方法也适用于无向图。

• 每个无向图都可以看作是有向图（每条边都是双向的）。
• 广度优先搜索（BFS）是一种有向图算法。

**命题：**在有向图中，广度优先搜索（BFS）可以在时间复杂度为 O(E+V) 的时间内，计算出从顶点 s 到其他所有顶点的最短路径（即最少边数的路径）。

3.5.1：demo 演示

重复执行以下操作，直到队列为空：

• 从队列中移除顶点 v。
• 将从顶点 v 出发的所有未标记的顶点加入队列，并将它们标记为已访问。

初始状态：

将顶点 0 添加到队列：

queue 代表队列，v 代表顶点，edgeTo[] 保存边信息，distTo[] 保存路径长度信息。

顶点 0 出队：

需要依次检查 与顶点 0 相邻且由此出发所指向的 顶点：分别是 2、1。

检查顶点 2：

顶点 2 没有被标记，添加到队列中。

检查顶点 1：

顶点 1 没有被标记，添加到队列中。

完成顶点 0 搜索：

顶点 2 出队：

依次检查与顶点 2 相邻且由此出发所指向的顶点：4。

检查顶点 4：

顶点 4 没有被标记，添加到队列中。

完成顶点 2 搜索：

顶点 1 出队：

依次检查与顶点 1 相邻且由此出发所指向的顶点：2。

检查顶点 2，已经被标记。

完成顶点 1 搜索：

顶点 4 出队：

依次检查与顶点 4 相邻且由此出发所指向的顶点：3。

检查顶点 3：

顶点 3 没有被标记，添加到队列中。

完成顶点 4 搜索：

顶点 3 出队：

依次检查与顶点 3 相邻且由此出发所指向的顶点：分别是 5、2。

检查顶点 5：

顶点 5 没有被标记，添加到队列中。

检查顶点 2，已经被标记。

完成顶点 3 搜索：

顶点 5 出队：

依次检查与顶点 5 相邻且由此出发所指向的顶点：0。

检查顶点 0，已经被标记。

完成顶点 5 搜索：

完成所有搜索：

3.5.2：多源最短路径

多源最短路径
给定一个有向图和一组起点顶点，找出从该组任意起点顶点到图中其他所有顶点的最短路径。

Q. 如何实现多源最短路径算法？
A. 可以使用广度优先搜索（BFS），但是在初始化时，将所有源顶点都入队列。 (具体做法是首先将所有指定的源顶点放入队列中作为搜索的起点，然后按照广度优先搜索的规则依次遍历图中的其他顶点，逐步计算出从各个源顶点到图中所有其他顶点的最短路径。)

3.6：BFS 应用

3.6.1：网络爬虫

**目标：**从某一指定的根网页（例如www.princeton.edu）出发爬取整个网站。

**解决方案：**使用 广度优先搜索（BFS) 算法隐式构建的有向图 进行爬取。

步骤如下：

1. 将根网页设为源节点 s。
2. 维护一个用于存储待探索网站的 队列（Queue）。
3. 维护一个记录已发现网站的 集合（SET），用于去重。
4. 从队列中取出下一个网站，并检查其指向的所有链接所对应的网站（前提是这些网站尚未被添加进队列或集合中）。
   • 如果某个链接指向的网站还未被发现，则将其加入队列。
   • 同时将新发现的网站添加到已发现网站的集合中，确保不会重复抓取同一网站。

Q. 为什么不用 DFS 实现？

（利用通义千问总结一下） 网络爬虫的实现通常首选广度优先搜索（BFS）而不是深度优先搜索（DFS）的原因在于以下几个关键因素：

1. 短路径优先：
   • BFS 保证爬虫首先遍历到的是离起始网页最近的网页，因此对于寻找最短路径的情况非常有利。在网络爬虫场景下，如果目的是快速抓取到尽可能接近种子 URL 的网页，BFS 能够找到从起始网页到任意页面的最短跳转路径。
2. 更全面的初始层级覆盖：
   • BFS 逐层遍历，能更均匀地抓取同一层级上的所有链接，这对于初步建立网站的拓扑结构、索引和导航结构的初步构建十分有效，能够迅速获取到一个网站的第一层链接资源。
3. 避免过深探索：
   • DFS 可能会导致爬虫陷入深层次且可能不是特别重要的链接结构中，而忽视了其他重要性较高的较浅层次页面。尤其是在没有合理剪枝策略的情况下，DFS 可能导致爬虫在某一分支上耗费过多资源，而忽略了其他可能更重要的部分。
4. 减少重复爬取：
   • BFS 通过维护一个已经访问过的网页集合（通常是哈希表），能够有效地避免爬虫反复进入同一个网页的多个入口，减少了不必要的重复抓取。
5. 反映网页的重要性：
   • 在某些基于链接流行度的评价体系中，入链数量往往代表了一定程度上的网页重要性。BFS 倾向于先抓取那些有更多的入链（即被更多网页链接到的网页），这在一定程度上符合优先抓取重要网页的需求。

综上所述，网络爬虫采用 BFS 作为基础遍历策略，能够更好地满足实际应用中的需求，如高效地获取范围广泛的链接、平衡地抓取不同层次的内容以及减少不必要开销等。当然，具体实现时根据任务的具体要求，有时候也会结合 DFS 或其他策略来优化爬虫的行为。

3.6.2：Java 实现

4：拓扑排序 topological sort

4.1：定义

4.2：demo 演示

• 执行深度优先搜索
• 按逆后序返回顶点

初始状态：

访问第一个顶点 0：

依次检查相邻顶点：1、2、5。

检查顶点 1：

检查相邻顶点：4。

检查顶点 4：

顶点 4 没有出度，完成搜索并加入堆栈（后序 postorder）：

返回顶点 1，完成搜索并加入后序：

返回顶点 0 继续搜索。

检查顶点 2：

顶点 2 没有出度，完成搜索并加入后序：

返回顶点 0 继续搜索。

检查顶点 5：

检查顶点 2，已经被标记。

顶点 5 完成搜索并加入后序：

完成顶点 0 的搜索并加入后序：

按顺序检查其他未标记顶点。

顶点 1、2 已经被标记，检查顶点 3：

依次检查相邻顶点：2、4、5、6。

检查顶点 2，已经被标记。

检查顶点 4，已经被标记。

检查顶点 5，已经被标记。

检查顶点 6：

检查相邻顶点：0、4。

检查顶点 0，已经被标记。

检查顶点 4，已经被标记。

完成顶点 6 的搜索并加入后序：

完成顶点 3 的搜索并加入后序：

完成所有顶点搜索。

4.3：Java 实现：DFS 排序

edu.princeton.cs.algs4.DepthFirstOrder

edu.princeton.cs.algs4.DepthFirstOrder#dfs

edu.princeton.cs.algs4.DepthFirstOrder#reversePost

4.4：DAG 拓扑排序证明

对应书本命题 F：

图4.2.11 有向无环图的逆后序是拓扑排序

4.5：有向循环检测

**命题：**一个有向图存在拓扑排序当且仅当它不含任何有向环。

证明：

• 若存在有向环，则无法构造拓扑排序。
• 若不存在有向环，则基于深度优先搜索（DFS）的算法能够找到一个拓扑排序。

5：强连通分量 strong components

5.1：定义

（PPT 和书本内容一致，直接把书本的内容贴出来）

定义：

性质：

5.2：无向图连通分量 vs. 有向图强连通分量

5.3：强连通分量算法简史

1960年代：核心运筹学问题。

• 广泛研究，出现了一些实用算法。
• 其复杂性尚未被充分理解。

1972年：线性时间的深度优先搜索（DFS）算法（由 Tarjan 提出）。

• 经典算法，在算法领域占有重要地位。
• 算法难度级别相当于“Algs4 进阶版”。
• 显示了深度优先搜索在广泛应用场景下的重要性和实用性。

1980年代：简易两遍线性时间算法（Kosaraju-Sharir 算法）。

• 教授课程时忘记带讲义，为了授课临时开发出该算法！
• 后来发现该算法实际上在 1972 年的俄罗斯科学文献中已有记载。

1990年代：更多简易的线性时间算法出现。

• Gabow 改进了原有的运筹学算法。
• Cheriyan 和 Mehlhorn 设计了一种单遍线性时间算法，这是 LEDA 项目所需的关键技术。

Prof. Sedgewick 总结：

So this story indicates, even from fundamental problems in graph processing, there’s algorithms out there still waiting to be discovered. And this algorithm is a good example of that.

因此，这个故事表明，即使在图形处理的基本问题中，仍然存在有待发现的算法。而上述提到的算法恰好是一个很好的例子。

5.4：Kosaraju-Sharir 算法

5.4.1：直觉

**反向图：**原图 G 中的强连通分量与反向图 G^R 中的相同。

**核 DAG（Kernel DAG）：**将每个强连通分量收缩成单个顶点。

思路：

• 在核 DAG 中计算拓扑排序（采用逆后序）。
• 以逆拓扑顺序考虑顶点，并运行深度优先搜索（DFS）。

书中的描述：

5.4.2：demo 演示

阶段1： 在 G^R 图中计算逆后序排列。
阶段2： 在 G 图中运行深度优先搜索，按照 G^R 图中的逆后序排列顺序访问未标记的顶点。

初始状态：

5.4.2.1：第一阶段

在反向图 G^R 图中计算逆后序排列。

反向图 G^R：

逆后序排列演示在前面拓扑排序刚说完，就不一一截图了，大致搜索过程如下（* 粗体 代表搜索完成放入后序）：

0 —— 6 —— 8

8 —— 6 —— 7

7 —— 6

6 —— 0 —— 2 —— 4 —— 11 —— 9 —— 12 —— 10

10 —— 12

12 —— 9

9 —— 11

11 —— 4 —— 5 —— 3

3 —— 5

5 —— 4

4 —— 2

2 —— 0

1

检查确保所有顶点都已经被标记。

第一阶段结束后的结果：

5.4.2.2：第二阶段

在 G 图中运行深度优先搜索，按照 G^R 图中的逆后序排列顺序访问未标记的顶点。

原始图 G：

以第一阶段结果 1 0 2 4 5 3 11 9 12 10 6 7 8 进行搜索。

搜索顶点 1：

没有其他顶点，强连通分量编号标记为 0，完成搜索。

同理，搜索其他分量，大致过程如下：

0 —— 5 —— 4 —— 3 —— 2

顶点 0、2、3、4、5 为强连通分量，标记为 1。

11 —— 12 —— 9 —— 10

顶点 9、10、11、12 为强连通分量，标记为 2。

6 —— 8

顶点 6、8 为强连通分量，标记为 3。

7

顶点 7 为强连通分量，标记为 4。

完成所有的连通分量查询：

5.4.3：过程小结

Kosaraju-Sharir 算法：计算强连通分量的简单（但神秘）算法。

5.4.4：证明

证明具有一定的数学复杂性，但编码实现非常简单。

5.4.5：Java 实现

edu.princeton.cs.algs4.KosarajuSharirSCC

edu.princeton.cs.algs4.KosarajuSharirSCC#dfs

edu.princeton.cs.algs4.KosarajuSharirSCC#stronglyConnected

6：有向图处理小结

（完）