11.1 Graph Fundamentals, BFS & DFS

1. What Is a Graph?

A Graph is the most general way to model connections between anything:

• Vertices (Nodes, V): The things themselves (cities on a map, users on a social network, courses in a degree, or cells (r, c) in a 2D grid).
• Edges (E): The links connecting two nodes (u and v).
  • Undirected Edge (u <-> v): A two-way street (if A is friends with B, B is friends with A).
  • Directed Edge (u -> v): A one-way street (Course A must be taken before Course B).

How is a Graph different from a Tree? A Tree is just a restricted Graph with one root and no loops (cycles). A general Graph can have cycles, disconnected islands, and multiple paths between the same two nodes!

2. Why Do We Need visited & How Do We Store a Graph in Code?

1. How to Store a Graph: Adjacency List (adj[u])

In interviews, graphs are usually given as a list of edges like edges = [[0, 1], [0, 2], [1, 3]]. Before doing anything else, convert that edge list into an Adjacency List (adj[u] = list of neighbors of u). That lets you look up all neighbors of any node u immediately using only O(V + E) memory.

2. Why visited Is Mandatory

Because graphs can contain cycles (0 -> 1 -> 2 -> 0), walking to neighbors without remembering where you have already been will cause an infinite loop! Always mark a node in visited the moment you discover it.

3. When to Pick DFS vs. BFS

• Graph DFS (Recursion): Best for exploring or counting connected islands (Number of Islands, Clone Graph).
• Graph BFS / Multi-Source BFS (FIFO Queue): Best for shortest unweighted path / minimum minutes (Rotting Oranges, Word Ladder). Because BFS expands outward one ripple at a time, the first time it touches a node is guaranteed to be via the shortest number of edges!

3. Basic Operations & Walkthroughs (All 4 Languages)

from collections import deque

# 1. Build an Adjacency List from an undirected edge list -> O(V + E)
def build_graph(n: int, edges: list[list[int]]) -> list[list[int]]:
  adj = [[] for _ in range(n)]
  for u, v in edges:
      adj[u].append(v)
      adj[v].append(u)
  return adj

# 2. Graph DFS (Explore one connected component) -> O(V + E)
def dfs(u: int, adj: list[list[int]], visited: set[int]) -> None:
  visited.add(u)
  for v in adj[u]:
      if v not in visited:
          dfs(v, adj, visited)

# 3. Multi-Source Grid BFS (e.g., Rotting Oranges) -> O(R * C)
def multi_source_bfs(grid: list[list[int]]) -> int:
  rows, cols = len(grid), len(grid[0])
  q = deque()
  fresh = 0
  for r in range(rows):
      for c in range(cols):
          if grid[r][c] == 2: q.append((r, c))
          elif grid[r][c] == 1: fresh += 1
  minutes = 0
  while q and fresh > 0:
      minutes += 1
      for _ in range(len(q)):
          r, c = q.popleft()
          for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
              nr, nc = r + dr, c + dc
              if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                  grid[nr][nc] = 2
                  fresh -= 1
                  q.append((nr, nc))
  return minutes if fresh == 0 else -1

4. Core Interview Patterns & Common Traps

# Mark visited IMMEDIATELY when pushing to the BFS queue:
q = deque(initial_sources)
visited = set(initial_sources)
steps = 0
while q:
  for _ in range(len(q)):
      r, c = q.popleft()
      for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
          nr, nc = r + dr, c + dc
          if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in visited:
              visited.add((nr, nc))
              q.append((nr, nc))
  steps += 1

5. Practice On Your Own (Curated Submodule Problems)