Graphs, BFS, and DFS

A tree is just a graph with an extra rule (no cycles, one path to any node). Dropping that rule is what unlocks graphs — and the traversal patterns look almost identical, with one crucial addition.

Intermediate

5 min read

A graph, compared to what you already know

A tree (from its own lesson) is a graph with two restrictions: no cycles, and exactly one path between any two nodes. A graph drops both restrictions — nodes (vertices) can connect to any other nodes via edges, connections can form cycles, and there can be multiple paths — or no path at all — between two given nodes. Trees are graphs; not every graph is a tree. A social network (who follows whom), a road map (which intersections connect to which), and a dependency graph (which package requires which other package) are all naturally graphs, not trees — there's no single "root," and cycles are often normal (two friends can follow each other; two intersections can connect both ways).

Directed vs. undirected, weighted vs. unweighted

An edge can be undirected (the connection goes both ways, like a friendship) or directed (one-way, like a "follows" relationship or a one-way street). An edge can also carry a weight — a cost, distance, or time associated with traversing it — or be unweighted, where every edge is treated as equally costly. These are independent choices: a graph can be directed and weighted (flights between cities, with cost), undirected and unweighted (a simple friend network), or any other combination — recognizing which one you're looking at determines which algorithms even apply.

Representing a graph in code: the adjacency list

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

The adjacency list — a dict mapping each node to a list of its neighbors — is the standard representation for most real graph problems, because it's compact and directly answers "what does this node connect to" without wasted space. The alternative, an adjacency matrix (a 2D grid where matrix[i][j] is 1 if an edge exists between node i and j), makes "are these two specific nodes connected" an O(1) lookup, but wastes memory on sparse graphs — a graph with 10,000 nodes and only 20,000 edges would need a 10,000×10,000 matrix (mostly zeros) versus an adjacency list sized to the actual number of edges.

BFS: level by level, using a queue

from collections import deque
 
def bfs(graph, start):
    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)
                queue.append(neighbor)
 
    return order

Breadth-first search visits all of a node's immediate neighbors before moving on to their neighbors — level by level, outward from the start, exactly the shape covered in the stacks-and-queues lesson. A queue (FIFO) is what enforces this: nodes are processed in the exact order they were discovered, so every node at distance 1 from start is visited before any node at distance 2. The visited set is the one addition graphs need beyond what tree traversal required — since a graph can contain cycles, without tracking visited nodes, bfs could loop forever re-visiting the same nodes back and forth.

DFS: as deep as possible, then backtrack

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

Depth-first search goes as deep as possible down one path before backtracking to try another — the recursive call stack (from the recursion lesson) naturally provides the "remember where to backtrack to" behavior, the same way it did for tree traversal. The same visited set requirement applies here for the same reason: a graph's cycles mean the recursion could otherwise call itself into an infinite loop, re-visiting nodes it's already seen.

The concrete difference from tree traversal — one line

# Tree traversal — no visited tracking needed:
def tree_dfs(node):
    if node is None:
        return
    process(node)
    tree_dfs(node.left)
    tree_dfs(node.right)
 
# Graph traversal — visited tracking is required:
def graph_dfs(graph, node, visited):
    visited.add(node)
    process(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            graph_dfs(graph, neighbor, visited)

A tree's "no cycles" guarantee means tree traversal never has to worry about revisiting a node — every node has exactly one path down to it from the root, so recursing into children can never loop back on itself. A graph has no such guarantee, so the visited set isn't an optional optimization, it's what makes graph traversal correct at all; skip it, and BFS/DFS on a graph with any cycle will genuinely never terminate.

When to reach for BFS vs. DFS

BFS is the right choice whenever the question is about the shortest path in an unweighted graph, or "closest to the start" — because BFS explores in strict distance order, the first time it reaches a target node is guaranteed to be via a shortest path. Finding the shortest number of hops between two people in a social network, or the fewest moves to solve a puzzle, are BFS problems.
DFS is the natural choice for exploring every reachable node without caring about distance — detecting a cycle, checking whether a path exists at all between two nodes, or exploring all possibilities in a maze or a dependency tree. DFS also underlies topological sort (ordering nodes so every directed edge points forward — the shape behind "which order should these package dependencies install in").

Both are O(V + E) — every vertex and every edge gets visited at most once — so the choice between them is about what the traversal order actually needs to guarantee, not about performance.