Traverse directed graph without "catching up"

Question

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

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":

"breadth first":

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: It should ensure that every arrow goes from a lower to a higher number

Answer 1

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:

• take a node from the queue
• increment predecessors_visited for all its descendants.
• add any descendant whose predecessors_visited == indegree to the queue.