有向无环图的拓扑排序

1. 拓扑排序简介

在计算机科学中，有向无环图（Directed Acyclic Graph，DAG）是指没有环的有向图。本文将介绍如何在 DAG 上以线性时间复杂度完成拓扑排序。

拓扑排序在很多实际问题中都有应用，例如任务调度、编译顺序安排等。它本质上是对图中顶点的一种线性排列，使得所有边的起点都出现在终点之前。

2. 什么是拓扑排序

拓扑排序（Topological Sort）是对 DAG 图顶点的一种线性排序方式，满足：若图中存在一条从顶点 u 到 v 的有向边，则 u 在排序中出现在 v 之前。

举个例子：我们穿衣服时，某些衣物有穿戴顺序要求，比如必须先穿袜子再穿鞋。我们可以用 DAG 来表示这些依赖关系：

图中每个顶点代表一件衣物，箭头表示穿戴顺序。我们要找出一个顺序，满足所有依赖关系，比如：

拓扑排序的一个关键性质是：只要图是无环的，就一定存在至少一种拓扑序列。

3. Kahn 算法

Kahn 算法是一种经典的拓扑排序算法，核心思想是：不断选择入度为 0 的顶点加入排序结果中，并更新其邻居的入度。

3.1. 算法步骤

algorithm KahnsAlgorithm(G):
    // INPUT
    //   G = A Directed Acyclic Graph (DAG)
    // OUTPUT
    //   L = A topological sort of all vertices in G

    Compute in-degree for each vertex in G
    Initialize a queue Q with all vertices of in-degree 0
    
    Initialize an empty vertex list L

    while Q is not empty:
        u <- remove a vertex from Q
        add u to the end of L
        for each neighboring node v of u:
            decrease the in-degree of v by 1
            if the in-degree of v is 0:
                add v to Q

    return L

✅ 关键点：

使用队列保存当前入度为 0 的顶点
每次处理顶点后，更新其邻接顶点的入度
若邻接顶点入度变为 0，则加入队列

⚠️ 注意：若最终结果中顶点数量小于图中总顶点数，说明图中存在环，无法进行拓扑排序。

3.2. 时间复杂度

计算所有顶点的入度：O(V + E)
每个顶点和边都会被处理一次：O(V + E)

✅ **总时间复杂度为 O(V + E)**，线性时间，效率很高。

4. 基于深度优先搜索（DFS）的拓扑排序

我们也可以使用 DFS 来实现拓扑排序。其核心思想是：在递归完成后，将当前顶点添加到结果列表的最前面。

4.1. DFS 遍历回顾

标准 DFS 算法如下：

algorithm DFSTraversal(G):
    // INPUT
    //   G = A graph
    // OUTPUT
    //   L = A list of all vertices in G after DFS traversal

    L <- initialize an empty vertex list
    visited <- initialize an array to false for each vertex

    for each vertex u in G:
        if not visited[u]:
            dfsRecursive(u)

    return L

function dfsRecursive(u):
    visited[u] = true
    add u to the end of L
    for each neighboring vertex v of u:
        if not visited[v]:
            dfsRecursive(v)

⚠️ 问题：这种写法不能保证生成拓扑排序。因为顶点一旦访问就加入列表，无法保证其所有依赖都处理完成。

4.2. 修改后的拓扑排序算法

我们只需将顶点加入结果列表的时机从“访问时”改为“递归完成后”即可：

algorithm DFSTopologicalSort(G):
    // INPUT
    //   G = A Directed Acyclic Graph (DAG)
    // OUTPUT
    //   L = A topological sort of all vertices in G

    L <- initialize an empty vertex list
    visited <- initialize an array to false for each vertex

    for each vertex u in G:
        if not visited[u]:
            topologicalSortRecursive(u)

    return L

function topologicalSortRecursive(u):
    visited[u] = true
    for each neighboring vertex v of u:
        if not visited[v]:
            topologicalSortRecursive(v)
    add u to the front of L

✅ 关键点：

每个顶点只有在所有邻接顶点都处理完后才被加入列表
将顶点添加到列表的前面，保证顺序正确

⚠️ 注意：该算法依赖递归实现，若图非常大，可能会导致栈溢出。可以考虑用显式栈（Stack）实现来避免这个问题。

5. 总结

拓扑排序是针对有向无环图（DAG）的一种排序方法，广泛应用于任务调度、依赖解析等场景。
常见实现方式有两种：
- Kahn 算法：基于入度，使用队列维护当前可处理顶点，实现简单，适合实际应用。
- DFS 实现：基于递归，逻辑清晰，但需注意栈深度问题。
两种算法时间复杂度均为 **O(V + E)**，效率很高。

✅ 推荐使用场景：

Kahn 算法适合图结构明确、需要检测环的场景
DFS 实现适合图结构较小、逻辑清晰的场景

如果你希望看到 Java 实现代码，可以参考我们另一篇文章：Java 中的深度优先搜索。

Persistence

REST

Security