4.2 Directed Graphs：可达性、DAG拓扑序与强连通分量

4.2 · Directed Graphs覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“4.2 · Directed Graphs”如何用有向可达、环检测、拓扑序与强连通分量区分方向性结构问题
能逐项核对有向图、有向图表示、有向可达性、环与有向无环图、拓扑顺序、强连通性，并区分作者站内容与本页独立补充
能按“DFS/BFS、拓扑排序与 Kosaraju-Sharir SCC 都可在线性 Θ(V+E) 时间完成”手算一个最小输入，逐步检查“拓扑序要求每条边 v→w 都满足 order(v) 小于 order(w)；同一 SCC 内顶点两两可达”
能注入“检测有向环时递归返回后未清除 onStack，或 SCC 第一遍没有在反向图上取逆后序”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“4·2 · Directed Graphs”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“4·2 · Directed Graphs”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“4·2 · Directed Graphs”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：4.2 · Directed Graphs

1. 有向图：在本页通过“建立有向邻接”连接解释、交互状态和练习验收。
2. 有向图表示：在本页通过“执行可达搜索”连接解释、交互状态和练习验收。
3. 有向可达性：在本页通过“检测回边或生成逆后序”连接解释、交互状态和练习验收。
4. 环与有向无环图：在本页通过“分配 SCC”连接解释、交互状态和练习验收。
5. 拓扑顺序：在本页通过“验证拓扑或互达”连接解释、交互状态和练习验收。
6. 强连通性：在本页通过“建立有向邻接”连接解释、交互状态和练习验收。

从“能去，不代表能回”开始

有向图（directed graphs）把web links、task dependencies、data flow、call relation、one-way roads与state transitions建模为arrows。与undirected graph最根本的差别不是画了箭头，而是reachability不再symmetric：v可到w，不推出w可到v。

先预测从2能到4且4能到5，是否说明5也能到2。不会。只有若5到2也存在directed path，三者才可能落在同一strong component。Directed relation迫使我们区分out-neighbors、in-neighbors、source-to-target path和mutual reachability。

官方4.2按digraph representation、directed reachability、cycles and DAGs、DFS orders/topological order、strong connectivity与transitive closure展开。它们都复用DFS skeleton，但每一步新增的state决定不同certificate。

selected vertex = 4show reverse digraph

outdegree

indegree

adj(4)

2 5

Directed edge v-to-w只进入adj(v)；reverse把每条arrow翻转，因此indegree与outdegree交换，reachability也会改变。

4.2.1 Digraph representation：edge只进入from的adjacency list

有向图表示（digraph representation）与4.1 Graph相似，但 addEdge(v,w) 只写 adj[v]：

public void addEdge(int v, int w) {
    validateVertex(v);
    validateVertex(w);
    adj[v].add(w);
    indegree[w]++;
    E++;
}
 
public Iterable<Integer> adj(int v) {
    return adj[v];
}

adj(v)只迭代从v指出的destinations，cost proportional to outdegree(v)。每条edge给一个source贡献outdegree、给一个destination贡献indegree，因此：

\sum_v outdegree(v)=E=\sum_v indegree(v)

Digraph仍允许parallel edges与self-loops。Adjacency-list space Theta(V+E)，而不是undirected graph的2E endpoint entries。若错误地双向添加，所有one-way semantics消失，directed reachability与SCC都会被扩大。

Reverse digraph (G^R) 翻转每条edge：

public Digraph reverse() {
    Digraph reverse = new Digraph(V);
    for (int v = 0; v < V; v++)
        for (int w : adj(v))
            reverse.addEdge(w, v);
    return reverse;
}

Reverse是本节的核心变换：w reachable from v in G 等价于 v reachable from w in reverse(G)。它让“谁能到达s”变成普通的“从s可达谁”，也为Kosaraju SCC提供第一遍order。

4.2.2 Directed reachability：只沿outgoing edges

有向可达性（directed reachability）可直接复用DFS，但必须使用Digraph的outgoing adj：

private void dfs(Digraph G, int v) {
    marked[v] = true;
    count++;
    for (int w : G.adj(v))
        if (!marked[w]) dfs(G, w);
}

Single-source marked[w] 回答source到w；它不回答w到source。后者应在reverse(G)从source运行DFS，或在G从w运行DFS。Strong connectivity正是两个方向都true。

