Graph Traversals

You have a social network graph. Starting from Alice, you want to find all her connections: direct friends, friends of friends, and so on.

How do you explore the graph systematically? Visit every reachable vertex exactly once?

Two approaches: Breadth-First Search (BFS) and Depth-First Search (DFS).

Breadth-First Search (BFS)

Explore level by level. Visit all immediate neighbors first, then their neighbors, then their neighbors' neighbors.

Like ripples in water spreading outward.

Graph:
    A
   / \
  B   C
 / \   \
D   E   F

BFS from A: A, B, C, D, E, F

Level 0: A
Level 1: B, C (A's neighbors)
Level 2: D, E, F (neighbors of B and C)

Algorithm: Use a queue.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

Why queue? FIFO ensures level-by-level: process all level k before level k+1.

Time: O(V + E). Visit each vertex once, check each edge once.

Space: O(V) for visited set and queue.

Depth-First Search (DFS)

Explore as far as possible down one branch before backtracking.

Like walking through a maze: go straight until you hit a dead end, then backtrack.

Graph:
    A
   / \
  B   C
 / \   \
D   E   F

DFS from A: A, B, D, E, C, F

Goes deep: A → B → D (dead end) → backtrack → E → backtrack → C → F.

Algorithm: Use a stack (or recursion).

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        vertex = stack.pop()
        
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            
            # Add neighbors in reverse to maintain left-to-right order
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result

print(dfs_iterative(graph, 'A'))  # ['A', 'B', 'D', 'E', 'C', 'F']

Recursive (cleaner):

def dfs_recursive(graph, vertex, visited=None, result=None):
    if visited is None:
        visited = set()
    if result is None:
        result = []
    
    visited.add(vertex)
    result.append(vertex)
    
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, result)
    
    return result

print(dfs_recursive(graph, 'A'))  # ['A', 'B', 'D', 'E', 'C', 'F']

Why stack/recursion? LIFO explores deepest path first.

Time: O(V + E). Same as BFS.

Space: O(V) for visited set and stack/recursion.

BFS vs DFS

Finding Shortest Path with BFS

BFS finds shortest path in unweighted graph (fewest edges).

def bfs_shortest_path(graph, start, goal):
    visited = set([start])
    queue = deque([(start, [start])])
    
    while queue:
        vertex, path = queue.popleft()
        
        if vertex == goal:
            return path
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # No path

path = bfs_shortest_path(graph, 'A', 'F')
print(path)  # ['A', 'C', 'F']

BFS guarantees shortest because it explores closer vertices first.

DFS might find A → B → ... → F (longer path).

Detecting Cycles with DFS

Graph has cycle if during DFS we revisit a vertex that's in current path.

def has_cycle(graph):
    visited = set()
    rec_stack = set()  # Recursion stack
    
    def dfs(vertex):
        visited.add(vertex)
        rec_stack.add(vertex)
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True  # Back edge = cycle
        
        rec_stack.remove(vertex)
        return False
    
    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex):
                return True
    
    return False

# Cyclic graph
cyclic = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A']
}

print(has_cycle(cyclic))  # True (A → B → C → A)

Connected Components

Find groups of connected vertices in undirected graph.

def count_components(graph):
    visited = set()
    count = 0
    
    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
    
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
            count += 1
    
    return count

disconnected = {
    'A': ['B'],
    'B': ['A'],
    'C': ['D'],
    'D': ['C'],
    'E': []
}

print(count_components(disconnected))  # 3 components: {A,B}, {C,D}, {E}

Bidirectional Search

Search from both start and goal simultaneously. Meet in the middle.

Faster for large graphs: O(b^(d/2)) vs O(b^d).

def bidirectional_search(graph, start, goal):
    if start == goal:
        return [start]
    
    front_visited = {start: None}
    back_visited = {goal: None}
    front_queue = deque([start])
    back_queue = deque([goal])
    
    while front_queue and back_queue:
        # Expand from front
        if front_queue:
            current = front_queue.popleft()
            for neighbor in graph[current]:
                if neighbor in back_visited:
                    return reconstruct_path(front_visited, back_visited, current, neighbor)
                if neighbor not in front_visited:
                    front_visited[neighbor] = current
                    front_queue.append(neighbor)
        
        # Expand from back
        if back_queue:
            current = back_queue.popleft()
            for neighbor in graph[current]:
                if neighbor in front_visited:
                    return reconstruct_path(front_visited, back_visited, neighbor, current)
                if neighbor not in back_visited:
                    back_visited[neighbor] = current
                    back_queue.append(neighbor)
    
    return None

Common Mistakes

Not tracking visited: Infinite loop in graphs with cycles.

# Wrong
def dfs_wrong(graph, vertex):
    for neighbor in graph[vertex]:
        dfs_wrong(graph, neighbor)  # Never stops!

# Right
def dfs_right(graph, vertex, visited):
    visited.add(vertex)
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_right(graph, neighbor, visited)

Using wrong traversal: Need shortest path? Use BFS, not DFS.

Stack overflow with DFS recursion: Deep graphs exhaust stack. Use iterative.

The Pattern

Graph traversals explore all reachable vertices:

• BFS: queue, level-by-level, shortest path
• DFS: stack/recursion, deep-first, cycle detection
• Both O(V + E)

Understanding traversals means knowing which solves your problem: distance (BFS) vs exploration (DFS).

Master BFS and DFS, and you'll solve connectivity, path, and search problems.