预备知识

全序与偏序关系

全序关系（Total Order）是集合上的一种二元关系，又称线性序或简单序。它要求集合中任意两个元素都可比较。数学上，全序关系需要同时满足反对称性、传递性和完全性。

反对称性表示：对任意元素 xx 和 yy，若 xx 关系于 yy 且 yy 关系于 xx，则有 x=yx=y。传递性表示：若 xx 关系于 yy，且 yy 关系于 zz，则 xx 关系于 zz。完全性（或连通性）要求任意两个元素 xx 和 yy，要么 xx 关系于 yy，要么 yy 关系于 xx。因此，全序集合中的所有元素可以排列成单一线性序列。

偏序关系（Partial Order）放宽了全序的约束，适合表达依赖网络。偏序关系同样满足反对称性和传递性，但不要求完全性，并包含自反性：对任意元素 xx，都有 xx 关系于 xx。取消完全性后，偏序集合中并非所有元素对都必须可比。

全序是偏序的特例。将偏序集合映射为全序集合的过程称为线性扩展：若原偏序中 x≤yx \le y 成立，则扩展后的全序中仍保持该关系。在计算机科学中，寻找偏序集合的线性扩展即为拓扑排序。由于偏序不要求所有元素可比，同一偏序集合可能存在多个合法线性扩展，因此拓扑排序结果通常不唯一。

离散忘了可以看看殷翔老师的讲义
Part III.Relatioins
Part VI.Graph Theory

深度优先搜索及其实现

深度优先搜索（DFS）的基本思想是沿图的深度方向探索，直到无法继续深入，再通过回溯寻找其他分支。

算法从起始顶点 ss 开始。访问该顶点后，继续探查其未访问邻接点；若存在未访问邻居，则选择一个作为新当前顶点 uu 并递归执行 DFS。当当前顶点的所有出边都处理完毕，且不存在未访问邻接点时，搜索回溯到发现当前顶点的前驱节点。该过程持续到源点可达的所有节点均被发现。

由于图可能非连通，标准 DFS 需要外层调度。当一次从单一起点出发的搜索完成后，若仍有未访问顶点，则选择新的未访问顶点作为起点，重复 DFS，直到所有顶点被访问。对于树结构，DFS 轨迹等价于先序遍历；对于图，该过程会构造深度优先支撑树或森林。

DFS 可以用递归实现，也可以用显式栈模拟递归。BFS 需要维护搜索前沿的所有节点，而 DFS 的空间消耗主要受搜索路径最大深度限制。时间复杂度方面，每条边最多被访问和评估常数次，因此整体时间复杂度为 O(V+E)O(V+E)，其中 VV 为顶点数，EE 为边数。

深度优先搜索的底层实现依赖状态切换系统与时间戳记录机制。顶点状态划分为三种：未发现（UNDISCOVERED）、已发现（DISCOVERED）以及已访问完毕（VISITED）。算法引入全局时钟变量记录顶点的状态变更时间。

以下是实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 对顶点 v 所在连通分量执行递归 DFS；clock 记录全局时间戳。
template <typename Tv, typename Te>
void Graph<Tv, Te>:: DFS( int v, int & clock ) {
    // 记录 v 的发现时间；++clock 保证时间戳单调递增。
    dTime(v) = ++clock;
    // DISCOVERED 表示 v 已进入递归栈，但其出边尚未全部处理。
    status(v) = DISCOVERED;

    // 依次枚举 v 的所有邻接顶点 u。
    for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u))
    {
        // 根据 u 的状态决定边 (v, u) 的类别。
        switch (status(u)) {
            case UNDISCOVERED:
                // u 尚未被任何 DFS 路径发现，(v, u) 成为树边。
                type(v, u) = TREE;
                // 记录 u 在 DFS 森林中的父节点。
                parent(u) = v;
                // 递归进入 u，继续拓展当前 DFS 分支。
                DFS(u, clock);
                break;
            case DISCOVERED:
                // u 仍在递归栈中，说明 (v, u) 指向当前路径上的祖先。
                type(v, u) = BACKWARD;
                break;
            default:
                // u 已访问完毕；比较发现时间区分前向边与跨边。
                type(v, u) = dTime(v) < dTime(u)? FORWARD : CROSS;
                break;
        }
    }

    // v 的所有邻接边均已处理，退出递归栈。
    status(v) = VISITED;
    // 记录 v 的完成时间，用于括号引理和拓扑分析。
    fTime(v) = ++clock;
}

