BFS & DFS

With a graph stored as a dict-based adjacency list, the next question is: how do you actually visit every node? The two fundamental approaches are Breadth-First Search (BFS), which explores level by level outward from a start node, and Depth-First Search (DFS), which plunges as deep as possible down one path before backtracking. Both visit every reachable vertex and edge exactly once, just in a different order — and that order matters a lot depending on the problem.

Example Graph

An unweighted, undirected graph with 6 vertices, used for both traversals below:

      0
     / \
    1   2
    |   |
    3   4
     \ /
      5

Edges: 0-1, 0-2, 1-3, 2-4, 3-5, 4-5. We'll start both traversals at vertex 0.

# Adjacency list for the graph above, as a dict of lists
adj = {i: [] for i in range(6)}

def add_edge(u, v):
    adj[u].append(v)
    adj[v].append(u)

add_edge(0, 1); add_edge(0, 2)
add_edge(1, 3); add_edge(2, 4)
add_edge(3, 5); add_edge(4, 5)

Breadth-First Search (BFS)

BFS uses a queue. It visits the start node, then all of its direct neighbors, then all of their unvisited neighbors, and so on — expanding outward in complete "rings" one level at a time. A visited set stops it from revisiting nodes or looping forever on a cycle. Python's list can pop from the front, but that's an O(n) operation; collections.deque supports O(1) appends and pops from both ends, which is exactly why it's the standard choice for a BFS queue.

from collections import deque

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

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)  # mark on enqueue, not on dequeue
                queue.append(neighbor)

    return order

# bfs(adj, 0) on the example graph: [0, 1, 2, 3, 4, 5]
# Level 0: {0} -> Level 1: {1, 2} -> Level 2: {3, 4} -> Level 3: {5}

Time complexity: O(V + E) — every vertex is enqueued once and every edge is examined once (twice for an undirected graph, still a constant factor). Space complexity: O(V) for the visited set and the deque, which can hold up to one full level of the graph at once.

Depth-First Search (DFS)

DFS commits to one path and follows it as far as it can before backtracking, using either Python's natural recursion (which uses the call stack) or an explicit list used as a stack. It's less "fair" than BFS about exploring breadth-wise, but it's the natural fit for problems about paths, cycles, and structure rather than distance.

def dfs(adj, start):
    order = []
    visited = set()
    _dfs_helper(adj, start, visited, order)
    return order

def _dfs_helper(adj, node, visited, order):
    visited.add(node)
    order.append(node)

    for neighbor in adj[node]:
        if neighbor not in visited:
            _dfs_helper(adj, neighbor, visited, order)  # recurse depth-first before trying siblings

# dfs(adj, 0) on the example graph: [0, 1, 3, 5, 4, 2]
# From 0 -> 1 (first neighbor) -> 3 (its first neighbor) -> 5 -> 4 (5's other neighbor)
# -> backtrack all the way to 0 -> try 0's other neighbor, 2 (already-visited nodes skipped)

Time complexity: O(V + E) — same reasoning as BFS, every vertex and edge is visited exactly once. Space complexity: O(V) — the visited set plus the recursion call stack, which in the worst case (a long path) holds all V frames at once.

BFS vs DFS: When to Choose Which