207. 课程表(Java、DFS)

要点是判断该图是否成环
DFS步骤：
1. 建立有向图

List[] buildGraph(int numCourses, int[][] prerequisites)

2. 遍历有向图判断是否成环

void traverse(List[] graph, int s)

DFS：

class Solution {
    boolean[] visited;
    boolean[] onPath;
    boolean hasCycle;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List[] graph = buildGraph(numCourses,prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        for(int i = 0;i
            travel(graph,i);
        }
        return !hasCycle;
    }

    List[] buildGraph(int numCourses,int[][] prerequisites){
        List[] graph = new LinkedList[numCourses];
        for(int i = 0;i
            graph[i] = new LinkedList<>();
        }
        for(int[] edge:prerequisites){
            int to = edge[0];
            int from = edge[1];
            // 添加一条从 from 指向 to 的有向边
            // 修完课程 from 才能修课程 to
            graph[from].add(to);
        }
        return graph;
    }

    void travel(List[] graph,int start){
        if(onPath[start]){
            hasCycle = true;
            return;
        }

        if(visited[start]||hasCycle){
            return;
        }
        //类似回溯，在进入节点start的时候将 onPath[s] 标记为 true，离开时标记回 false，如果发现onPath[start]已经被标记，说明出现了环。
        visited[start] = true;
        onPath[start] = true;
        for(int w:graph[start]){
            travel(graph,w);
        }
        onPath[start] = false;
    }
}

BFS：

1. 图的建立

List[] buildGraph(int numCourses, int[][] prerequisites)

2. 建立入度数组、BFS
   将入度为0的from节点入队，在出队时，将from节点对应的to节点的入度-1，判断入度是否为0，将入度为0的节点加入队列
   如果最终所有节点都被遍历过（count 等于节点数），则说明不存在环，反之则说明存在环。