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).

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. 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

---

4. 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
      }
    }
  }
}

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))