图的搜索⚓︎

约 1318 个字 36 行代码预计阅读时间 5 分钟总阅读量次

课程: Network Optimization (15.082J/6.855J/ESD.78J)
来源: MIT OpenCourseWare, Fall 2010
主题: 图搜索算法、正确性证明、拓扑排序

1. 概述 (Overview)⚓︎

主要介绍搜索图的不同方法及其理论基础，这是网络优化中大多数算法的基础。

通用搜索方法 (Generic Approach)
广度优先搜索 (Breadth First Search, BFS)
深度优先搜索 (Depth First Search, DFS)
程序验证 (Program Verification)
支持网络搜索的数据结构
拓扑排序 (Topological Sort)

2. 有向图搜索 (Searching a Directed Graph)⚓︎

问题定义

输入: 有向网络 \(G\)，起始节点 \(s\)。
输出: 集合 \(S = \{j: \text{在 } G \text{ 中存在从 } s \text{ 到 } j \text{ 的有向路径}\}\)。即从 \(s\) 可达的所有节点。
附加输出: 对于每个 \(j \in S \setminus \{s\}\)，记录前驱节点 \(pred(j)\)。

核心概念

标记节点 (Marked Nodes): 节点要么被标记，要么未被标记。初始只有 \(s\) 被标记。被标记意味着从 \(s\) 可达。
容许弧 (Admissible Arcs): 弧 \((i, j)\) 是容许的，如果节点 \(i\) 已标记且节点 \(j\) 未标记。
扫描弧 (Scanning Arcs): 遍历选定节点的弧列表，使用 CurrentArc 跟踪，直到找到容许弧或列表扫描完毕。

通用搜索算法 (Algorithm Search)

ALGORITHM SEARCH
初始化:
    取消标记 N 中的所有节点; 标记节点 s;
    pred(s) = 0; 
    LIST = {s}

while LIST ≠ ø do
    从 LIST 中选择一个节点 i;
    if 节点 i 关联到一条容许弧 (i, j) then
        标记节点 j;
        pred(j) := i;
        将节点 j 添加到 LIST 末尾;
    else
        从 LIST 中删除节点 i;

3. 搜索策略：BFS 与 DFS⚓︎

通用算法中 LIST 的操作方式决定了搜索策略。

3.1 广度优先搜索 (BFS)⚓︎

规则: 选择的节点是 LIST 中的第一个节点 (FIFO 队列)。
性质: BFS 树是最短路径树 (Shortest Path Tree)。
- 即：树中从 \(s\) 到 \(j\) 的路径包含最少数量的弧。
- 节点按照距离 \(s\) 的递增顺序被标记。
不变式 (Invariant): 如果 \(d(i) < d(j)\)，则 \(i\) 在 \(j\) 之前被标记。

3.2 深度优先搜索 (DFS)⚓︎

规则: 选择的节点是 LIST 中的最后一个节点 (LIFO 栈)。
性质:
- 每个诱导子树 (Induced Subtree) 包含连续标记的节点。
- 后代节点按顺序访问。
- 若每个节点至少有一条出弧，DFS 遇到的第一条不可容许弧确定了一个有向环。

4. 算法分析与正确性证明 (Algorithm Analysis)⚓︎

4.1 证明方法⚓︎

分块 (Chunks): 将算法 subdivided。
不变式 (Invariants): 算法运行过程中始终为真的属性。
变化量 (Things that change): 每次重新进入循环时单调增加的函数（用于证明终止性）。

4.2 搜索算法的不变式 (Invariants)⚓︎

当控制程序在 while 循环开始时，以下性质成立：

任何被标记的节点都是从 \(s\) 可达的。
LIST 上的所有节点都被标记。
如果一个被标记的节点 \(j\) 不在 LIST 上，则其出弧 \(A(j)\) 已被完全扫描。

4.3 正确性证明 (Proof of Correctness)⚓︎

