跳至主要內容

环检测及拓扑排序算法

labuladong原创数据结构图论算法约 7996 字

207. 课程表 https://leetcode.cn/problems/course-schedule

207. Course Schedule https://leetcode.com/problems/course-schedule

210. 课程表 II https://leetcode.cn/problems/course-schedule-ii

210. Course Schedule II https://leetcode.com/problems/course-schedule-ii

剑指 Offer II 113. 课程顺序 https://leetcode.cn/problems/QA2IGt

剑指 Offer II 113. 课程顺序 https://leetcode.com/problems/QA2IGt

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCodeDifficulty
207. Course Schedule🟠
210. Course Schedule II🟠

Prerequisites

Before reading this article, you need to have learned:

Tip

本文有视频版：Detailed Explanation and Application of Topological Sorting。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

Graph data structures have some unique algorithms such as bipartite graph detection, cycle detection in graphs, topological sorting, the classic minimum spanning tree, single-source shortest path problem, and more complex issues like network flow.

However, for practical purposes, unless you're preparing for competitions, you might not need to learn complex topics like network flow. Algorithms like Minimum Spanning Tree and Shortest Path Problem are classic but not frequently encountered in typical problem-solving scenarios. You can learn them if you have extra time. Algorithms like Bipartite Graph Detection and topological sorting are fundamentally graph traversal techniques and should be mastered proficiently.

In this article, we will discuss two graph algorithms in detail using specific problem examples: cycle detection in directed graphs and topological sorting.

Both algorithms can be solved using DFS (Depth-First Search) or BFS (Breadth-First Search) approaches. While the BFS solution might be more straightforward in terms of implementation, understanding the DFS approach can deepen your comprehension of recursive traversal of data structures. Hence, this article will first explain the DFS approach followed by the BFS approach.

Cycle Detection Algorithm (DFS Version)

Let's start with LeetCode Problem 207: "Course Schedule":

207. Course Schedule | 力扣 | LeetCode |

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.
java 🟢
// The function signature is as follows
boolean canFinish(int numCourses, int[][] prerequisites);

The problem is not difficult to understand: when can't we finish all the courses? When there is a circular dependency.

This scenario is quite common in real life. For example, when writing code and importing packages, we must design the code directory structure reasonably. Otherwise, circular dependencies will occur, and the compiler will report an error. The compiler uses a similar algorithm to determine whether your code can compile successfully.

When faced with dependency issues, the first thing to think about is converting the problem into a "directed graph" data structure. If there is a cycle in the graph, it means there is a circular dependency.

Specifically, we can consider courses as nodes in a directed graph, with node numbers 0, 1, ..., numCourses-1. The dependencies between courses are directed edges between nodes.

For example, if you must complete course 1 before taking course 3, there is a directed edge from node 1 to node 3.

We can generate a graph based on the prerequisites array given in the problem:

If we find a cycle in this directed graph, it means there are circular dependencies between the courses, and it will be impossible to complete all courses. Conversely, if there are no cycles, it means we can complete all courses.

To solve this problem, we first need to convert the input into a directed graph and then determine if there is a cycle in the graph.

How do we convert it into a graph? In our previous article Graph Structure Storage, we discussed two ways to store graphs: adjacency matrix and adjacency list.

Here, I'll use the adjacency list to store the graph. Let's start by writing a function to build the graph:

java 🟢
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // There are numCourses nodes in the graph
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        // Add a directed edge from 'from' to 'to'
        // The direction of the edge represents a dependency, i.e., course 'to' can only be taken after course 'from'
        graph[from].add(to);
    }
    return graph;
}

Now that we have constructed the graph, how do we check if there is a cycle in the graph?

It's very simple. The idea is to test your ability to traverse all paths in the graph. If I can traverse all the paths, then determining if a path forms a cycle becomes easy.

The article Graph Traversal with DFS/BFS explains how to use the DFS algorithm to traverse all paths in a graph. If you have forgotten, please review it because we will use it below.

Here, I will directly apply the DFS code template that traverses all paths. We will use a hasCycle variable to record whether there is a cycle. When we encounter a node that is already in the onPath set during traversal, it indicates a cycle, and we set hasCycle = true.

Based on this idea, let's look at the first version of the code (which might time out):

