对一个 有向无环图(Directed Acyclic Graph，DAG) G 进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边 <u,v> ∈ E(G)，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。

图的数据结构

采用邻接表的形式，较为方便的进行拓扑排序

1	List<List<Integer>> graph;

BFS

开始时，所有入度为00 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

在广度优先搜索的每一步中，我们取出队首的节点 u：

我们将 u 放入答案中；
我们移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么我们就将 v 放入队列中。

在广度优先搜索的过程结束后。如果答案中包含了这 n 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

public int[] topologicalSort(List<List<Integer>> graph) {
    int n = graph.size();
    int[] inDegrees = new int[n];
    Queue<Integer> queue = new ArrayDeque<>();

    for (List<Integer> list : graph) {
        for (int i : list) {
            inDegrees[i]++;
        }
    }

    for (int i = 0; i < n; i++) {
        if (inDegrees[i] == 0) {
            queue.add(i);
        }
    }

    int[] ans = new int[n];
    int index = 0;

    while (!queue.isEmpty()) {
        int u = queue.poll();
        ans[index++] = u;
        for (int adj : graph.get(u)) {
            if (--inDegrees[adj] == 0) {
                queue.add(adj);
            }
        }
    }

    if (index != n) {
        return new int[0];
    }

    return ans;
}

DFS

对于图中的任意一个节点，它在搜索的过程中有三种状态，即：

「未搜索」：我们还没有搜索到这个节点；
「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成）；
「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。

所以我们只要在节点已完成后将其入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于 u 处于栈顶的位置，那么 u 出现在所有 u 的相邻节点的前面。因此对于 u 这个节点而言，它是满足拓扑排序的要求的。

因此我们只需在 dfs 完成后将其入栈，拓扑排序就是栈顶往栈底的顺序。

List<List<Integer>> graph;
// 0 表示未搜索、1 表示搜索中、2 表示已完成
int[] visited;
// 因为无须出栈，直接使用数组模拟栈
int[] ans;
int index;
boolean hasCircle = false;

public int[] topologicalSort(List<List<Integer>> graph) {
    this.graph = graph;
    int n = graph.size();
    visited = new int[n];
    ans = new int[n];
    index = n - 1;

    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            dfs(i);
        }
    }

    if (hasCircle) {
        return new int[0];
    }

    return ans;
}

public void dfs(int u) {
    visited[u] = 1;
    for (int v : graph.get(u)) {
        if (visited[v] == 0) {
            dfs(v);
            if (hasCircle) {
                return;
            }
        } else if (visited[v] == 1) {
            hasCircle = true;
            return;
        }
    }
    visited[u] = 2;
    ans[index--] = u;
}

复杂度分析

两者就是 BFS、DFS 的变种，因此：

时间复杂度： $O(V+E)$ 【邻接表】， $O(V^2)$ 【邻接矩阵】
空间复杂度： $O(V)$