终止条件: LIST = \(\emptyset\)。
集合定义: \(S\) = 标记节点，\(T\) = 未标记节点。
推导:
- 不存在从 \(S\) 指向 \(T\) 的弧（否则根据不变式 2，\(j\) 会被标记）。
- 根据不变式 1，\(S\) 中所有节点从 \(s\) 可达。
- 根据不变式 3，\(S\) 的所有出弧已扫描。
- 结论: \(T\) 中没有节点是从 \(s\) 可达的。

4.4 割集定理 (Cutset Theorem)⚓︎

推论: 当且仅当存在节点集 \(N\) 的一个划分 \((S, T)\)，使得没有弧从 \(S\) 指向 \(T\) 时，不存在从 \(s\) 到 \(t\) 的有向路径。

4.5 运行时间分析 (Running Time)⚓︎

初始化: \(O(n)\) (取消标记所有节点)。
While 循环:
- 每次循环 \(O(1)\) (除弧扫描外)。
- 最多 \(2n\) 次迭代 (每个节点最多被添加一次、删除一次)。
- 总时间 \(O(n)\)。
弧扫描:
- 每条弧扫描 \(O(1)\)。
- 共 \(m\) 条弧。
- 总时间 \(O(m)\)。
总复杂度: \(O(n + m)\)

5. 拓扑排序 (Topological Sort) 详解⚓︎

拓扑排序是针对有向无环图 (DAG, Directed Acyclic Graph) 的一种节点排序方式。

核心性质: 如果图 \(G\) 没有有向环，则可以重新标记节点，使得对于图中的每一条弧 \((i, j)\)，都满足 \(i < j\)。
前提条件: 图中不能存在有向环。如果存在环，则无法进行拓扑排序。

5.2 基本推论 (Corollaries)⚓︎

在进行拓扑排序前，了解以下关于无环图的性质非常重要：

存在源点与汇点: 如果 \(G\) 没有有向环，则图中至少存在一个没有出弧的节点（汇点），也至少存在一个没有入弧的节点（源点）。
DFS 与环: 如果每个节点至少有一条出弧，深度优先搜索 (DFS) 遇到的第一条“不可容许弧” (inadmissible arc) 必然确定了一个有向环。

5.3 算法步骤⚓︎

下面的拓扑排序算法基于入度 (Indegree) 的概念，通常被称为 Kahn 算法。

ALGORITHM TOPOLOGICAL_SORT

1. 初始化 (INITIALIZE):
   - 对所有节点 i ∈ N，设置 indegree(i) := 0
   - 对所有弧 (i, j) ∈ A，执行 indegree(j) := indegree(j) + 1
   - 创建列表 LIST := ∅
   - 对所有节点 i ∈ N，如果 indegree(i) = 0，则将 i 加入 LIST
   - 设置计数器 next := 0

2. 循环处理 (while LIST ≠ ∅):
   - 从 LIST 中选择一个节点 i 并删除
   - next := next + 1
   - 记录顺序 order(i) := next  (此时节点 i 被“标记”)
   - 遍历 i 的所有出弧 (i, j) ∈ A(i):
       - indegree(j) := indegree(j) – 1
       - 如果 indegree(j) = 0，则将 j 加入 LIST

3. 结果检查:
   - 如果 next < n (节点总数):
       则网络包含有向环 (无法完全拓扑排序)
   - 否则:
       网络是无环的，order 即为拓扑顺序

5.5 核心逻辑⚓︎

寻找入口: 首先找到所有入度为 0 的节点（即没有前驱依赖的节点），放入待处理列表 LIST。
逐步剥离: 每次从 LIST 取出一个节点，将其放入排序结果，然后将其所有后继节点的入度减 1。
触发新节点: 如果某个后继节点的入度变为 0，说明其所有前驱节点都已处理完毕，将其加入 LIST。
环检测: 如果处理结束后，仍有节点未被标记（next < n），说明剩余节点构成了环（因为环中的节点入度永远无法减为 0）。

5.6. 算法正确性证明 (不变式 Invariant)⚓︎

