Course Schedule and Topological Sort

Course Schedule Problem

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

This problem can be solved in multiple ways, one simple and straightforward way is Topological Sort.

Topological Sort.

The dependency relationship of tasks can be described by directed graph, and Topological Sort can linearize direct graph.

Does topological sort applies to every graph?

No, Topological sort can only be applied to DAG, when there are cycle in the graph, it could not be used.

How does topological sort work?

The critical step of topological is to find out the vertex that goes not have out degree, which we call it sink or minimal vertex. Then we ignore edges from any vertex to this sink vertex.

In summary topological sort works in this way:

topologicalSort(digraph):
    for i = 1 to |V|
        find minimal vertex
        num(v) = i
    delete v and all associated edges from digraph

It’s hard to delete the node from the graph, while if we are sure the successor node of current nodes has all been processed, we don’t need to delete it at all. This reminds us of tail recursion and the following code implements the algorithm we describe above:

TS(v)
    num(v) = i++
    for u in v.neighbors:
        if num(u) == 0
            TS(u)

        else if TSNum(u) == 0
            return false // Cycle detected
    TSNum(v) = j++

topologicalSorting(diagraph)
    for v in all vertex:
        num(v) = TSNum(v) = 0

    i = j = 1
    while any vertex have num(v) == 0
        TS(v)

    return vertex order by TSNum

We need to pay attention to two places in the above algorithm:

  • How does the ordering work?

The critical line is: TSNum(v) = j ++, meaning we increase the TSNum value of a node only after we finished visited all it neighboring nodes, which guarantees that the value of TSNum(v) > TSNum(u) where u in v.neighbors.

  • How does the cycle detection work?

The critical line is: else if TSNum(u) == 0. TSNum(v) == 0 means it has already been visited but has not yet returned, which means we can revisit that node starting from that node, which is a symbol of cycle.

Solution to Course Schedule problem

The question apparently can be solved by Topological Sort, but we probably don’t want to implement the complex DFS algorithm, while in the same time, we can use BFS to calculate order as well. We need to calculate the indegree each node, those course that have indegree of zero can start first. And each time we find an edge, subtract the indegree of all its neighbors.

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // calculate indegree
        int[] indegree = new int[numCourses];

        //To adjacent list
        Map<Integer, List<Integer>> adjac = new HashMap<Integer, List<Integer>> ();
        for (int[] edge : prerequisites) {
            int prev = edge[0];
            int dep = edge[1];
            if (adjac.containsKey(prev)) {
                adjac.get(prev).add(dep);
            } else {
                List<Integer> list = new ArrayList<Integer> ();
                list.add(dep);
                adjac.put(prev, list);
            }
            indegree[dep] ++;
        }

        // track the order of each nodes
        int count = numCourses - 1;
        int[] order = new int[numCourses];

        // bfs to get the order of all the nodes
        Queue<Integer> queue = new LinkedList<Integer> ();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        } 

        while (queue.size() != 0) {
            int course = queue.poll();
            order[count--] = course;
            if (adjac.containsKey(course)) {
                List<Integer> deps = adjac.get(course);
                for (int dep : deps) {
                    indegree[dep] --;
                    if (indegree[dep] == 0) {
                        queue.offer(dep);
                    }
                }
            }
        } 

        if (count != -1) {
            return new int[0];
        }

        return order;
    }

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