在该实现中，dTime(v) 和 fTime(v) 记录顶点被发现和访问完毕的时间戳。通过传递 clock 变量的引用，算法保证整个遍历过程共享单调递增的时间轴。邻接节点的遍历采用 firstNbr 和 nextNbr 接口，迭代获取当前顶点 vv 的所有邻居 uu。

在遍历期间，针对邻居顶点 u 的状态，switch 分支结构进行边分类处理。如果 u 处于 UNDISCOVERED 状态，搜索树通过该边拓展，记录父节点指针 parent(u) = v，并触发递归调用。若处于其他状态，则进行边的分类标记，不触发递归，防止搜索陷入死循环。循环结束后，将当前节点标记为 VISITED，并记录结束时间戳。与广度优先搜索不同，深度优先搜索在回溯时存在状态变更的逻辑，而广度优先搜索不存在回溯过程。

DISCOVERED 可以理解为“当前仍在递归栈中”，VISITED 则表示“这个顶点的所有后续分支都已经处理完并弹栈”。因此，从当前顶点指向 DISCOVERED 顶点的边会回到祖先，构成后向边；指向 VISITED 顶点的边则只能指向已经结束的分支或后代。

搜索树与森林结构

DFS 的执行轨迹会在图中形成树形结构。从单一顶点 ss 出发，在无向图中会访问与 ss 连通的所有顶点；在有向图中会访问由 ss 可达的所有顶点。

遍历中，由 UNDISCOVERED 状态拓展得到的边称为树边。树边连接的顶点构成以源点为根的 DFS 树。顶点一旦被发现就会修改状态，因此后续树边不会指向已发现顶点，树边结构不会形成回路。当外层调度不断选择未访问顶点启动新搜索时，所有 DFS 树共同构成 DFS 森林。

森林拓扑关系由各节点内部的 parent 指针完整描述。将这些指针方向逆向解析，能够复原出支撑森林的层级关系。深度优先搜索完成后，通过状态与时间戳数据，系统能够推导原图的连通属性与层次结构。

括号引理与活跃期

时间戳记录 DFS 的运行顺序。每个顶点具有一个活跃期，定义为发现时间与访问完毕时间构成的区间 (dTime[u],fTime[u])。

括号引理指出：在给定有向图及其 DFS 森林中，仅根据顶点活跃期区间即可判断祖先后代关系：

其一，顶点 uu 是顶点 vv 的后代，当且仅当 uu 的活跃期是 vv 活跃期的严格子集。即区间 (dTime[u],fTime[u]) 包含于 (dTime[v],fTime[v]) 之中。该包含关系表明，祖先必定先于后代被发现，并且必须在所有后代分支探索完毕后结束活跃状态。

其二，顶点 uu 是顶点 vv 的祖先，当且仅当 uu 的活跃期完全包含 vv 的活跃期。

其三，如果顶点 uu 与顶点 vv 在支撑森林中不存在祖先后代承袭关系，当且仅当两者的活跃期交集为空集。在时间轴上，这意味着一个顶点的探索过程完全在另一个顶点被发现之前结束。括号引理将复杂的图拓扑关系转换为一维时间区间的判定依据，仅凭状态数组与时间戳即可对各边进行分类归属。

图遍历边分类

DFS 可根据时间戳与状态将边划分为四类，用于分析图结构。

树边（TREE）：当算法从当前顶点进入处于未发现状态的目标顶点时，该边标记为树边。树边构成深度优先森林的骨干路径。

后向边（BACKWARD）：当试图从当前顶点出发，经过边到达正处于已发现但尚未访问完毕状态的目标顶点时，该边判定为后向边。目标顶点是当前顶点的祖先节点。在深度优先搜索中，发现后向边是有向图中存在回路的充要条件。后向边的数量与回路数量具有直接相关性，是循环检测算法的核心判定依据。

前向边（FORWARD）：当尝试通过边进入已经处于访问完毕状态的目标顶点，且当前顶点的发现时间早于目标顶点的发现时间时，该边为前向边。目标顶点在另一条通过树边拓展的路径中已被探明，且目标顶点是当前顶点的后代。

跨边（CROSS）：与前向边相似，跨边同样指向已处于访问完毕状态的顶点。区别在于跨边目标顶点的发现时间早于当前顶点的发现时间。这表明目标顶点的活跃期先期结束，与当前顶点所在的分支无交集，该边横跨了搜索树的独立分支。

图遍历算法对比

深度优先搜索与广度优先搜索适用于不同场景。二者的搜索策略和内存特性不同，对应的典型应用如下：