Multi-source DirectedDFS接受sources iterable，对每个尚未marked source启动同一DFS；最终marked set是所有source reachability sets的union。它适合正则表达式NFA中的current states、multiple entry points或contagion sources。

DFS只进入每个reachable vertex一次并scan其outgoing list，whole digraph worst：

T_{\mathrm{reach}}=\Theta(V+E)

若只访问局部，则成本按reachable subgraph计。Path version仍用edgeTo记录first-discovery parent；directed path certificate必须逐pair验证edge方向，不能只检查两个vertices相邻。

4.2.3 Cycles and DAGs：onStack区分back edge与finished edge

环与有向无环图（cycles and DAGs）需要比marked更多的信息。Directed cycle是沿arrows回到start的nonempty path；DAG（directed acyclic graph）允许tasks按依赖顺序线性安排。

仅看到edge指向marked vertex不能判cycle。Marked vertex可能早已完成，edge只是cross/forward edge。DirectedCycle额外维护 onStack[v]：vertex enter设true，所有descendants完成后设false；edge指向onStack vertex才是back edge。

private void dfs(Digraph G, int v) {
    onStack[v] = true;
    marked[v] = true;
    for (int w : G.adj(v)) {
        if (cycle != null) return;
        if (!marked[w]) {
            edgeTo[w] = v;
            dfs(G, w);
        } else if (onStack[w]) {
            cycle = new Stack<Integer>();
            for (int x = v; x != w; x = edgeTo[x]) cycle.push(x);
            cycle.push(w);
            cycle.push(v);
        }
    }
    onStack[v] = false;
}

Cycle certificate应首尾相同，每个consecutive pair是actual directed edge，intermediate vertices不重复。onStack是当前active recursion path，不是“访问过”；漏掉return时clear会把finished subtree错当active ancestor。

4.2.4 DFS orders：enter、finish与reverse finish

DepthFirstOrder在DFS生命周期的三个时点记录vertex：

Preorder：enter并mark时enqueue。
Postorder：所有out-neighbors完成后enqueue。
Reverse postorder：把postorder反转。

Postorder反映“descendants先完成，ancestor后完成”。在DAG中，若有edge (v\to w)，DFS要么由v进入w并让w先finish，要么w已在其他search中finish；v不会在w仍active时由edge回到w，否则存在cycle。因此reverse post让v排在w之前。

Pre/post arrays还支持constant-time interval reasoning：在DFS tree中，ancestor的pre早且post晚。不过general digraph edge classification需结合tree structure，不能只看一个order list。

4.2.5 Topological order：所有arrows都向前

拓扑顺序（topological order）是dependency schedule。若rank记录position，certificate是：

\forall(v\to w)\in E,\quad rank(v)<rank(w)

关键定理有两部分：

Digraph有topological order当且仅当它是DAG。
DAG的DFS reverse postorder是一种topological order。

若存在directed cycle，cycle上的每条edge要求rank严格递增，绕一圈却要求start小于自身，矛盾；所以cycle certificate足以拒绝order。反之DAG无back edge，reverse post满足所有edges forward。

Official Topological先运行DirectedCycle；无cycle才计算DepthFirstOrder.reversePost，并建立rank array。Whole processTheta(V+E)。Topological order通常不唯一；两个indegree-zero tasks可交换。若client需要deterministic output，应规定tie-breaker。

Queue-based Kahn algorithm是另一证书：初始化所有indegrees，将zero-indegree sources入queue，逐个remove并decrement outgoing destinations；若最终processed count小于V，remaining subgraph含cycle。它同样linear，并适合显式追踪ready tasks。

4.2.6 Strong connectivity：mutual reachability的equivalence classes

强连通性（strong connectivity）要求两个方向都可达：

v\sim w \iff (v\leadsto w)\land(w\leadsto v)

它是equivalence relation，因而partition vertices。DAG中每个vertex单独构成一个SCC；任何含多个vertices的SCC必含directed cycle。

Kosaraju-Sharir algorithm只需两轮DFS：

在reverse(G)上计算reverse postorder。
按该order在G上对每个unmarked vertex运行DFS；每次search得到一个SCC并赋同一id。

为什么first-pass order重要？把每个SCC收缩为kernel DAG。Reverse graph把kernel arrows反向；其reverse postorder让第二遍优先从original kernel的sink-side component启动，该DFS不会越过cross edge进入尚未处理component，因此一次search恰好封闭一个SCC。随意用preorder没有这一保证。

Total work是两次DFS加一次reverse：

