Graph Traversal: BFS and DFS

[!NOTE] If a Graph is a maze, Traversal is the strategy to explore it. There are two main philosophies: Go Wide (BFS) or Go Deep (DFS).

In interviews and real-world system design, graphs model almost everything: networks of computers, social media connections, dependencies in a package manager, or cities on a map. Knowing how to search these graphs efficiently is foundational. Do you need to find the absolute shortest path between two people on LinkedIn? Or do you need to quickly figure out if two servers are connected at all? The answers lie in BFS and DFS.

1. Breadth-First Search (BFS)

Imagine dropping a stone in a pond. The ripples expand outward in perfect circles. That is BFS.

• Strategy: Explore all neighbors at the current depth before moving deeper.
• Data Structure: Queue (FIFO).
• Key Property: Finds the Shortest Path in unweighted graphs.
• Analogy: A contagious virus spreading person-to-person.

2. Depth-First Search (DFS)

Imagine solving a maze. You follow a path until you hit a dead end, then backtrack to the last junction and try a different path. That is DFS.

• Strategy: Go as deep as possible down one branch before backtracking.
• Data Structure: Stack (LIFO) or Recursion.
• Key Property: Good for puzzles, topological sorting, and detecting cycles.
• Analogy: Exploring a cave system.

---

3. Complexity & Comparison

Time & Space Complexity

Algorithm	Time Complexity	Space Complexity	Why?
BFS	$O(V + E)$	$O(V)$	Every vertex $V$ and edge $E$ is visited once. Space is bounded by the widest level (up to $O(V)$).
DFS	$O(V + E)$	$O(V)$	Every vertex and edge is visited once. Space is bounded by the maximum recursion depth (up to $O(V)$ for a skewed graph).

When to use which?

• BFS: Use when you want to find the shortest path on an unweighted graph, or when you know the target is close to the starting point. It requires more memory for wide graphs.
• DFS: Use for exploring all possibilities (like solving a maze, generating permutations), checking for cycles, or topological sorting. It uses less memory for wide graphs but more for deep graphs.

---

4. Interactive: Traversal Visualizer

Click the grid to place Obstacles (Walls). Then run BFS or DFS to see how they navigate from Start (Green) to fill the available space.

Visited: 0 | Max Depth: 0

Start Wall Visited Frontier

---

5. Code Implementation

Breadth-First Search (Queue)

Java

public void bfs(int startNode) {
  boolean[] visited = new boolean[V];
  Queue<Integer> queue = new LinkedList<>();

  visited[startNode] = true;
  queue.add(startNode);

  while (!queue.isEmpty()) {
    int u = queue.poll();
    System.out.print(u + " ");

    for (int v : adj.get(u)) {
      if (!visited[v]) {
        visited[v] = true;
        queue.add(v);
      }
    }
  }
}

Go

func (g *Graph) BFS(startNode int) {
  visited := make(map[int]bool)
  queue := []int{startNode}
  visited[startNode] = true

  for len(queue) > 0 {
    u := queue[0]
    queue = queue[1:] // Dequeue
    fmt.Printf("%d ", u)

    for _, v := range g.Adj[u] {
      if !visited[v] {
        visited[v] = true
        queue = append(queue, v) // Enqueue
      }
    }
  }
}

Depth-First Search (Stack / Recursion)

Java

public void dfs(int u, boolean[] visited) {
  visited[u] = true;
  System.out.print(u + " ");

  for (int v : adj.get(u)) {
    if (!visited[v]) {
      dfs(v, visited);
    }
  }
}

// Wrapper
public void startDFS(int startNode) {
  boolean[] visited = new boolean[V];
  dfs(startNode, visited);
}

Go

func (g *Graph) DFS(u int, visited map[int]bool) {
  visited[u] = true
  fmt.Printf("%d ", u)

  for _, v := range g.Adj[u] {
    if !visited[v] {
      g.DFS(v, visited)
    }
  }
}

// Usage: g.DFS(0, make(map[int]bool))