拓扑排序

拓扑排序

拓扑排序是对有向无环图（DAG）的一种线性排序，使得对于每一条有向边 (u, v)，顶点 u 在顶点 v 之前。拓扑排序常用于任务调度、编译依赖关系等场景。

根据定义可以的出拓扑排序的两个性质:

• 如果图中存在环，则不存在拓扑排序。原因:
  • 如果图中存在环，则无法找到一个线性序列使得每个顶点都在其依赖的顶点之前。
• 如果图存在拓扑排序,它的拓扑排序可能不唯一

算法实现

Kahn算法

步骤:

1. 计算每个顶点的入度。
2. 将所有入度为0的顶点加入队列。
3. 重复以下步骤直到队列为空:
   • 从队列中取出一个顶点，将其加入拓扑排序结果。
   • 遍历该顶点的所有邻接点，将它们的入度减1。如果入度为0，则加入队列。
4. 检查环路:
   • 如果拓扑排序结果的顶点数小于图中顶点数，则图中存在环路。 ``` 图结构：A → B → C ↘ D ↗ 步骤：
5. 入度：A(0), B(1), C(1), D(1)
6. 初始队列：A
7. 处理A → 队列加入B、D → 结果序列[A]
8. 处理B → 队列加入C → 结果序列[A,B]
9. 处理D → 入度C减为0 → 结果序列[A,B,D]
10. 处理C → 结果序列[A,B,D,C] 最终排序：A → B → D → C 或 A → D → B → C（可能不唯一） ``` 时间复杂度: O(V + E)，其中 V 是顶点数，E 是边数。

深度优先搜索（DFS）算法

步骤:

1. 标记状态:为每个顶点标记三种状态（未访问、访问中、已访问）。
2. 深度遍历:从任意未访问顶点出发，递归访问其邻接顶点。
3. 记录顺序:将顶点按完成遍历的顺序逆序排列，即为拓扑排序。
4. 检查环路:如果在遍历过程中遇到“访问中”状态的顶点，则图中存在环路。

   图结构同上。
   DFS路径可能为 A → D → C → B，后序逆序为 B → C → D → A → 逆序后拓扑排序为 A → D → C → B。
   

时间复杂度: O(V + E)，其中 V 是顶点数，E 是边数。

习题