图的有向无环图与拓扑排序 1. 基本定义 有向无环图（DAG）是有向图的一种特殊类型，它不包含任何有向环，即不存在从任一顶点出发经过若干条有向边后回到自身的路径。DAG 是描述具有偏序关系（如任务依赖、时间顺序等）的常用模型。 2. 拓扑排序的概念 对于 DAG 的拓扑排序是指将所有顶点排列成一个线性序列，使得对于图中的每一条有向边 \( u \to v \)，在序列中 \( u \) 都出现在 \( v \) 之前。这样的序列反映了图中顶点之间的依赖关系方向。 3. 拓扑排序的存在性与唯一性 存在性：当且仅当图为 DAG 时，拓扑排序存在（否则有环会导致循环依赖，无法排序）。 唯一性：拓扑排序通常不唯一，因为当多个顶点间没有直接或间接依赖关系时，它们可以任意排列。 4. Kahn 算法（基于入度的广度优先方法） 步骤 ： 计算每个顶点的入度（指向该顶点的边数）。 将所有入度为 0 的顶点加入队列。 从队列中取出顶点 \( u \)，将其加入拓扑序列。 对于 \( u \) 的每个邻接顶点 \( v \)，将其入度减 1；若入度变为 0，则将 \( v \) 加入队列。 重复步骤 3-4 直到队列为空。 若拓扑序列包含所有顶点，则排序成功；否则说明图中有环。 5. 基于深度优先搜索（DFS）的拓扑排序 步骤 ： 对图进行 DFS 遍历，记录每个顶点的完成时间（即递归返回的顺序）。 按完成时间的逆序输出顶点，即可得到拓扑排序。 原理：在 DFS 中，一条边 \( u \to v \) 意味着 \( u \) 的完成时间一定晚于 \( v \)，逆序后 \( u \) 自然在 \( v \) 之前。 6. 时间复杂度与空间复杂度 两种算法的复杂度均为 \( O(|V| + |E|) \)，其中 \( |V| \) 是顶点数，\( |E| \) 是边数，适合处理大规模 DAG。 7. 应用场景 任务调度：如编译器的模块依赖分析、课程选修顺序规划。 数据流分析：在计算有向无环数据流图时确定计算顺序。 事件排序：在版本控制或因果推理中处理偏序事件。