Search code examples
directed-acyclic-graphstopological-sort

Topological Ordering : Graphs

I had a look at a similar question about topological ordering but was still unsure about the concept.

There is this questions that I am unsure about.

Assuming the DFS visits adjacent nodes in alphabetical order, nd a topological order of
the nodes v 2 V by running the DFS on this DAG G from the source (zero in-degree)
node.

Graph

For the following I got a topological order of (a, d, c, e, b, f). Would this be the correct topological ordering?

Solution

  • Well the there can be multiple correct orderings for a topological sort and the one you have is correct. The thing to bear in mind is that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering so in your graph, consider the edge a->c (a must come before c) c->e (c must come before e) e->f (e must come before f) and so on.