应用场景 适用算法框架
连通图的支撑树构建 深度优先搜索 / 广度优先搜索
非连通图的支撑森林构建 深度优先搜索 / 广度优先搜索
连通性检测 深度优先搜索 / 广度优先搜索
无向图环路检测与二部图判定 深度优先搜索 / 广度优先搜索
有向图环路检测 深度优先搜索
顶点之间可达性检测与路径求解 深度优先搜索 / 广度优先搜索
顶点之间的最短距离求解 广度优先搜索
直径、半径、围长、中心计算 广度优先搜索
欧拉回路求解 深度优先搜索
拓扑排序算法 深度优先搜索
双连通分量与强连通分量分解 深度优先搜索

广度优先搜索按层扩展，可以确定源点到目标节点经过最少边数的路径，适合无权图最短距离与中心度计算。深度优先搜索通常不用于最短路径优化，更适合验证可达性和分析拓扑结构。

在分析深层拓扑性质时，DFS 更常用。有向图环路检测依赖后向边识别；双连通分量和强连通分量分解依赖时间戳与回溯；拓扑排序也可由 DFS 完成。

深度优先搜索实例

为展示深度优先搜索状态机的工作机制与时间戳的演进过程，对包含多个顶点的图执行详细的运行轨迹追踪。设定起始时钟变量为 0，图顶点集合为 {a,b,c,d,e,f,g,h,i,j}\{a,b,c,d,e,f,g,h,i,j\}。

在第一阶段，算法选定顶点 a 为起点。时钟变量自增为 1，顶点 a 状态变更为已发现，记录发现时间 a:1。算法考察 a 的邻接分支，选定未发现的顶点 b。时钟变量递增，顶点 b 被发现，记录 b:2。沿着树边继续深入，顶点 b 邻接的顶点 c 被探查，记录 c:3。算法由此在连通图内持续向深层推进，后续依次发现处于路径深处的顶点，相继记录时间戳 f:4，h:5，g:6。

当搜索触及顶点 j 时，时间戳更新为 7，记录 j:7。此时顶点 j 无任何未发现的邻接出边，算法判定 j 节点探查结束。状态变更为访问完毕，记录结束时间戳 8。顶点 j 的活跃期闭合为 (7,8)。完成 j 的访问后，算法回溯至发现 j 的上一层前驱节点，并在该节点邻居集合中继续探查，发现顶点 i，记录时间戳 i:9。随后搜索进一步推进至顶点 d，记录 d:10。

在第二阶段，顶点 d 出边探查完毕。由于 d 所在的局部路径存在指向已发现节点（即祖先）的边，触发后向边分类逻辑，表明图中存在局部回路。顶点 d 探查结束，记录访问完毕时间戳 11，此时活跃期闭合为 (10,11)。随后，算法产生连续回溯。顶点 i 探查结束，闭合活跃期 (9,12)。顶点 g 闭合活跃期 (6,13)。顶点 h 闭合活跃期 (5,14)。顶点 f 闭合活跃期 (4,15)。控制流回退至顶点 c。

在第三阶段，从顶点 c 返回的过程中，顶点 c 本身的探测完毕，记录时间戳 16，闭合活跃期 (3,16)。此时回溯至顶点 b，算法继续探测 b 的其他相邻分支，发现了尚未被访问的独立分支顶点 e。时间戳更新，记录发现时间 e:17。顶点 e 探测后结束，闭合活跃期 (17,18)。随后回溯至 b 并结束其状态，记录访问完毕时间戳 19，闭合活跃期 (2,19)。最终回溯至初始顶点 a，记录访问完毕时间戳 20，闭合活跃期 (1,20)。

该执行实例中时间戳的分布呈现出严格的嵌套结构。例如顶点 b 的活跃期 (2,19) 完全包含 c 的活跃期 (3,16)，验证了 b 为 c 祖先的括号引理。而顶点 e(17,18) 与顶点 c(3,16) 区间不交，符合两者处于独立搜索分支的结论。这印证了仅凭全局时间戳即可完成边分类与拓扑分析的理论设计。

有向无环图及其应用

有向无环图（DAG）是带方向且不含回路的图结构，常用于依赖建模。

在系统应用中，DAG 用于表达时序要求或因果依赖。面向对象语言中的类继承关系应符合 DAG 结构，以避免循环继承。操作系统中，线程间资源等待关系也可建模为依赖图，用于发现潜在死锁。

在工程规划中，课程先修关系、知识模块安排、项目规划、编译依赖和自动回复防回路等问题，都可以通过 DAG 与拓扑排序建模。

拓扑排序

定义

每个有向无环图都对应某个偏序集合。拓扑排序等价于为该偏序集合构造一个相容的全序序列。在线性序列中，原图每条有向边表示的前驱到后继的依赖次序必须保持不变，即不存在顶点通过有向边指向排在其前面的顶点。

