algorithmdirected-acyclic-graphsgraph-traversal

Traverse directed graph without "catching up"


I have a (acyclical) directed graph, which I want to traverse in the right order. enter image description here

The arrows indicate dependencies - a node should only be visited if all previous nodes are already visited.

I tried both a "depth first" and "breadth first" approach. (Not sure if I can call them exactly that, since it's not an actual tree).

"depth first": enter image description here

"breadth first": enter image description here

With both approaches, I don't get the proper order - the leftmost node is visited before another node is visited.

I think I see what's going wrong - the "breadth" is not so relevant, since there can be an arbitrarily number of nodes on each branch. Just not sure how to fix this?

Edit: A right solution for my problem would be: enter image description here It should ensure that every arrow goes from a lower to a higher number


Solution

  • Have a queue of nodes to visit. Initially populate it with the starting vertex.

    Associate a count of predecessors_visited for each node, initially 0.

    Then, repeatedly: