Course Schedule I II

Leave a comment

December 19, 2016 by oneOokay

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices.


I 和 II的区别:I判断是否能修完课; II输出修课的顺序.

I:

DFS:判断是否存在circle决定了课程是否能够修完

  1. DFS确认能够到达每个点(错误,并不需要到达每个点。如果存在不能到达的点说明那个课程没有前置课,直接修就可以了)
  2. DFS判断是否存在circle决定了课程是否能够修完.有circle,不能修完.没circle,可以休完.
  3. 怎么确认是否存在circle(在dfs里面用一个visited)
    • 构建一个HashMap<Integer, ArrayList>, ArrayList为所有的以key为前置课的课程(这里因为要用到DFS递归,所以数组更加方便,直接用ArrayList[],不用HashMap)

所以DFS的思路是:

  1. 构建一个ArrayList[]来存前置课的mapping关系,ArrayList为所有的以i为前置课的课程.也就是所有i之后的课程.在有向图graph里面就是neighbors.
  2. 构建一个boolean[]来存该课程是否被访问过了,用来看有没有circle
  3. for-loop对所有课程进行dfs:dfs传入ArrayList[], visited和当前课程i,dfs返回值为boolean。如果找到了cycle(遇到了visited),说明这个课程不能做完成。
  4. helper method里面对当前visited的点的visited的值要进行toggle.这样的话在主函数的for loop里面每次开始help的时候,visited都是false.这里的visited其实就是从主函数的forloop当前的点开始的一条path上是否visited了. (注意这里要跟II对比).

BFS/拓扑排序:用拓扑排序来判断这个组成的图是否是一个valid DAG(Directed Acyclic Graph)有限的有向无环图。

  • DAG:In mathematics and computer science, a directed acyclic graph (DAG i/ˈdæɡ/), is a finite directed graph with no directed cycles.

所以如果最终所有Node的degree都是0,说明他就是一个valid DAG,就说明这个课是可以完成的。

重新理一下拓扑排序的BFS算法,当node的degree==0的时候,当前node会被加入到queue中。所以如果存在回路的话,那么不是所有的node都能够degree变成0被放到queue里面。所以我们可以通过queue 处理的node的总数与numCourse相比,如果他们相等,就说明图是valid DAG,return true;否则return false。

而且这个BFS也能够用来解Course Schedule II直接输出排序。这个就可以直接作为模板了。

DFS:时间复杂度O(V+E),空间:O(V)

public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0 
|| prerequisites[0].length == 0){
return true;
}
ArrayList[] graph = new ArrayList[numCourses];
for(int i = 0; i < numCourses; i ++){
graph[i] = new ArrayList();}

for (int i = 0; i < prerequisites.length; i ++){
graph[(prerequisites[i][1])].add(prerequisites[i][0]);}

boolean[] visited = new boolean[numCourses];
for (int i = 0; i < numCourses; i ++){
if (!dfs(graph, visited, i)) //这里其实每次开始if dfs的时候,visited都是false
return false;
}
return true;
}

private boolean dfs(ArrayList[] graph, boolean[] visited, int i){
if (visited[i]) return false;
visited[i] = true;
ArrayList children = graph[i];
for(int child : children){
if (!dfs(graph, visited, (int)child))
return false;
}
visited[i] = false;//toggle
return true;
}

BFS:拓扑排序:时间复杂度O(V+E):边+点

public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0){
            return true;
        }
        
        ArrayList[] graph = new ArrayList[numCourses];
        for(int i = 0; i < numCourses; i ++){
             graph[i] = new ArrayList();
         }
        int[] degrees = new int[numCourses];         
        //construct the graph: dot -> dot: graph和入度可以同时计算,互不影响
        for(int i = 0; i < prerequisites.length; i ++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            degrees[prerequisites[i][0]] ++;//入度
        }
        Queue queue = new LinkedList<>();
        
        for (int i = 0; i < numCourses; i ++){
            if (degrees[i] == 0) {
                queue.offer(i);
            }
        }
        int num = 0;
        while(!queue.isEmpty()){
            int cur = queue.poll();
            num ++;
            for(int i = 0; i < graph[cur].size(); i ++){
                int index = (int)graph[cur].get(i);//这里要转int
                degrees[index] --;
                if (degrees[index] == 0){
                    queue.offer(index);
                }
            }
        }
        return num == numCourses;
    }