T_{\mathrm{SCC}}=\Theta(V+E)

预处理后 stronglyConnected(v,w)只比较ids，constant time。Certificate可在每个id内选representative，验证所有members both reachable；cross-id pair至少缺一个方向。

4.2.7 Kernel DAG：先压缩cycles，再分析global flow

将每个SCC contraction为single vertex，保留不同components之间的arrows并deduplicate，得到kernel DAG（condensation graph）。它必定acyclic：若components间形成cycle，cycle上components彼此可达，本应合并为一个SCC。

Kernel DAG把local cyclic behavior与global one-way flow分开。可在其上做topological schedule、source/sink analysis、2-SAT assignment或reachable-core reasoning。任意original path映射成component path；同component内部可自由mutually reach。

SCC output验收不仅看count。应核对每个original edge：同id是internal edge，不同id则成为kernel edge；kernel必须通过DirectedCycle检查；所有vertices恰好属于一个component；component sizes总和V。

4.2.8 Transitive closure：用space换大量reachability queries

Transitive closure保留同一vertices，并在v可达w时包含logical edge v到w。Simple implementation为每个source运行一次DirectedDFS，保存V组marked arrays：

public TransitiveClosure(Digraph G) {
    tc = new DirectedDFS[G.V()];
    for (int v = 0; v < G.V(); v++)
        tc[v] = new DirectedDFS(G, v);
}
 
public boolean reachable(int v, int w) {
    return tc[v].marked(w);
}

Preprocessing timeTheta(V(V+E))、spaceTheta(V squared)，之后query constant。它适合static medium graph与大量queries；large sparse graph若queries少，按需DFS更节省。Dynamic edge updates会使closure maintenance复杂，不能继续假设一次build永久有效。

Closure certificate包含reflexive reachability、每条original edge可达、transitivity：若v可达w且w可达x，则v可达x。SCC在closure matrix中表现为互相全true的diagonal blocks。

统一验收：每增加一种state就增加一种certificate

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“4.2 · Directed Graphs”的两个最小情境间切换，再逐项选择正式概念。预测“DFS/BFS、拓扑排序与 Kosaraju-Sharir SCC 都可在线性 Θ(V+E) 时间完成”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

4.2 · Directed Graphs：对象、操作与不变量

用有向可达、环检测、拓扑序与强连通分量区分方向性结构问题

选择最小情境

切换正式概念

拓扑前提: 加入边 0→1、1→2、2→0
当前观察: directed graphs：检测到有向环后拒绝输出拓扑序

DFS/BFS、拓扑排序与 Kosaraju-Sharir SCC 都可在线性 Θ(V+E) 时间完成

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

有向图：在实验 1 中指出对应状态，并写出一个通过条件。
有向图表示：在实验 2 中指出对应状态，并写出一个通过条件。
有向可达性：在实验 3 中指出对应状态，并写出一个通过条件。
环与有向无环图：在实验 1 中指出对应状态，并写出一个通过条件。
拓扑顺序：在实验 2 中指出对应状态，并写出一个通过条件。
强连通性：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“DFS/BFS、拓扑排序与 Kosaraju-Sharir SCC 都可在线性 Θ(V+E) 时间完成”不是孤立结论？

问题 3：故障恢复。 怎样证明“检测有向环时递归返回后未清除 onStack，或 SCC 第一遍没有在反向图上取逆后序”已经修复？

保存原图/反向图、marked、onStack、edgeTo、逆后序、component id 与可达矩阵预言机作为正常基线；注入该故障并标记第一个违反“拓扑序要求每条边 v→w 都满足 order(v) 小于 order(w)；同一 SCC 内顶点两两可达”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

本章回顾

Directed edge只进入source adjacency list；indegree sum与outdegree sum都等于E。
Reverse graph把“谁能到s”转成“从s能到谁”，并支撑SCC ordering。
DirectedDFS沿outgoing edges计算single/multi-source reachability，关系通常不symmetric。
Cycle detection必须区分marked与onStack，back edge to active ancestor才闭合directed cycle。
DFS记录pre、post与reverse post；DAG的reverse post是一种topological order。
Digraph有topological order当且仅当无directed cycle，cycle是拒绝schedule的certificate。
Kosaraju先在reverse graph定order，再在original graph逐DFS划分SCC，整体linear。
SCC contraction形成kernel DAG；transitive closure则用quadratic space换constant reachability query。