DFS vs BFS — [Notes]

DFS

✅ A DFS will only store as much memory on the stack as is required for the longest root to leaf path in the tree.

In other words, its space usage is O(h) where h is the height of the tree.

✅ The Depth First Search (DFS) is the most fundamental search algorithm used to explore nodes and edges of a graph. It runs with a time complexity of O(V+E) and is often used as a building block in other algorithms.

✅ By itself the DFS isn’t all that useful, but when augmented to perform other tasks such as count connected components, determine connectivity, or find bridges/articulation points then DFS really shines.

✅ We can augment the DFS algorithm to:

• Compute a graph’s minimum spanning tree.
• Detect and find cycles in a graph.
• Check if a graph is bipartite.
• Find strongly connected components.
• Topologically sort the nodes of a graph.
• Find bridges and articulation points.
• Find augmenting paths in a flow network.
• Generate mazes.

BFS

✅ The Breadth First Search (BFS) is another fundamental search algorithm used to explore nodes and edges of a graph.

✅ It runs with a time complexity of 0(V+E) and is often used as a building block in other algorithms.

✅ The BFS algorithm is particularly useful for one thing: finding the shortest path on unweighted graphs.

✅ A BFS starts at some arbitrary node of a graph and explores the neighbor nodes first, before moving to the next level neighbors.

✅ A BFS maintains a queue every node at a fixed depth before visiting the next depth.

For example, if you have a complete binary tree, the number of leaves will be n/2 | n+1/2 = O(n) where n is the number of nodes in the tree. 
Each of those n/2 |(n+1)/2 nodes will be queued up at some point. 

✅ Many trees you will come across are moderately balanced. Even randomly built binary search trees have expected logarithmic height. In these cases, h = O(log n) < O(n), and DFS will therefore use less memory. So DFS is more memory efficient than BFS.

✅ Depth-first search is more memory efficient than breadth-first search also because you can backtrack sooner. It is also easier to implement if you use the call stack but this relies on the longest path not overflowing the stack.

✅ BFS is less space-efficient than DFS as BFS maintains a priority queue of the entire level while DFS just maintains a few pointers at each level by using a simple stack.

✅ If it is known priorly that an answer will likely be found far into a tree (depths of tree), DFS is a better option than BFS.

✅ If it is known that the solution is not far from the root of the tree, a breadth-first search (BFS) might be better.

✅ BFS is useful when the depth of the tree can vary or when a single answer is needed.
→ For instance, the shortest path in a maze. BFS will perform better here because DFS is most likely to start out on the wrong path, exploring a large portion of the maze before reaching the goal.

✅ If the tree is very deep and solutions are rare, depth-first search (DFS) might take an extremely long time, but BFS could be faster.

✅ If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. We go for DFS in such cases.

✅ If solutions are frequent but located deep in the tree we opt for DFS.

DFS vs BFS

BFS vs. DFS:

• BFS stores all the nodes level by level (till they are processed). For an average graph, this might mean requiring larger space compared to DFS. BFS uses a larger amount of memory because it expands all children of a vertex and keeps them in memory.
• BFS is going to use more memory depending on the branching factor.
  The space complexity of BFS is O((branching factor) ^ (distance from source to destination)) as we have seen above.
  If a graph is super wide and the goal state is not guaranteed to be closer to the start node then we need to think twice before performing a BFS, since that might not give an optimal result.
• BFS is better when the target is closer to the Source (like, looking for first degree and second-degree connections in the Facebook Friends network, or LinkedIn Connection Network).
• DFS is better when the target is far from the source (example: DFS is suitable for decision trees used in puzzle games).
• If you know a solution is not far from the start node, BFS would be better in most cases.
  If solutions are located deep in the tree or graph, BFS could be impractical.