Java Topological Sort with BFS


  • 0
    C

    Topological sort using BFS by building graph, indegrees count for each node, and set of classes taken.

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Map<Integer, Set<Integer>> graph = new HashMap<>();
            Map<Integer, Integer> indegrees = new HashMap<>();
            Set<Integer> taken = new HashSet<Integer>();
            
            // initialize indegrees and graph
            for (int i = 0; i < numCourses; i++) {
                indegrees.put(i, 0);
                graph.put(i, new HashSet<Integer>());    
            }
            
            // create edges on graph and indegrees count for each node
            for (int i = 0; i < prerequisites.length; i++) {
                int clazz = prerequisites[i][0];
                int prereq = prerequisites[i][1];
            
                graph.get(prereq).add(clazz);
                indegrees.put(clazz, indegrees.get(clazz) + 1);
            }
            
            // mark every node with 0 indegrees as taken until no more nodes with 0 indegrees
            boolean hasNextRoot = true;
            while (hasNextRoot) {
                hasNextRoot = false;
                Set<Integer> indegreesKeys = indegrees.keySet();
                for (Integer key : indegreesKeys) {
                    int indegree = indegrees.get(key);
                    if (indegree == 0) {
                        hasNextRoot = true;
                        taken.add(key);
                        
                        // reduce indegree count for all adjacent nodes
                        Set<Integer> adj = graph.getOrDefault(key, new HashSet<>());
                        for (Integer dep : adj) {
                            indegrees.put(dep, indegrees.get(dep) - 1);
                        }
                        
                        indegrees.put(key, -1);
                    }
                }
            }
            
            // if there is a cycle, not every course will be taken
            return taken.size() == numCourses;
        }
    }
    

Log in to reply
 

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