Compare breadth-first search (BFS) and depth-first search (DFS) for exploring a graph.
Your answer should cover:
- The order in which each visits nodes, and the data structure that produces that order.
- Which problems each is the right tool for (give at least two per traversal, with reasons).
- Their space behaviour — when does BFS's memory explode, and when does DFS's?
- Why BFS finds shortest paths in unweighted graphs but not weighted ones, and what handles the weighted case.
- Why a visited set is essential in graphs but unnecessary in trees.