Hay un total de n cursos que debe tomar, etiquetados de 0 a n – 1. Algunos cursos pueden tener requisitos previos, por ejemplo, para tomar el curso 0 primero debe tomar el curso 1, que se expresa como un par: [0,1]. Dado el número total de cursos y una lista de pares de requisitos previos, ¿es posible que termine todos los cursos?
Por ejemplo, dado 2 y [[1,0]]hay un total de 2 cursos para tomar. Para tomar el curso 1 debería haber terminado el curso 0. Entonces es posible.
Para otro ejemplo, dado 2 y [[1,0],[0,1]]hay un total de 2 cursos para tomar. Para tomar el curso 1 debe haber terminado el curso 0, y para tomar el curso 0 también debe haber terminado el curso 1. Así que es imposible.
Análisis
Este problema se puede convertir en encontrar si una gráfica contiene un ciclo.
Solución Java 1 – BFS
Esta solución utiliza la búsqueda de respiración primero y es fácil de entender.
public boolean canFinish(int numCourses, int[][] prerequisites) { if(prerequisites == null){ throw new IllegalArgumentException("illegal prerequisites array"); } int len = prerequisites.length; if(numCourses == 0 || len == 0){ return true; } // counter for number of prerequisites int[] pCounter = new int[numCourses]; for(int i=0; i<len; i++){ pCounter[prerequisites[i][0]]++; } //store courses that have no prerequisites LinkedList<Integer> queue = new LinkedList<Integer>(); for(int i=0; i<numCourses; i++){ if(pCounter[i]==0){ queue.add(i); } } // number of courses that have no prerequisites int numNoPre = queue.size(); while(!queue.isEmpty()){ int top = queue.remove(); for(int i=0; i<len; i++){ // if a course's prerequisite can be satisfied by a course in queue if(prerequisites[i][1]==top){ pCounter[prerequisites[i][0]]--; if(pCounter[prerequisites[i][0]]==0){ numNoPre++; queue.add(prerequisites[i][0]); } } } } return numNoPre == numCourses; } |
Solución Java 2 – DFS
public boolean canFinish(int numCourses, int[][] prerequisites) { if(prerequisites == null){ throw new IllegalArgumentException("illegal prerequisites array"); } int len = prerequisites.length; if(numCourses == 0 || len == 0){ return true; } //track visited courses int[] visit = new int[numCourses]; // use the map to store what courses depend on a course HashMap<Integer,ArrayList<Integer>> map = new HashMap<Integer,ArrayList<Integer>>(); for(int[] a: prerequisites){ if(map.containsKey(a[1])){ map.get(a[1]).add(a[0]); }else{ ArrayList<Integer> l = new ArrayList<Integer>(); l.add(a[0]); map.put(a[1], l); } } for(int i=0; i<numCourses; i++){ if(!canFinishDFS(map, visit, i)) return false; } return true; } private boolean canFinishDFS(HashMap<Integer,ArrayList<Integer>> map, int[] visit, int i){ if(visit[i]==-1) return false; if(visit[i]==1) return true; visit[i]=-1; if(map.containsKey(i)){ for(int j: map.get(i)){ if(!canFinishDFS(map, visit, j)) return false; } } visit[i]=1; return true; } |
Video de clasificación topológica de Coursera.
