leetcode第207题课程表

思考:

这是一个中等难度的题,但是我做了很久很久,有很多的问题想的都不透彻!图的深度遍历,这就是很经典的一个dfs,我发现我还没有养成这种分块处理问题的能力,基础也还差一些,像拓扑排序,这算是比较经典的算法了,

基本的思路:

• 根据数组建立一个linkedlist的临界表,把图先创建起来,再根据图进行一个深度优先遍历,在遍历的途中当我们发现这个节点已经走过了或者是已经形成了一个环,这时候,返回上一个递归函数继续遍历.

class Solution {
       boolean[] visited;
    boolean[] onPath;
    boolean hasCycle = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //这个题的水平其实还是不错的 判断有向图是否存在环
        List<Integer>[] lists = buildGraph(numCourses, prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            traverse(lists,i);
        }
        return !hasCycle;
    }

    /**
     * 建立一个图的方法
     * @param numCourses
     * @param prerequisites
     * @return
     */
    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }

        for ( int[] edges :prerequisites) {
            //把科目放在linkedlist里面  创建一个邻接表
            int from = edges[1];//这个一维数组里面肯定是有两个值的,根据根节点的位置创建的表的大小
            int to = edges[0];
            graph[from].add(to);
        }

        return graph;

    }

    void traverse(List<Integer>[] graph, int s) {
        //
        if (onPath[s]) {
            hasCycle = true;
        }
        if (visited[s] || hasCycle) {
            return;
        }
        //前序遍历代码的位置
        //将当前节点的遍历记为以标记
        visited[s] = true;
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph,t);
        }
        onPath[s] = false;
    }
}