Just like in Trees, we use BFS and DFS to visit nodes in a Graph. The big difference? Graphs can have Cycles! You MUST keep track of visited nodes to avoid infinite loops.

1. Breadth First Search (BFS) - The Ripple

Think of dropping a Pebble in a Pond:

• The ripple hits all neighbors of depth 1 first.
• Then it hits all neighbors of depth 2.
• Goal: Finding the Shortest Path in an unweighted graph.

2. Depth First Search (DFS) - The Explorer

Think of a Spelunker in a Cave:

• Go deep into one branch until you hit a wall.
• Backtrack slightly and try the next branch.
• Goal: Exhaustive search, cycle detection, path existence.

---

The "Visited" Array

Because graphs can be connected in complex ways, you can reach the same node twice. The Rule: Always check if (!visited.has(node)) before exploring.

Complexity Analysis

• Time: $O(V + E)$ where $V$ is vertices and $E$ is edges. We visit every node and every edge once.
• Space: $O(V)$ to store the visited set and the queue/stack.

---

javascript Standard
/**
 * BFS - Iterative (uses Queue)
 */
function bfs(startNode, adjList) {
  const queue = [startNode];
  const visited = new Set([startNode]);

  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node); // Process

    for (const neighbor of adjList.get(node)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

/**
 * DFS - Recursive (uses Stack)
 */
function dfs(node, visited, adjList) {
  visited.add(node);
  console.log(node); // Process

  for (const neighbor of adjList.get(node)) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited, adjList);
    }
  }
}

---

Top Techniques

• Number of Connected Components: How many "islands" are in the graph? Start BFS/DFS on every unvisited node and count how many times you start.
• Flood Fill: Used in "Island" problems or "Minesweeper" logic to color connected areas.
• Path Existence: Can you get from $A$ to $B$?

Key Differences

BFS is generally better for Shortest Path. DFS is generally easier to implement (recursion) and better for Topological Sort or Cycle Detection. 🌊