Explain the difference between depth-first search and breadth-first search.

Depth-First Search (DFS) and Breadth-First Search (BFS) are two fundamental algorithms used to traverse or search through trees and graphs. They differ primarily in the order in which they explore nodes.

1. Depth-First Search (DFS):

   • DFS explores as far down a branch as possible before backtracking.
   • It uses a stack data structure, either explicitly or via recursion.
   • Suitable for scenarios where you want to visit every node and are interested in paths (e.g., solving mazes).

2. Breadth-First Search (BFS):

   • BFS explores all neighbors at the present depth prior to moving on to nodes at the next depth level.
   • It uses a queue data structure.
   • Ideal for finding the shortest path in unweighted graphs (e.g., social network connections).

Key Talking Points:

• DFS:

  • Uses a stack or recursion.
  • Explores deeply first.
  • Can be more memory efficient for wide graphs.

• BFS:

  • Uses a queue.
  • Explores neighbors level by level.
  • Finds shortest paths in unweighted graphs.

NOTES:

Reference Table:

• BFS: Picture yourself standing at the entrance of a building and exploring every room on the current floor before moving to the next floor.

Pseudocode:

# DFS using recursion
function DFS(node):
    if node is not visited:
        mark node as visited
        for each neighbor in node's neighbors:
            DFS(neighbor)

# BFS using a queue
function BFS(startNode):
    queue = empty queue
    enqueue startNode
    mark startNode as visited
    while queue is not empty:
        node = dequeue queue
        for each neighbor in node's neighbors:
            if neighbor is not visited:
                enqueue neighbor
                mark neighbor as visited

Follow-Up Questions and Answers:

1. How would you modify DFS to detect cycles in a graph?

   • Answer: You can modify DFS to detect cycles by maintaining a visited set and a recursion stack. If you encounter a node that is already in the recursion stack, a cycle exists.

2. What are some practical applications of BFS and DFS?

   • Answer: BFS is used in shortest path algorithms like Dijkstra's and in networking protocols. DFS is used in topological sorting, solving puzzles, and in scheduling problems.

3. Can you implement a DFS without recursion?

   • Answer: Yes, you can implement DFS without recursion by using an explicit stack to keep track of nodes.

By understanding these key points, you'll be well-prepared to discuss DFS and BFS in your interviews, especially at companies like FAANG where a strong grasp of algorithms is essential.