本文共 1720 字，大约阅读时间需要 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/