Graph Traversal in Python: BFS vs DFS on an Adjacency List

Fri Aug 14 2026

A graph can be represented as an adjacency list: a dict mapping each node to the list of nodes it connects to. This post builds one with a disconnected component included on purpose, then walks it with a queue-based bfs and a recursive dfs from the same start nodes to compare the order each visits nodes in.

The code

from collections import deque


def bfs(graph, start):
    # Visit level by level using a queue (deque): explore all of start's
    # neighbors before any of their neighbors.
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order


def dfs(graph, start):
    # Visit as deep as possible using a stack (or recursion): go down one
    # path fully before backtracking to try the next branch.
    visited = set()
    order = []

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

    _visit(start)
    return order


graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
    "G": ["H"],
    "H": ["G"],
}

print("adjacency list:")
for node, neighbors in graph.items():
    print(f"  {node}: {neighbors}")

print("\nbfs(graph, 'A'):", bfs(graph, "A"))
print("dfs(graph, 'A'):", dfs(graph, "A"))

print("\nbfs(graph, 'G'):", bfs(graph, "G"))
print("dfs(graph, 'G'):", dfs(graph, "G"))

reached_from_a = set(bfs(graph, "A"))
print("\nis 'G' reachable from 'A'?", "G" in reached_from_a)
print("is 'F' reachable from 'A'?", "F" in reached_from_a)

bfs uses a deque as a FIFO queue, visiting all of a node’s neighbors before moving to the next level. dfs recurses into each unvisited neighbor immediately, going as deep as possible before backtracking. The graph has two components: A-B-C-D-E-F connected to each other, and G-H connected only to each other.

Running it

Real output:

adjacency list:
  A: ['B', 'C']
  B: ['A', 'D', 'E']
  C: ['A', 'F']
  D: ['B']
  E: ['B', 'F']
  F: ['C', 'E']
  G: ['H']
  H: ['G']

bfs(graph, 'A'): ['A', 'B', 'C', 'D', 'E', 'F']
dfs(graph, 'A'): ['A', 'B', 'D', 'E', 'F', 'C']

bfs(graph, 'G'): ['G', 'H']
dfs(graph, 'G'): ['G', 'H']

is 'G' reachable from 'A'? False
is 'F' reachable from 'A'? True

Starting from 'A', bfs visited ['A', 'B', 'C', 'D', 'E', 'F'] — both of A’s direct neighbors (B, C) before any of theirs. dfs visited ['A', 'B', 'D', 'E', 'F', 'C'] — it went A -> B -> D, backtracked, then B -> E -> F, and only reached C last. Both traversals stopped at 6 nodes, never touching G or H, since that pair forms a separate component. Starting from 'G' instead, both bfs and dfs only found ['G', 'H']. The reachability check confirmed it directly: 'G' was not in the set of nodes BFS reached from 'A', while 'F' was.

Takeaway

Same graph, two different visit orders from the same start node — BFS went neighbor-by-neighbor while DFS went deep down one branch first — and both correctly stayed within their connected component, never crossing into the separate G-H pair from A.