理解算法为何能检测环，关键在于理解课程中提到的不变式 (Invariant)。

不变式定义

在 while 循环开始时，以下性质始终成立：

indegree(i) 的含义: 它表示从未标记 (unmarked) 节点指向节点 \(i\) 的弧的数量。
LIST 的性质: 如果节点 \(j\) 在 LIST 上，则不存在从未标记节点指向 \(j\) 的弧。

环检测原理

如果算法在所有节点被标记之前就结束（即 LIST 变空但 next < n），则剩余的未标记节点中必然存在有向环。
原因: 每个未标记节点至少有一个来自未标记节点的入弧（否则它的入度会是 0，从而被加入 LIST）。在一个有限图中，如果每个节点都有入度，必然存在环。

5.7 复杂度分析 (Complexity Analysis)⚓︎

时间复杂度

总复杂度: \(O(n + m)\)
- \(n\): 节点数量 (nodes)
- \(m\): 弧的数量 (arcs)
分解:
1. 初始化入度: 需要遍历所有弧，耗时 \(O(m)\)。
2. 初始化 LIST: 遍历所有节点，耗时 \(O(n)\)。
3. While 循环:
  - 每个节点最多进入和离开 LIST 一次，耗时 \(O(n)\)。
  - 每条弧最多被扫描一次（当处理其起始节点时），耗时 \(O(m)\)。
4. 合计: \(O(n) + O(m) = O(n + m)\)。

空间复杂度

需要存储入度数组 indegree[]、顺序数组 order[] 以及列表 LIST，复杂度为 \(O(n)\)。
图本身的存储通常为 \(O(n + m)\)。

5.8 主要应用场景⚓︎

线性化依赖关系: 将具有优先约束的任务排列成线性序列。例如：任务 \(i\) 必须在任务 \(j\) 之前完成，对应弧 \((i, j)\)，拓扑排序保证 \(i\) 排在 \(j\) 前面。
预处理步骤: 它是许多涉及无环图算法的重要预处理步骤 (Important starting point for many algorithms that involve acyclic graphs)。
任务调度: 确定课程修读顺序、编译顺序（Makefile 依赖）、项目里程碑计划。
动态规划优化: 在有向无环图上求最长路径或最短路径时，按拓扑顺序处理节点可以保证在计算节点 \(j\) 时，其所有前驱 \(i\) 的结果已计算完毕。
环检测: 快速判断一个有向图是否包含环（如果排序失败，则有环）。

特性	描述
适用图类型	有向图 (Directed Graph)
成功条件	图必须是无环的 (Acyclic)
核心数据结构	入度数组 (Indegree Array) + 队列/列表 (LIST)
时间复杂度	\(O(n + m)\)
关键不变式	`indegree(i)` 始终反映来自未标记节点的入弧数
失败含义	若未标记完所有节点，则图中存在有向环

拓扑排序是网络优化中基础且高效的工具，它不仅提供了节点的线性顺序，还兼任了环检测器的角色。

6. 无向图连通分量 (Undirected Graph Components)⚓︎

BFS 应用: BFS 可以在与组件中弧数成正比的时间内找到无向图的连通分量。
查找所有分量:
1. 维护未标记节点集 \(U\)。
2. 节点标记后从 \(U\) 删除。
3. 每次搜索完一个分量后，从 \(U\) 中选一个新节点开始搜索。

7. 总结 (Summary)⚓︎

主题	关键点	时间复杂度
图搜索 (Graph Search)	找到从 \(s\) 可达的所有节点；确定无向图连通分量	\(O(n + m)\)
广度优先搜索 (BFS)	最短路径树 (最少弧数)	\(O(n + m)\)
深度优先搜索 (DFS)	用于检测环、拓扑排序基础	\(O(n + m)\)
算法验证	使用归纳法证明不变式；建立单调变化量证明终止性	-
拓扑排序	无环图预处理；节点排序使得 \(i < j\) 对于所有弧 \((i, j)\)	\(O(n + m)\)