有向无环图

有向无环图（directed acyclic graph，DAG）是不含有向环的有向图。它允许分支、汇合以及许多不同的路径，只禁止沿箭头走若干步后回到出发点。本文讨论有限图；零长度的停留不算有向环，自环则是一条长度一的有向环，因而被排除。

例如，取边 $a\to c,b\to c,c\to d,b\to e,e\to f,d\to f$。可以把顶点排成 $a,b,c,e,d,f$，每条边都从排在前面的点指向后面的点，所以不可能沿箭头返回前面的位置。这种排列叫拓扑排序。

路径可以汇合，忽略方向后也可能有环；DAG排除的是沿箭头方向的闭合路线。

有向环和无向环不同

一个有向环由不同顶点 $v_0,\dots ,v_{k-1}$ 组成，边依次为 $v_i\to v_{i+1}$ 及 $v_{k-1}\to v_0$。主例忽略方向后含无向环 $b-c-d-f-e-b$，但不能沿这一圈保持箭头方向，所以仍是DAG。树是底层无向结构无环的图，DAG不要求底层图是树。

用有向路径表示可达性时，若不同顶点 $u,v$ 同时满足 $u{\to }^{\ast }v$ 与 $v{\to }^{\ast }u$，连接两条路径便产生有向闭游走；去掉重复区段可以抽出有向环。因此DAG中不同顶点不能互达，其强连通分量都是单点；反向结论还须排除自环，因为自环不改变分量大小。

无环等价于存在拓扑顺序

定理。 有限有向图是DAG，当且仅当存在一个顶点线性顺序，使每条有向边均从前指向后。

证明。 如果已有这种顺序，沿一条边位置严格增加。若出现有向环，绕一圈后位置既严格增加又回到原值，不可能。

反过来，先证明任意非空有限DAG都有入度零顶点。若每点入度都正，任取一点，沿一条进入边逆向找前驱，再找其前驱。由于顶点有限，最终有某顶点重复；从重复之间的前驱链按箭头正向读，就得到有向环，矛盾。

因此可把一个入度零顶点放在最前，然后删除它及出边。剩余诱导子图仍无环，否则其中的环也是原图的环。对顶点数归纳，剩余顶点有一个合格顺序；把删掉的点放在最前时，没有边从后面的顶点进入它，所有出边又都指向后方，于是获得全图顺序。空图以空顺序作为归纳起点，证明完成。

这一论证中的有限性确实在“沿前驱追溯必重复”和归纳中起作用。对无限图，拓扑排序的存在与所允许的线性顺序类型需要另行讨论，不能直接把有限删除过程当作终止证明。

主例中的顺序、路径和变式

主例中 $a,b$ 入度零；先选 $a$ 再选 $b$ 后，$c,e$ 都可进入顺序，得到 $a,b,c,e,d,f$。也可以先放 $b$ 再放 $a$，或在条件允许时交换 $c,e$。DAG只规定边引出的先后关系，未必规定所有顶点的唯一顺序。

最长有向路径之一为 $a\to c\to d\to f$，长度三；$b\to c\to d\to f$ 同长。每条有向路径不能重复顶点，否则重复区段构成有向闭游走并含环，所以 $n$ 点DAG的有向路径至多 $n-1$ 条边。

变式。 增加边 $f\to b$ 会产生环 $b\to e\to f\to b$，原图不再是DAG；增加边 $a\to d$ 则不产生环，因为旧拓扑顺序中 $a$ 在 $d$ 前，新边仍满足顺序条件。后者虽然不改变 $a$ 能到达 $d$ 的事实，却缩短了它们间最少边数。

邻接矩阵的幂与偏序

按拓扑顺序排列顶点，邻接矩阵的非零项只可能出现在主对角线上方，因此是严格上三角矩阵。更直接地，邻接矩阵的 $r$ 次幂记录 $r$ 步游走数；DAG中没有 $n$ 步游走，所以 $$A^n=0.$$ 反过来，若一个图含有向环，可以沿环走任意给定的步数，特别是 $n$ 步，所以 $A^n$ 至少有一个正条目。因此对零一邻接矩阵，这一零矩阵条件也刻画无环性。这里使用普通非负计数；若给边任意正负权重，幂中的代数抵消就不再表示游走不存在。

把“存在零步或多步路径”作为关系，DAG的可达性满足自反和传递；不同点互达被排除，又给出反对称性，因此定义了一个偏序关系。图中画出的边不必是这个偏序的最简表示，可能包含已经由较长路径蕴含的冗余边。拓扑排序则把这个偏序扩展成线性顺序，适合表达先修关系、任务依赖和动态规划的计算次序。