java 🟢
class Solution {
    // record the nodes in the recursion stack
    boolean[] onPath;
    // record whether there is a cycle in the graph
    boolean hasCycle = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        
        onPath = new boolean[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            // traverse all the nodes in the graph
            traverse(graph, i);
        }
        // as long as there are no cyclic dependencies, all courses can be finished
        return !hasCycle;
    }

    // graph traversal function, traverse all paths
    void traverse(List<Integer>[] graph, int s) {
        if (hasCycle) {
            // if a cycle has been found, no need to continue traversing
            return;
        }

        if (onPath[s]) {
            // s is already on the recursion path, indicating a cycle
            hasCycle = true;

            return;
        }
        
        // pre-order code position
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // post-order code position
        onPath[s] = false;
    }

    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        // code as seen previously
    }
}

Note that not all nodes in the graph are connected, so we need to use a for loop to start a DFS search algorithm from every node.

This solution is actually correct because it traverses all paths and can definitely determine if there's a cycle. However, this solution cannot pass all test cases and will time out. The reason is quite obvious: there is redundant computation.

Where is the redundant computation? Let me give you an example to explain.

Suppose you start traversing all reachable paths from node 2 and eventually find no cycle.

Now, suppose there is an edge from another node 5 to node 2. When you start traversing all reachable paths from node 5, you will definitely reach node 2 again. So, do you need to continue traversing all paths from node 2?

The answer is no. If you didn't find a cycle the first time, you won't find one this time either. Do you understand the redundant computation here? If you think there might be a counterexample, you can try drawing it out. In reality, there is no counterexample.

So, the solution is straightforward: if we find a node that has already been visited, we can skip it and avoid redundant traversal.

Here is the optimized code:

java 🟢
class Solution {
    // record nodes in the recursion stack
    boolean[] onPath;
    // record whether a node has been visited
    boolean[] visited;
    // record whether there is a cycle in the graph
    boolean hasCycle = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        
        onPath = new boolean[numCourses];
        visited = new boolean[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            // traverse all nodes in the graph
            traverse(graph, i);
        }
        // as long as there are no cyclic dependencies, all courses can be finished
        return !hasCycle;
    }

    // graph traversal function, traverse all paths
    void traverse(List<Integer>[] graph, int s) {
        if (hasCycle) {
            // if a cycle has been found, no need to traverse further
            return;
        }

        if (onPath[s]) {
            // s is already in the recursion path, indicating a cycle
            hasCycle = true;

            return;
        }
        
        if (visited[s]) {
            // no need to traverse already visited nodes
            return;
        }

        if (hasCycle) {
            // if a cycle has been found, no need to traverse further
            return;
        }

        // pre-order code position
        visited[s] = true;
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // post-order code position
        onPath[s] = false;
    }


    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        // code as seen previously
    }
}

Next, let's discuss another classic graph algorithm: Topological Sorting.

Topological Sorting Algorithm (DFS Version)

Consider LeetCode Problem 210 "Course Schedule II":

210. Course Schedule II | 力扣 | LeetCode |

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • All the pairs [ai, bi] are distinct.

This problem is an advanced version of the previous one. Instead of just determining whether all courses can be completed, it requires you to return a valid course order such that all prerequisite courses are completed before their respective courses.

The function signature is as follows:

java 🟢
int[] findOrder(int numCourses, int[][] prerequisites);

这里我先说一下拓扑排序（Topological Sorting）这个名词，网上搜出来的定义很数学，这里干脆用百度百科的一幅图来让你直观地感受下：

直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的，比如上图所有箭头都是朝右的。

很显然，如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。

但是我们这道题和拓扑排序有什么关系呢？

其实也不难看出来，如果把课程抽象成节点，课程之间的依赖关系抽象成有向边，那么这幅图的拓扑排序结果就是上课顺序。

首先，我们先判断一下题目输入的课程依赖是否成环，成环的话是无法进行拓扑排序的，所以我们可以复用上一道题的主函数：

java 🟢
public int[] findOrder(int numCourses, int[][] prerequisites) {
    if (!canFinish(numCourses, prerequisites)) {
        // not possible to finish all courses
        return new int[]{};
    }
    // ...
}

So, the key question is, how do we perform topological sorting? Do we need to use some advanced techniques again?

Actually, it's quite simple. Just reverse the result of a post-order traversal of the graph, and you'll get the topological sort result.

Do we need to reverse?

Some readers mention that they have seen topological sorting algorithms online that use the post-order traversal result without reversing it. Why is that?

