Topological Sort in JAVA


  • 0
    S

    I use HashMap to store the list of adjacent vertices (courses).
    The comments are included, hope it helps!

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[] indegree = new int[numCourses]; //record the in-degree of each vertex
            HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>(); //map each vertex to its list of adjacent vertices
            for(int i = 0; i < numCourses; i++) 
            map.put(i, new LinkedList<Integer>());
            for(int[] edge : prerequisites){
                indegree[edge[0]]++;
                map.get(edge[1]).add(edge[0]);
            }
            Queue<Integer> zeroVerts = new LinkedList<Integer>(); //determine all vertices with zero in-degree
            for(int i = 0; i < numCourses; i++)
                if(indegree[i] == 0) 
                   zeroVerts.offer(i);
            int courseOrder = 0; //number of courses could be put into the topological order
            while(!zeroVerts.isEmpty()){
                int course = zeroVerts.poll(); //choose a vertex with 0 in-degree
                courseOrder++;
    	        for(int c : map.get(course)){ //"remove" vertex by updating its neighbors
    	            indegree[c]--;
    	            if(indegree[c] == 0) //add any vertex that now has 0 in-degree to the queue
    	               zeroVerts.offer(c);
    	        }
            }
            return courseOrder == numCourses; //if we haven't added all of the vertices to the topo order, there's a cycle
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.