拓扑排序的前提是目标图无环。若图中存在环路，则一组顶点互为前置依赖，无法展开为线性序列。因此，拓扑排序算法需要同时具备环检测能力：若原图不是 DAG，则报告异常；若无环，则返回一个相容的线性排列。

关于拓扑排序的存在性，有限偏序集合必具有极值元素。在任何有向无环图中，必存在至少一个入度为零的顶点 mm。零入度表明该顶点未受任何前置依赖约束，可作为序列起点。假设将顶点 mm 及其发出的关联边自原图 GG 中剔除，残留子图 G∖{m}G \setminus \{m\} 仍为有向无环图。通过归纳法推导，若该子图存在拓扑排序序列 S={uk1,uk2,…,ukn−1}S=\{u_{k_1},u_{k_2},\ldots,u_{k_{n-1}}\}，则 S′={m,uk1,uk2,…,ukn−1}S'=\{m,u_{k_1},u_{k_2},\ldots,u_{k_{n-1}}\} 即为原图 GG 的完整拓扑排序。当图中入度为零的顶点不唯一时，拓扑排序结果亦不唯一。该定理不仅证实了任何有向无环图必有拓扑排序，也直接导出了一种基于入度的迭代算法模型。

拓扑排序不是在寻找唯一答案，而是在寻找任何一个不违反依赖关系的线性序列。只要某一时刻存在多个零入度顶点，选谁先输出都可能得到不同但同样合法的结果。使用队列、栈或优先队列，会影响输出顺序，却不影响合法性。

零入度算法

零入度算法（Kahn 算法）基于拓扑排序存在性定理：不断输出当前入度为零的顶点，并删除其出边，直到图被清空或检测到环。

算法先遍历所有顶点统计入度，将所有入度为零的顶点存入栈或队列，并初始化输出序列。

循环中，只要零入度辅助容器不为空，就弹出顶点 vv 并加入结果序列。随后枚举 vv 的所有出边，对每个邻接顶点 uu 将入度减 1，等价于删除顶点 vv 及其关联出边。若 uu 的入度降为 0，说明其所有前置约束已解除，将其加入辅助容器。

循环结束后检查是否所有顶点都已输出。若仍有顶点未处理，当且仅当原图包含环路，算法报告“非 DAG 图”；否则返回结果序列。该算法只线性扫描顶点与边，时间复杂度为 O(V+E)O(V+E) 或 O(n+e)O(n+e)。

零入度算法执行实例

图模型初始状态为图 (a)，包含顶点 {A,B,C,D,E,F}\{A,B,C,D,E,F\}。

初始阶段遍历统计表明，顶点 AA 入度为零，不依赖其余节点，被选定为首个移除对象。在状态 (b) 中，顶点 AA 输出，与之关联的出边被撤销。受此操作影响，邻接顶点 CC 和 DD 的入度减少。

检测发现，更新后的图中顶点 DD 与 BB 入度同为零。算法任选其一，弹出顶点 BB 输出，并消解 BB 的出边。在状态 ( c) 中，依赖 BB 的后续节点入度更新。随后处理剩余的零入度顶点 CC，其输出后状态转至 (d)。此时，顶点 DD 的前置依赖由于 AA 与 CC 的移除已全部清空，入度变零，继而被输出，系统状态更迭为 (e)。

按照相同逻辑，随着网络依赖的不断剥离，图的规模逐层缩小。顶点 FF 与 EE 依次成为零入度节点并按序输出，状态经由 (f) 演进至 (g)，此时全图清空。根据剥离次序生成的顶点序列即为合法拓扑排序方案。该实例呈现了多并发入口及节点状态联动更新的算法处理流程。

零出度算法

零出度算法与零入度思路相反：它关注无后续依赖的顶点。当一个节点的所有后继都已处理，该节点就可以安排在这些后继之前。该逻辑与 DFS 回溯过程一致。

零出度算法基于深度优先搜索框架，借助栈结构 SS 记录拓扑序列。算法对图执行深度遍历以生成森林。在探索过程中，算法利用状态监控功能判断边类型。若探查过程中发现后向边（当试图从当前顶点出发，经过边到达正处于已发现但尚未访问完毕状态的目标顶点时，该边判定为后向边），即表明试图回到处于活跃期的祖先节点，该特征证实存在环路，算法立即返回并报告 “NOT_A_DAG” 退出。

若不存在环路，搜索进程向下推进。每当有顶点的所有分支探查结束，其状态更新为 VISITED 时，将该顶点压入栈 SS。根据括号引理，后代顶点的完成时间总是早于祖先顶点，因此后代会在祖先之前结束访问并率先入栈。当深度优先搜索结束，各个节点按结束时间 fTime 逆序排列存放于栈中。顺序弹出栈中元素，得到的线性列表即为拓扑排序序列。算法的时间复杂度与基础图遍历一致，为 O(V+E)O(V+E)。

零出度算法的“输出时机”与零入度算法相反。Kahn 算法在依赖清空时立刻输出节点；DFS 版本则在节点的所有后继都已经安排好之后才压栈。最后从栈顶弹出，等价于按完成时间从晚到早排列，从而让前驱出现在后继之前。

零出度算法执行实例

初始阶段如图 (a) 所示，如果从 BB 出发进行 DFS（即图示的情况）：

  • 访问 DD，没有后续节点，回溯，状态更新为 VISITED，DD 进栈。
  • CC 的分支探查还没有结束，再次向下探到 FF，没有后续节点，回溯，状态更新为 VISITED，FF 进栈。
  • 从 FF 回溯遇到 EE，此时其没有后续节点，分支探查结束，回溯，状态更新为 VISITED，EE 进栈。
  • 回到 CC，此时 CC 的另一个分支 DD 已经进栈，分支探查完成，回溯，状态更新为 VISITED，CC 进栈。
  • 回到 BB，现在其分支探查结束，进栈。
  • 此时只剩一个节点 AA，其指向的节点已经全部入栈，不需要分支探查，返回并入栈。

如果从 AA 出发进行 DFS：

  • 访问 DD，没有后续节点，回溯，状态更新为 VISITED，DD 进栈。
  • AA 的分支探查还没有结束，再次向下探到 FF，没有后续节点，回溯，状态更新为 VISITED，FF 进栈。
  • 从 FF 回溯遇到 EE，此时其没有后续节点，分支探查结束，回溯，状态更新为 VISITED，EE 进栈。
  • 回到 CC，此时 CC 的另一个分支 FF 已经进栈，分支探查完成，回溯，状态更新为 VISITED，CC 进栈。
  • 回到 AA，现在其分支探查结束，进栈。
  • 此时只剩一个节点 BB，其指向的节点已经入栈，不需要分支探查，返回并入栈。

拓扑排序代码实现

基于 DFS 状态机的零出度拓扑排序，只需在基础遍历逻辑上增加环检测与入栈动作。核心代码如下。

首层接口设计接收时间戳引用及外部分配的栈指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 基于 DFS 完成时间构造拓扑序；发现后向边时返回 false。
template <typename Tv, typename Te> // 顶点类型、边类型
bool Graph<Tv, Te>:: TSort(int v, int & clock, Stack<Tv>* S) {
    // 记录 v 的发现时间。
    dTime(v) = ++clock;
    // v 进入递归栈，处于活跃期。
    status(v) = DISCOVERED;

    // 枚举 v 的所有后继顶点 u。
    for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {
        // 根据 u 的 DFS 状态进行边分类和环检测。
        switch (status(u)) {
            case UNDISCOVERED:
                // u 尚未访问，(v, u) 是拓扑 DFS 森林中的树边。
                parent(u) = v;
                type(v, u) = TREE;
                // 若子递归检测到环，立即向上传递失败结果。
                if (!TSort(u, clock, S)) return false;
                break;
            case DISCOVERED:
                // 指向活跃顶点的边是后向边，说明图中存在环。
                type(v, u) = BACKWARD;
                return false;
            default:
                // u 已完成，按时间戳区分前向边和跨边。
                type(v, u) = dTime(v) < dTime(u)? FORWARD : CROSS;
                break;
        }
    }

    // 所有后继处理完毕，v 可以退出活跃期。
    status(v) = VISITED;
    // 后继先入栈，前驱后入栈；最终弹栈得到拓扑序。
    S->push(vertex(v));
    // 当前分支未发现环。
    return true;
}

代码将原本的空返回值改为布尔值。处理 UNDISCOVERED 邻接边时，递归调用嵌入 if (!TSort(u, clock, S)) return false;。若深层递归检测到环，false 会沿调用链上传，使算法提前终止。处理 DISCOVERED 分支时，若邻居仍处于活跃期，说明出现后向边，直接 return false;。

节点入栈发生在循环结束后，S->push(vertex(v)); 将退出活跃期的当前节点压入输出栈。该顺序与各节点 fTime 的结束顺序一致，使后继节点先入栈，前驱节点后入栈。最终弹栈即可得到拓扑序列，复杂度仍为 O(V+E)O(V+E)。