在有向无环图DAG中用于描述活动之间先后次序的序列称为拓扑序列。它是对图中所有顶点的一种线性排序使得对于每一条有向边 (u → v)u 在序列中都出现在 v 的前面。该序列存在的充要条件是图中无环常用于任务调度、依赖解析等场景。有向无环图DAG一定存在至少一个拓扑序列其根本原因在于DAG中必然存在至少一个入度为0的顶点即没有前驱的顶点且删除该顶点及其出边后剩余子图仍是DAG从而可递归构造线性序。形式化解释如下基础性质在任意有限非空有向无环图中不可能所有顶点入度都大于0。否则从任一顶点出发逆向追溯前驱因每个顶点都有前驱由于顶点数有限必出现重复访问 → 构成有向环与“无环”矛盾。因此DAG中至少存在一个入度为0的顶点称为“源点”。构造性证明归纳法基例1个顶点的DAG其本身即为拓扑序列。归纳步假设对所有含k个顶点的DAG拓扑序列存在考虑含k1个顶点的DAG G。取其一个入度为0的顶点v将其从G中移除及所有以v为起点的边剩余图G’仍是DAG删边/删点不引入环且含k个顶点。由归纳假设G’存在拓扑序列σ。将v置于σ最前端得到序列v σ —— 该序列满足对G中任意边(u→w)若uv则v在w前若u,w∈G’则u在w前由σ保证。故为G的拓扑序列。算法体现Kahn算法正是基于此原理——反复选取并删除当前入度为0的顶点天然生成一个合法拓扑序列DFS法则通过逆后序遍历即完成时间降序确保依赖关系满足。因此“无环”这一结构约束保证了依赖图中总存在“可立即执行”的起点使得全局线性排序成为可能。若某有向图存在拓扑序列则该图一定是有向无环图DAG。这是拓扑序列存在的充要条件即一个有向图存在拓扑序列 ⟺ 该图是有向无环图。反推成立的原因必要性证明假设一个有向图 G 存在拓扑序列 ( v_1, v_2, \dots, v_n )即对图中任意有向边 ( (v_i \to v_j) )都有 ( i j )v_i 在序列中严格位于 v_j 之前。现用反证法证明 G 无环假设 G 中存在一个有向环 ( v_{i_1} \to v_{i_2} \to \cdots \to v_{i_k} \to v_{i_1} )k ≥ 2。根据拓扑序列定义每条边 ( v_{i_p} \to v_{i_{p1}} ) 要求下标满足 ( i_p i_{p1} )从而有[i_1 i_2 \cdots i_k i_1]这导致 ( i_1 i_1 )矛盾。因此环不可能存在 → G 必为有向无环图。✅ 结论拓扑序列的存在性严格等价于图的无环性。不存在“有环却有拓扑序列”的情况反之DAG 一定可拓扑排序如前所述。补充说明实际算法如Kahn或DFS拓扑排序在检测到环时会失败如Kahn算法最终剩余未访问顶点DFS发现回边这正是利用该等价性进行环检测的核心机制。
