Graph Traversal

Overview

Graph traversal systematically visits nodes reachable from a start node. Breadth-first search (BFS) explores level by level using a queue and finds shortest paths in unweighted graphs. Depth-first search (DFS) plunges as deep as possible using recursion or a stack. Both run in O(V + E) time and use O(V) space, where V is vertices and E is edges.

Syntax / Usage

Represent the graph as an adjacency list (a dict of node to neighbors) and track visited nodes in a set so cycles do not cause infinite loops.

from collections import deque

def bfs(graph, start):               # O(V + E) time, O(V) space
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)   # mark on enqueue, not dequeue
                queue.append(neighbor)
    return order

Examples

Traverse a small graph breadth-first from node A:

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs(graph, "A"))  # ['A', 'B', 'C', 'D']

Depth-first search with recursion, useful for reachability and cycle detection:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

print(dfs(graph, "A"))  # {'A', 'B', 'C', 'D'}

Common Mistakes

• Marking a node visited when dequeuing instead of enqueuing, causing duplicate processing.
• Omitting the visited set, which loops forever on cyclic graphs.
• Using BFS for shortest paths on weighted graphs, where Dijkstra is required instead.
• Deep recursive DFS overflowing the call stack; switch to an explicit stack for large graphs.
• Assuming the graph is connected, so nodes unreachable from the start are silently skipped.

See Also

algorithms-recursion algorithms-searching algorithms-backtracking