II:按顺序输出课程
DFS : (注意跟I进行对比)

  • 用一个stack来存排序,传入helper method里面.最终stack会包含所有的点.pop出来的顺序就是课程的顺序.
  • 一个boolean[] added:这里的意义是,是否已经在stack里面了的意思.这个added不能够用来判定是否存在环.而且这个boolean array的值不被toggle.因为加入stack就是加入了.只有在最后一步输出结果的时候会被pop.在helper method之后进行赋值.
  • 另一个boolean[] visited用来track 主函数里面for loop help method 对当前node进行DFS的一条path,点是否已经存在于这个path里面了.用这个boolean来进行是否存在闭环的判定.所以这个要进行toggle.因为每次main method for loop开始的时候,这个visited里面都应该为false.
  • 当helper method return false的时候,说明存在闭环.
public int[] findOrder(int num, int[][] prereq) {
 int[] res = new int[num];
 if(prereq == null || prereq.length == 0 || prereq[0].length == 0) {
 for (int i = 0; i < num; i ++)
 res[i] = i;
 return res;
 };
 
 ArrayList[] graph = new ArrayList[num];
 for (int i = 0; i < num; i ++){
 graph[i] = new ArrayList<Integer>();
 }
 for (int i = 0; i < prereq.length; i ++){
 graph[prereq[i][1]].add(prereq[i][0]); 
 }
 boolean[] added = new boolean[num];
 boolean[] visited = new boolean[num];
 Stack<Integer> stack = new Stack<>();
 for (int i = 0; i < num; i ++){
 if(!helper(graph, added, visited, i, stack))
 return new int[0];
 }
 
 int i = 0;
 while (!stack.isEmpty()){ //pop出的顺序就是拓扑排序顺序
 res[i ++] = (int)stack.pop();
 }
 return res;
 }
 
 private boolean helper(ArrayList[] graph, boolean[] added, 
boolean[] visited, int curCourse, Stack<Integer> stack){
//当前的点已经被加到stack里了.pass.且return true.
 if (added[curCourse]) return true; 
//当前的点已经在当前的path里,形成了一个闭环.return false
 if (visited[curCourse]) return false;
//正在访问当前点,于是在for loop之前把它的visited mark为true
 visited[curCourse] = true;
 for (int i = 0; i < graph[curCourse].size(); i ++){
 if (!helper(graph,added,visited, (int)graph[curCourse].get(i), stack))
 return false; //存在环,直接返回false;
 }
 //DFS结束了,对visited的值进行toggle
 visited[curCourse] = false;
 stack.push(curCourse);
//for loop这一层的DFS结束了.点被加入到stack里面,mark added true
 added[curCourse] = true; 
 return true;//最终没有找到闭环,返回true
 } 

BFS: 与I相差不大,基本一样. queue poll出来的顺序就是拓扑排序的顺序.

public int[] findOrder(int num, int[][] prereq) {
 int[] res = new int[num];
 if(prereq == null || prereq.length == 0 || prereq[0].length == 0) {
 for (int i = 0; i < num; i ++)
 res[i] = i;
 return res;
 };
 
 ArrayList[] graph = new ArrayList[num];
 for (int i = 0; i < num; i ++){
 graph[i] = new ArrayList<Integer>();
 }
 int[] degrees = new int[num];
 for (int i = 0; i < prereq.length; i ++){
 graph[prereq[i][1]].add(prereq[i][0]); 
 degrees[prereq[i][0]] ++;
 }
 Queue<Integer> queue = new LinkedList<>();
 
 for (int i = 0; i < num; i ++){
 if (degrees[i] == 0)
 queue.offer(i);
 }
 int index = 0;
 while (!queue.isEmpty()){
 int cur = queue.poll();
 res[index ++] = cur;
 for (int i = 0; i < graph[cur].size(); i ++){
 int next = (int)graph[cur].get(i);
 degrees[next] --;
 if (degrees[next] == 0)
 queue.offer(next);
 }
 }
 if (index != num) return new int[0];
 return res;
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: