Hacker News new | ask | show | jobs
by gugagore 1319 days ago
What important property of DFS is missing if you just replace a stack with a queue?
1 comments

If you form a spanning tree by noting which edges where used during DFS traversal of undirected graph, then all of the edges not used will connect a node with it's ancestor and there will be no cross edges. It doesn't matter if all you care is traversing the graph in any order and maybe checking which parts are connected, but it is important for some of the more complex graph algorithms built on top of DFS.