You can indeed find such solutions. The reason is that the way they define the edges while constructing the graph is different from mine. In my graph, the direction of the arrow represents the "dependency" relationship. For example, if node 1 points to node 2, it means that node 1 is depended on by node 2, i.e., you must complete 1 before you can do 2, which aligns more with our intuition.

If you reverse this and define directed edges as "dependencies," then all edges in the entire graph are reversed, and you don't need to reverse the post-order traversal result. Specifically, you can change graph[from].add(to); in my solution to graph[to].add(from); to avoid reversing the result.

Let's look at the solution code. It builds on the cycle detection code by adding the logic to record the post-order traversal result:

java 🟢
class Solution {
    // record the postorder traversal result
    List<Integer> postorder = new ArrayList<>();
    // record if a cycle exists
    boolean hasCycle = false;
    boolean[] visited, onPath;

    // main function
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        // traverse the graph
        for (int i = 0; i < numCourses; i++) {
            traverse(graph, i);
        }
        // cannot perform topological sort if there is a cycle
        if (hasCycle) {
            return new int[]{};
        }
        // reverse postorder traversal result is the topological sort result
        Collections.reverse(postorder);
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = postorder.get(i);
        }
        return res;
    }

    // graph traversal function
    void traverse(List<Integer>[] graph, int s) {
        if (onPath[s]) {
            // found a cycle
            hasCycle = true;
        }
        if (visited[s] || hasCycle) {
            return;
        }
        // pre-order traversal position
        onPath[s] = true;
        visited[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // post-order traversal position
        postorder.add(s);
        onPath[s] = false;
    }

    // build graph function
    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        // code as seen earlier
    }
}

Although the code looks lengthy, the logic should be clear. As long as there are no cycles in the graph, we call the traverse function to perform a DFS traversal of the graph, record the post-order traversal results, and finally reverse the post-order traversal results to get the final answer.

So why is the reversed post-order traversal result the topological sort?

To avoid mathematical proof, I will use an intuitive example to explain. Let's talk about binary trees, which we have discussed many times in the context of binary tree traversal frameworks:

java 🟢
void traverse(TreeNode root) {
    // pre-order traversal position
    traverse(root.left)
    // in-order traversal position
    traverse(root.right)
    // post-order traversal position
}

When does post-order traversal of a binary tree occur? It happens after traversing both the left and right subtrees. In other words, the code for post-order traversal executes only after all nodes in the left and right subtrees have been added to the result list, and then the root node is added.

This characteristic of post-order traversal is crucial. The foundation of topological sorting is post-order traversal because a task can only start after all tasks it depends on have been completed.

You can think of a binary tree as a directed graph where the edges point from parent to child nodes, as shown in the figure below:

In a standard post-order traversal, the root node appears at the end. By reversing the traversal result, you get the topological sorting result:

I know some readers might ask, what is the relationship between the reversed post-order traversal result and the pre-order traversal result?

For binary trees, it might seem like there's a relationship, but actually, there isn't any. Do not mistakenly think that the reversed post-order traversal result is equivalent to the pre-order traversal result.

The key difference between the two has been explained in Binary Tree Concepts (Overview). The post-order traversal code executes only after both the left and right subtrees have been traversed, which uniquely reflects the "dependency" relationship. Other traversal orders cannot achieve this.

Cycle Detection Algorithm (BFS Version)

Earlier, we discussed using the DFS algorithm with the onPath array to determine if a cycle exists; we also talked about using DFS with reverse postorder traversal for topological sorting.

In fact, the BFS algorithm can achieve these two tasks by using the indegree array to record the "in-degree" of each node. If you are not familiar with BFS, you can read the previous article Core Framework of BFS Algorithm.

The concepts of "out-degree" and "in-degree" are intuitive in directed graphs: if a node x has a edges pointing to other nodes and is pointed to by b edges, then node x has an out-degree of a and an in-degree of b.

Let's start with the cycle detection algorithm and directly look at the BFS solution code:

java 🟢
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // build the graph, directed edges represent "dependency" relationship
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        // construct the indegree array
        int[] indegree = new int[numCourses];
        for (int[] edge : prerequisites) {
            int from = edge[1], to = edge[0];
            // increase the indegree of node 'to'
            indegree[to]++;
        }

        // initialize the queue with nodes having zero indegree
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                // node 'i' has no indegree, i.e., no dependencies
                // can be used as a starting point for topological sort, add to queue
                q.offer(i);

            }
        }

        // record the number of nodes traversed
        int count = 0;
        // start the BFS loop
        while (!q.isEmpty()) {
            // dequeue node 'cur' and decrease the indegree of its adjacent nodes
            int cur = q.poll();
            count++;
            for (int next : graph[cur]) {

                indegree[next]--;
                if (indegree[next] == 0) {
                    // if the indegree becomes zero, it means all dependencies of 'next' have been visited
                    q.offer(next);
                }
            }
        }

        // if all nodes have been traversed, it means there is no cycle
        return count == numCourses;
    }

    // function to build the graph
    List<Integer>[] buildGraph(int n, int[][] edges) {
        // see above
    }
}

