New answers tagged graph-traversal
1
1) In answer to the semantic question "Wouldn't 'breadth first' mean 'Process children first, then process parent'?"
This question is a duplicate of the following: What is the meaning of 'breadth' in breadth first search?
2) In answer to the technical question "Why is the current node printed (and processed) first before its children are processed?"...
0
Trees are acyclic. If you have for instance the directed graph $(1,2),(2,1)$ and try running the algorithm with marking visited after the recursive call, you will get a stack overflow. Or for an undirected graph you can consider a triangle $(1,2),(2,3),(1,3)$ which will result in the same thing. For acyclic graphs this issue won't arise so mark visited in ...
0
For post-order see: https://en.wikipedia.org/wiki/Tree_traversal#Post-order.
The algorithm just says perform step 2 using BFS traversal rather than DFS traversal, and then let $L$ be vertices of BFS in the postorder. After that perform step 3 to compute SCCs.
2
Here is one such example of undirected weighted graph.
Top 50 recent answers are included
