Given a directed acyclic graph with $n$ nodes labeled from $1$ to $n$, what is an efficient way to produce the unique topological ordering with lower labeled nodes prioritized over higher labeled?

In other words: in the ordering the node labeled $1$ appears as early as possible, and if there are many such orders, among them choose the order(s) where the node labeled $2$ appears as early as possible, and so on producing the unique order in the end.

I tried to apply Kahn's algorithm. Instead of picking nodes arbitrary, choose ancestors of node $1$ from nodes with in-degree zero. Among those, choose ancestors of node 2, and so on. However, I don't know whether this idea can be efficiently implemented.

Choosing the lowest labeled node does not work: a counterexample is the DAG with the nodes 1, 2, 3 and 4, and edges 3 -> 1, 2 -> 4 and 4 -> 1. If we choose the lowest-numbered node, we get the ordering (2,3,1,4) but the ordering we look for is (3,1,2,4).

  • $\begingroup$ What are the constraints on your running time? Does this algorithm have to run in $O(|V|+|E|)$? $\endgroup$ – Discrete lizard Apr 24 '18 at 17:49
  • $\begingroup$ @Discretelizard Not necessarily in $O(|V|+|E|)$. A logarithmic factor is allowed for example but anything quadratic is too slow. $\endgroup$ – eLibrarian Apr 24 '18 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.