Let me summarize the BFS algorithm steps:

  1. Build the adjacency list: As before, the direction of the edge indicates a "dependency" relationship.

  2. Create an indegree array: This array records the in-degree of each node, where indegree[i] represents the in-degree of node i.

  3. Initialize the BFS queue: Add nodes with an in-degree of 0 to the queue first.

4. Start the BFS loop: Continuously dequeue nodes, reduce the in-degree of adjacent nodes, and add nodes with a new in-degree of 0 to the queue.

5. Check for cycles: If all nodes are visited (count equals the number of nodes), there is no cycle. Otherwise, a cycle exists.

Here's an illustration to help you understand. In the following diagram, the numbers in the nodes represent their in-degrees:

After initializing the queue, nodes with an in-degree of 0 are added first:

Start the BFS loop, dequeue a node from the queue, reduce the in-degree of adjacent nodes, and add newly produced nodes with an in-degree of 0 to the queue:

Continue dequeuing nodes and reducing the in-degree of adjacent nodes. This time, no new nodes with an in-degree of 0 are produced:

Continue dequeuing nodes, reducing the in-degree of adjacent nodes, and adding newly produced nodes with an in-degree of 0 to the queue:

Continue dequeuing nodes until the queue is empty:

At this point, all nodes have been visited, indicating there is no cycle in the graph.

Conversely, if some nodes are not visited following the above BFS logic, a cycle exists.

For example, in the following case, the queue initially contains only one node with an in-degree of 0:

After dequeuing this node and reducing the in-degree of adjacent nodes, the queue is empty, but no new nodes with an in-degree of 0 are added, causing the BFS algorithm to stop:

As you can see, if some nodes are not visited, it indicates a cycle in the graph. Now, looking back at the BFS code, you should easily understand the logic.

Topological Sorting Algorithm (BFS Version)

If you understand the cycle detection algorithm using BFS, you can easily derive the topological sorting algorithm using BFS since the order in which nodes are traversed is the result of the topological sort.

For example, in the first example mentioned earlier, the value in each node in the following diagram represents the order in which they are queued:

Obviously, this order is a feasible result of topological sorting.

Therefore, we can slightly modify the cycle detection algorithm using BFS to record the order of node traversal to obtain the result of the topological sort:

java 🟢
class Solution {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Build the graph, same as in cycle detection algorithm
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        // Calculate in-degrees, same as in cycle detection algorithm
        int[] indegree = new int[numCourses];
        for (int[] edge : prerequisites) {
            int from = edge[1], to = edge[0];
            indegree[to]++;
        }

        // Initialize the queue with nodes having in-degree of 0, same as in cycle detection algorithm
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.offer(i);

            }
        }

        // Record the topological sort result
        int[] res = new int[numCourses];
        // Record the order of traversed nodes (index)
        int count = 0;
        // Start executing BFS algorithm
        while (!q.isEmpty()) {
            int cur = q.poll();
            // The order of nodes being dequeued is the topological sort result
            res[count] = cur;
            count++;
            for (int next : graph[cur]) {

                indegree[next]--;
                if (indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }

        if (count != numCourses) {
            // A cycle exists, topological sort is not possible
            return new int[]{};
        }
        
        return res;
    }

    // Function to build the graph
    List<Integer>[] buildGraph(int n, int[][] edges) {
        // See above
    }
}

Generally, graph traversal algorithms require a visited array to prevent revisiting nodes. In this BFS algorithm, the indegree array serves the function of the visited array. Only nodes with an indegree of 0 can be enqueued, ensuring there are no infinite loops.

Alright, we've covered the BFS implementations for cycle detection and topological sorting. Here's a thought-provoking question for you:

For the BFS-based cycle detection algorithm, if you were asked to identify the specific nodes that form a cycle, how would you implement it?

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode力扣
310. Minimum Height Trees310. 最小高度树
-剑指 Offer II 113. 课程顺序
上次编辑于: