Re:An aesthetically pleasing pathfinding visualizer
by Karliss on Sunday November 06, 2022 @04:36AM
(#33490782)
"Still technically a DFS" - No! The traditional textbook DFS visiting order has certain important properties. It's not just a "BFS" which uses stack and doesn't produce shortest path. There are more complex graph processing for finding strongly connected components, searching cutpoints and others which rely on proper DFS. Replacing DFS with this thing will result in completely wrong result. It is possible to implement a proper DFS non recursively, but it's a bit more trickier than just replacing queue with a stack in BFS.
[ Parent
| on HN ]
Re:An aesthetically pleasing pathfinding visualizer
by gugagore on Sunday November 06, 2022 @08:45AM
(#33492570)
What important property of DFS is missing if you just replace a stack with a queue?
Re:An aesthetically pleasing pathfinding visualizer
by Karliss on Sunday November 06, 2022 @03:10PM
(#33496544)
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.