本文共 1759 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要判断是否可以完成所有课程的学习，给定每门课程的先决条件。这个问题可以转化为图的环检测问题，其中每个课程是一个节点，先决条件是边。我们需要检测图中是否存在环，如果存在环，则无法完成所有课程的学习。

方法思路

我们可以使用深度优先搜索（DFS）来检测图中的环。DFS的思路是从一个节点开始，逐步深入到其所有后继节点，直到无法继续深入。在这个过程中，如果我们发现已经访问过的节点，说明存在环，从而返回false。否则，如果所有节点都被成功访问并处理，返回true。

具体步骤如下：

解决代码

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Solution {
    private List
   
    
     > adj;
    private byte[] visited;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < numCourses; i++) {
            for (int j : prerequisites[i]) {
                adj.get(i).add(j);
            }
        }
        visited = new byte[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (!dfs(i)) {
                    return false;
                }
            }
        }
        return true;
    }
    private boolean dfs(int i) {
        if (visited[i] != 0) {
            return visited[i] == 1;
        }
        visited[i] = 2;
        for (int j : adj.get(i)) {
            if (!dfs(j)) {
                return false;
            }
        }
        visited[i] = 1;
        return true;
    }
}
    
   

代码解释

这种方法确保了我们能够在O(V + E)时间复杂度内完成环检测，其中V是节点数，E是边数。该算法适用于处理较大的节点数，因为它避免了递归深度过大的问题。

转载地址：http://nkru.baihongyu.com/