How to traverse all nodes of a Directed Acyclic Graph in a specific order?

1
votes

I have a problem where I need to traverse ALL nodes of the Directed Acyclic graph in a specific order because some nodes/vertices are dependent on results of multiple other nodes/vertices.

In this case, DFS or BFS won't work.

What is the solution/algorithm/ threads for traversing a DAG like this?

Should I be also ordering the nodes? eg: That node which does not depend on anything else - is first, then Node A, then Node B, then C (which depends on Node A and Node B).. beforehand?

1
graphdirected-acyclic-graphs
We would have to know what specific order you're talking about, but if some nodes are dependent on others, that suggests you might be looking for a topological sorting of nodes. – beaker
More information is needed, like what is the nature of the dependency of B in A, and more important is that dependency know before traversing. Consider minimal reproducible example – c0der

1 Answers

1
votes

The answer was topological sort which can be implemented using

  • Kahn's algorithm
  • Depth-first search or
  • Parallel algorithms

Thanks @beaker