Topological sorting algorithms

Question

I am building a dependency based scheduler where my tasks/nodes form a directed acyclic graph. I have the following constraints and am trying to decide on the most appropriate algorithm:

1. New tasks can be added (with or without dependencies) at any time
2. Some tasks can run in parallel

Two algorithms are mentioned repeatedly with regards to topological sorting; depth first search and Kahn's algorithm.

• What are the pro's and con's of these two algorithms?
• Is one algorithm objectively better for my scenario?
• Is there an alternate that better fits my scenario?

I have one further question about vocabulary. Given dependencies such as:

c->b
b->a
e->d

Is this considered to be a single directed acyclic graph, 2 acyclic graphs (since e and d are not dependent on the other tasks) or an acyclic graph with sub acyclic graphs?

Answer 1

I think you misunderstood these algorithms.

Depth First Search: So the Depth First Search algorithm (I looked it up on wikipedia. There it is actually called an algorithm. I would rather call it a strategy) is an algorithm for traversing through a graph. So to visit all nodes. It will not return you the topological order of your graph!!

Kahn's algorithm: Kahn's algorithm on the other hand, is the right algorithm for your problem. It will return you the topoligical order if there is one. The algorithm has an asymptotic running time of O(m+n) where m is the amount of edges and n is the amount of vertices in your graph. I do not think, that you will find a better algorithm for that problem.

Vocabulary: In your example, you have one DAG (directed acyclic graph) with two weakly connected components.

EDIT: After your mention of an algorithm based on Depth First Search: For the asymptotic running time, it does not matter which algorithm you are using. Both are in O(m+n). Also concerning the storage, it actually should not matter.