我在关于调度课程的leetcode上做了一个问题（https://leetcode.com/problems/course-schedule/description/#=）
但出于某种原因，我似乎真的很困惑自己 . 我相信这个问题等同于确定它作为图形的表示是否具有拓扑排序 . 但是只有有向非循环图才能进行拓扑排序 - 所以我们要么必须事先检查它是否有一个循环，要么在搜索它并执行拓扑排序时检查它是否有循环 .
发布的使用DFS的解决方案之一如下：
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList[] graph = new ArrayList[numCourses];
for(int i=0;i<numCourses;i++)
graph[i] = new ArrayList();
boolean[] visited = new boolean[numCourses];
for(int i=0; i<prerequisites.length;i++){
graph[prerequisites[i][1]].add(prerequisites[i][0]);
}
for(int i=0; i<numCourses; i++){
if(!dfs(graph,visited,i))
return false;
}
return true;
}
private boolean dfs(ArrayList[] graph, boolean[] visited, int course){
if(visited[course])
return false;
else
visited[course] = true;;
for(int i=0; i<graph[course].size();i++){
if(!dfs(graph,visited,(int)graph[course].get(i)))
return false;
}
visited[course] = false;
return true;
}
}
看起来它所做的就是检查之前是否已经访问过节点（课程） - 但是之前是否有可能访问过一个节点但是图形中没有一个循环？这段代码如何检查没有循环，以便它知道它有拓扑排序？