I know DFS is good for some problems and BFS is good for some other problems but if something can be solved using DFS, can it be solved (maybe less optimally) with BFS (or vise versa)? And is there a proof for it? Thanks!

CodePudding user response：

No.

Shortest path is the canonical example of something that can be solved easily with BFS. But with DFS you either have to accept the possibility of endless loops, or else avoid revisiting nodes and fail to find shortest paths in many cases.

Examples going the other way are harder to find. But for example the Hopcroft-Tarjan algorithm for planarity testing relies on the fact that in a DFS you know properties of the entire path to the present node. And that context you do not have in a BFS.