Graph Traversal

BFS and DFS are the two fundamental ways to explore a graph. BFS goes wide (level by level), DFS goes deep (as far as possible before backtracking). Knowing when to use each is half the battle.

BFS: Breadth-First Search

Explore all neighbors first, then their neighbors. Uses a queue. Great for shortest paths in unweighted graphs.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(node)  # Process node

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

DFS: Depth-First Search

Go as deep as possible, then backtrack. Can use recursion or a stack.

def dfs(graph, node, visited):
    if node in visited:
        return

    visited.add(node)
    print(node)  # Process node

    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

Classic: Number of Islands

def numIslands(grid):
    if not grid:
        return 0

    count = 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return

        grid[r][c] = '0'  # Mark visited
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

    return count