CourseScheduleBFS1.java

public boolean canFinishBfsTopoSort(int numCourses, int[][] prerequisites) {
    if (numCourses <= 1 || prerequisites.length == 0 || prerequisites[0].length == 0) {
        return true;
    }

    Map<Integer, Set<Integer>> graph = new HashMap<>();

    // could be extracted into a build graph function
    for (int i = 0; i < numCourses; i++) {
        graph.put(i, new HashSet<>());
    }

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

    int coursesRemaining = numCourses;
    Queue<Integer> queue = new LinkedList<>();

    // initialize
    for (Map.Entry<Integer, Set<Integer>> entry : graph.entrySet()) {
        // this is the reverse as the graph topological order, but it is the actual problem solving order
        // e.g., a->b, -> reads as depends on, meaning you have to finish b to do a, so it will print out b, a
        if (entry.getValue().size() == 0) { 
            queue.offer(entry.getKey());
            coursesRemaining--;
        }
    }

    // BFS
    while (!queue.isEmpty()) {
        int key = queue.poll();
        System.out.println("** key: " + key);
        for (Map.Entry<Integer, Set<Integer>> entry : graph.entrySet()) {
            Set<Integer> curDependencies = entry.getValue();

            if (curDependencies.contains(key)) {
                curDependencies.remove((Integer)key); // need to cast or else it will be remove(int index)
                if (curDependencies.size() == 0) { // immediately check to avoid another loop
                    queue.offer(entry.getKey());
                    coursesRemaining--;
                }
            }
        }
    }

    return coursesRemaining == 0;
}