[LC 207] Course Schedule

Both DFS and BFS can solve the problem. Edges can be stored in Map<Integer, List<Integer>> map. Same idea and very similar code for [LC 210] Course Schedule II.
DFS:
    public boolean canFinish(int n, int[][] prerequisites) {
        // store edges to map
        for (int i = 0; i < prerequisites.length; i++) {
            insertMap(prerequisites[i][0], prerequisites[i][1]);
        }
        // maintain a set to store all nodes that have been visited
        Set<Integer> visited = new HashSet<Integer>();
        for (int i = 0; i < n; i++) {
            if (visited.contains(i)) continue; // there may be multiple components in the network
            visited.add(i);
            Set<Integer> path = new HashSet<Integer>();
            path.add(i);
            // given head and tail to track the current path, if there is a loop than return false, otherwise continue search other connected components
            if (!helper(Integer.MIN_VALUE, i, visited, path)) return false;
        }
        return true;
    }
    private boolean helper(int head, int tail, Set<Integer> visited, Set<Integer> path) {
        if (!map.containsKey(tail)) return true; // current path comes to the end without encountering loop
        List<Integer> nexts = map.get(tail);
        for (int next : nexts) {
            if (path.contains(next)) return false; // current path contains loop
            path.add(next);
            visited.add(next);
            if (!helper(tail, next, visited, path)) return false;
            path.remove(next);
        }
        return true;
    }
BFS:
    public boolean canFinish(int n, int[][] prerequisites) {
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        Queue<Integer> q = new LinkedList<Integer>();
        int[] degree = new int[n];
        for (int i = 0; i < prerequisites.length; i++) {
            map.putIfAbsent(prerequisites[i][1], new ArrayList<Integer>());
            map.get(prerequisites[i][1]).add(prerequisites[i][0]);
            // find nodes that depend on nothing, i.e. start of each connected component
            degree[prerequisites[i][0]]++;
        }
        for (int i = 0 ; i < n; i++) {
            if (degree[i] == 0) {
                q.add(i); // add all courses that depend on nothing
            }
        }
        int count = 0; // traverse the graph and count how many nodes are visited
        while (!q.isEmpty()) {
            int course = q.poll();
            count++; // total number of the nodes that can be reached from those depend on nothing
            if (!map.containsKey(course)) continue;
            List<Integer> list = map.get(course);
            for (int c : list) {
                degree[c]–; // if the last node is the only dependence, then the current node is a new start
                if (degree[c] == 0) {
                    q.add(c);
                }
            }
        }
        return count == n; // if all nodes can be visited from the start, then the courses can be finished
    }
The logic of comparing “count” and the number of courses:
For graphs with loops, all nodes in the nodes have to depends on something, thus will never be visited. Consider the two cases below:
(1,0), (2,1), (3,2), (3,1): 1 depends on 0, 2 depends on 1, …
(0,1), (2,1), (3,2), (3,1)
For case 1, count is 1 in the end, since node 0 depends on nothing, but its only child node depends on other nodes in the loop.
For case 2, count is 0 in the end, since all nodes depend on something else.
The running time shows that BFS is much faster, why:
Consider the graph which contains two branches:
1–>2–>4–>5–>6–>7
1–>3–>4–>5–>6–>7
If using DFS, our traversal is 1–>2–>4–>5–>6–>7–>3–>4–>5–>6–>7, when that is done, we finish searching for loops in the graph. If using BFS, our traversal is 1–>2–>3–>4–>5–>6–>7, since only when both 2 and 3 are polled from the queue, node 4 has no dependence and can be added to the queue, so that the long list from 4 to 7 is visited only once.
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