Topological Sort

Leetcode had another good question this morning which involved using topological sort, which I hadn’t heard of until today. According to the wiki: “a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering”. In other words, given a bunch of vertices and directed edges, a topological sort finds an ordering where parent nodes always occur before child nodes in the graph. There may be more than one correct answer to this type of problem.

For example, the graph:

could have multiple answers. According to wikipedia:

  • 5, 7, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
  • 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
  • 5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first)
  • 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
  • 5, 7, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)
  • 3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)

are all valid topological sorts.

Now that we know a bit about topological sorting, let’s move on to the question.

The Question

The question is asking about prerequisites for courses. It asks if there is a valid ordering to take the classes based upon the list of prereqs. In other words, is there a valid way to topologically sort the given nodes based on the edges of prerequisites.

A Solution

I adapted the topological sort from Wikipedia in my solution, I also built a simple Node class which has a status to help with the sort. This is an accepted solution:

The main thing that’s different here is that my visit function will return False if it ever encounters a node marked T in any of its recursive calls. In other words, if there is a cycle the entire function will return False and my canFinish function will also return False. If we can successfully traverse our nodes, that means that there is a valid topological sort and we can return True. Note how easily this could be changed to instead return a valid topological sort.

Complexity

I build the list of nodes, which will happen in O(n) time where n is the number of courses. I also have to add all of the edges, which will happen in O(e) time where e is the number of prerequisite edges. I then perform the topological sort which is linear with regard to n. I can’t think of a valid graph where e > n, but an invalid graph could contain more prerequisite edges than the number of courses. Therefore, I suggest that the time complexity is O(max(n, e)).

For space, I store n nodes and e edges. The edges are not necessarily dependent on the number of nodes. I suggest the space complexity is O(n+e).

Leave a Reply

Your email address will not be published. Required fields are marked *

*