CODEWITHSUNDEEP
algorithmgraphscheduling
Tom
Tom

Reputation: 719

Topological sorting algorithms

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.

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?

Upvotes: 4

Views: 904

Answers (1)

Andreas
Andreas

Reputation: 309

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.

Upvotes: 1

Related Questions