有向无环图 依赖关系 经典图论算法

拓扑排序讲义

拓扑排序用来处理“先做什么，再做什么”的问题。只要图中表示的是前后依赖关系，这个算法就非常自然。

一句话理解： 如果图中有一条边 u → v，那么在拓扑排序结果里，u 一定排在 v 前面。

一、什么是拓扑排序

拓扑排序是对一个 有向无环图 中所有顶点排成一个线性顺序。

这个顺序要满足：如果存在边 u → v，那么 u 必须排在 v 前面。

二、适用条件

必须满足

  • 图是 有向图
  • 图中 没有环
  • 也就是图必须是 DAG

不能用于

  • 无向图的普通遍历顺序问题
  • 存在有向环的图
  • 没有前后依赖关系要求的场景

三、生活中的例子

四、拓扑排序为什么从入度为 0 的点开始

入度为 0，表示没有任何边指向这个点，也就是它没有前置依赖。

既然没有别的点必须排在它前面，那么它就可以先排。

核心结论： 每一步都从当前入度为 0 的结点中选一个放进答案，然后删去它发出的边，继续找新的入度为 0 的结点。

五、两种常见实现方法

方法 核心思路 特点
Kahn 算法 统计每个点的入度，把所有入度为 0 的点入队，逐个取出并删边 最常用，适合课堂讲解，也方便判断图中是否有环
DFS 做法 深度优先遍历，结点在“回退时”加入序列，最后逆序 也能得到拓扑序，所以拓扑排序不只一种实现方式

六、Kahn 算法步骤

  1. 统计每个结点的入度。
  2. 把所有入度为 0 的结点加入队列。
  3. 循环取出队头结点，加入拓扑序列。
  4. 删去它指向的边，也就是把相邻结点入度减 1。
  5. 如果某个结点入度变成 0，就把它加入队列。
  6. 直到队列为空。
如何判断有环： 如果最后排入序列的结点数小于总点数，说明还有点永远无法变成入度为 0，图中就存在环。

七、动画样例

下面用你给出的 6 个点样例演示 Kahn 算法。当前演示按其中一种合法顺序进行：

1, 4, 2, 3, 5, 6

未处理 当前取出 已进入拓扑序

当前拓扑序

当前队列中的入度为 0 结点

当前各点入度

点 1 2 3 4 5 6
入度

虚线表示：这条边对应的前置关系已经被“删掉”了。

八、为什么拓扑排序不一定唯一

直接看上面的动画样例。

当结点 4 被取出以后，结点 2 和结点 5 的入度都会变成 0。

这时：

结论： 只要某一步同时出现多个入度为 0 的结点，先取哪一个都可能形成不同的合法拓扑序，所以拓扑排序结果不一定唯一。

九、常见判断题解析

说法 判断 原因
拓扑排序只能用广度优先遍历实现 错 除了基于队列的 Kahn 算法，还可以用 DFS 实现。
每个有向图都至少存在一个拓扑排序 错 只有有向无环图才存在拓扑排序，有环就不行。
拓扑排序一定从入度为 0 的结点开始 对 入度不为 0 说明它前面还有依赖，不能先排。
拓扑排序的方案一定唯一 错 若某一时刻有多个入度为 0 的点，就可能产生多种合法顺序。

十、用途