Home > OS >  no back edges in topological ordering of DAGs
no back edges in topological ordering of DAGs

Time:06-25

When doing a topological ordering on a DAG (directed acyclic graph) using depth-first traversal, it is important to notice that no back edges are present since the graph does not have cycles. But why is this important, why would back edges cause a problem when doing the topological ordering on a depth-first manner?

CodePudding user response:

If there is a back edges there could be a directed cycle in the graph.

If there is a cycle a depth-first traversal will at some point enter the cycle and than go deeper and deeper without end.

You can fix this by detecting already visited nodes and avoid following them again (if already visited).

  • Related