如何实现拓扑排序算法？

拓扑排序是对有向无环图(DAG)中节点的一种排序方式。它将DAG中节点排成一个线性序列,使得如果存在一条从节点A到节点B的路径,那么在序列中节点A出现在节点B的前面。我们可以使用图和队列实现拓扑排序:

public int[] topologicalSort(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = new List[numCourses];
    int[] inDegrees = new int[numCourses];   // 节点的入度
    Queue<Integer> queue = new LinkedList<>();

    for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();

    for (int[] cp : prerequisites) {
        graph[cp[1]].add(cp[0]);  
        inDegrees[cp[0]]++;  // 节点的入度增加
    }

    for (int i = 0; i < numCourses; i++) {
        if (inDegrees[i] == 0) queue.offer(i);  // 入度为0的节点入队列
    }

    int[] res = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int pre = queue.poll();
        res[idx++] = pre;

        for (int cur : graph[pre]) {
            inDegrees[cur]--;      // 相邻节点的入度减一
            if (inDegrees[cur] == 0) queue.offer(cur);  // 入度为0的节点入队列
        }
    }

    return res;
}

算法流程:

1. 构建图graph和入度数组inDegrees。遍历prerequisites添加边和更新入度。
2. 找出所有入度为 0 的节点,入队列queue。
3. 从队列中取出一个节点pre。
4. 将pre添加到结果数组res中。
5. 遍历pre的相邻节点cur,将cur的入度减一。
6. 如果cur的入度变为 0,入队列queue。
7. 重复步骤3-6,直到queue为空,得到的res即为拓扑排序结果。
8. 返回res数组。

时间复杂度 O(n+e),空间复杂度 O(n)。

所以,拓扑排序的关键是:

1. 构建图和入度数组,添加边和更新入度。
2. 找出入度为 0 的节点入队列。
3. 队列中取出一个节点,添加到结果并更新其相邻节点的入度。
4. 相邻节点的入度变为 0 则入队列。
5. 重复此过程直到队列为空,得到拓扑排序结果。