Non-Linear Data Structures: Graphs

TL;DR

You'll learn how to represent graphs in Python using adjacency lists and matrices, and when to pick each. You'll walk through BFS and DFS with real code, tracing exactly how they explore a network. You'll finish knowing which traversal to reach for depending on whether you need shortest paths, connectivity, or cycle detection.

1. The Mental Model

A graph is just a set of things (nodes) and connections between them (edges) — nothing more. A tree is a graph with rules (no cycles, one parent); a graph drops those rules entirely, so it can model anything connected to anything. Roads between cities, friendships, web pages linking to each other — all graphs. If a tree is a family, a graph is a social network — messier, looping, and far more realistic.

2. The Core Material

2.1 Representing a Graph

Photo by Lukas Blazek on Pexels

You have two real choices in practice: adjacency list and adjacency matrix.

An adjacency list stores, for each node, the list of neighbors it connects to. In Python, a dictionary of lists works beautifully:

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

This costs $O(V + E)$ space (V = vertices, E = edges), which is efficient for sparse graphs (few edges relative to possible connections). Checking "is X a neighbor of Y" takes $O(\text{deg}(Y))$ time — you scan Y's list.

An adjacency matrix is a $V \times V$ grid of 0s and 1s (or weights):

import numpy as np
nodes = ['A', 'B', 'C', 'D', 'E']
idx = {n: i for i, n in enumerate(nodes)}
matrix = np.zeros((5, 5), dtype=int)
matrix[idx['A']][idx['B']] = 1
matrix[idx['B']][idx['A']] = 1  # undirected: symmetric

This costs $O(V^2)$ space regardless of how many edges actually exist, but checking "is X connected to Y" is $O(1)$ — just index into the matrix. Dense graphs (most nodes connected to most others) favor matrices; sparse real-world graphs (social networks, road maps) almost always favor lists.

2.2 Breadth-First Search (BFS)

Photo by cottonbro studio on Pexels

BFS explores a graph level by level — all neighbors first, then their neighbors, and so on. It's the right tool when you need the shortest path in an unweighted graph, because the first time BFS reaches a node, it's guaranteed to be via the shortest possible route (fewest edges).

BFS uses a queue (FIFO — first in, first out):

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

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

Mark nodes as visited when you enqueue them, not when you dequeue them — a classic source of bugs. If you wait until dequeue, the same node can be added to the queue multiple times by different neighbors before it's processed, wasting work and in worst cases breaking correctness.

Time complexity is $O(V + E)$: every vertex is dequeued once, and every edge is examined once (across all adjacency list traversals).

2.3 Depth-First Search (DFS)

Photo by Matheus Bertelli on Pexels

DFS dives as deep as possible down one path before backtracking. It uses a stack (LIFO — last in, first out), either explicitly or via recursion (which uses the call stack).

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

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

Iterative version with an explicit stack avoids Python's recursion depth limit on large graphs:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return order

DFS is also $O(V + E)$, but it's the natural choice for cycle detection, topological sorting, and connected components — anything where you need to fully explore one branch before moving to the next.

flowchart TD
    Start["Need to explore a graph"] --> Q1{"Need shortest path\n in unweighted graph?"}
    Q1 -->|Yes| BFS["Use BFS (queue)"]
    Q1 -->|No| Q2{"Detecting cycles or\ndoing topological sort?"}
    Q2 -->|Yes| DFS["Use DFS (stack/recursion)"]
    Q2 -->|No| Q3{"Just need connectivity\n or all reachable nodes?"}
    Q3 -->|Yes| Either["Either works — pick DFS\n for lower memory on deep graphs"]
    Q3 -->|No| Q4{"Edges have weights?"}
    Q4 -->|Yes| Dijkstra["Use Dijkstra / Bellman-Ford\n (not plain BFS/DFS)"]

2.4 Directed vs Undirected, Weighted vs Unweighted

An undirected graph's edges go both ways (friendship); a directed graph's edges have direction (Twitter follows, one-way streets). In code, the only difference in adjacency-list representation is whether you add the edge to both nodes' lists or just one:

# Undirected: add both directions
def add_edge_undirected(graph, u, v):
    graph.setdefault(u, []).append(v)
    graph.setdefault(v, []).append(u)

# Directed: add only one direction
def add_edge_directed(graph, u, v):
    graph.setdefault(u, []).append(v)

Weighted graphs attach a cost to each edge (distance, time, price). You represent this as a list of tuples instead of bare neighbor names:

weighted_graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('A', 4), ('D', 2)],
    'C': [('A', 1), ('D', 6)],
    'D': [('B', 2), ('C', 6)]
}

Plain BFS/DFS ignore weights entirely — they only count edges, not cost. If you need shortest weighted path, you need Dijkstra's algorithm or Bellman-Ford, which is a separate topic built on top of this same adjacency-list foundation.

3. Worked Example

Let's find the shortest path (not just the order of visits) from 'A' to 'E' in our original unweighted graph using BFS, tracking parents so we can reconstruct the path:

from collections import deque

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

def bfs_shortest_path(graph, start, goal):
    visited = {start}
    queue = deque([start])
    parent = {start: None}

    while queue:
        node = queue.popleft()
        if node == goal:
            # Reconstruct path by walking parents backwards
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)
    return None  # no path exists

print(bfs_shortest_path(graph, 'A', 'E'))

Trace it by hand:
- Start: queue = ['A'], parent = {A: None}.
- Dequeue A. Neighbors B, C — both unvisited. Enqueue both. parent = {A: None, B: A, C: A}. queue = ['B', 'C'].
- Dequeue B. Neighbors A (visited), D (new). Enqueue D. parent[D] = B. queue = ['C', 'D'].
- Dequeue C. Neighbors A (visited), D (already visited via B). Nothing new. queue = ['D'].
- Dequeue D. It's not the goal yet. Neighbors B, C (visited), E (new). Enqueue E. parent[E] = D. queue = ['E'].
- Dequeue E. It's the goal. Walk back: E → D → B → A. Reverse: ['A', 'B', 'D', 'E'].

Output: ['A', 'B', 'D', 'E'] — length 3 edges. This is provably the shortest route, because BFS explores strictly in order of distance from the start.

4. Production Pitfalls & Best Practices

4.1 Real-World Best Practices

• Use collections.deque for BFS queues, never a plain Python list with .pop(0) — that's $O(n)$ per removal, turning your $O(V+E)$ algorithm into $O(V^2)$.
• Mark nodes visited at enqueue time for BFS, not at dequeue time, to prevent duplicate queue entries.
• Prefer iterative DFS for large or unpredictable graphs — Python's default recursion limit (~1000) will crash on a long chain of nodes; sys.setrecursionlimit() is a band-aid, not a fix.
• Use defaultdict(list) or .setdefault() when building adjacency lists dynamically — avoids KeyError when a node appears as a destination before being added as a source.
• Separate graph construction from traversal logic — build the adjacency structure once, then reuse it across multiple BFS/DFS calls; don't rebuild it per query.
• For weighted shortest-path problems, don't try to bolt weights onto BFS — reach for heapq and Dijkstra instead; BFS's correctness guarantee only holds for unweighted (or equal-weight) edges.

4.2 Common Bugs & Anti-Patterns

Bug 1: Forgetting to track visited nodes → infinite loop on cyclic graphs.

# BAD — no visited set, loops forever on a cycle
def dfs_broken(graph, node):
    print(node)
    for neighbor in graph[node]:
        dfs_broken(graph, neighbor)

# FIXED
def dfs_fixed(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_fixed(graph, neighbor, visited)

Bug 2: Marking visited at dequeue time in BFS → duplicate work, wrong shortest-path results in some edge cases.

# BAD
def bfs_bad(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            queue.append(neighbor)  # may enqueue duplicates repeatedly

# FIXED — mark visited when enqueuing
def bfs_good(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Bug 3: Using a list as a queue — silent performance killer.

# BAD — O(n) per pop(0)
queue = []
queue.append(start)
node = queue.pop(0)

# FIXED
from collections import deque
queue = deque([start])
node = queue.popleft()

Bug 4: Assuming an adjacency matrix is cheap for sparse graphs.

# BAD — wastes memory for a graph with 1M nodes, 2M edges
matrix = [[0]*1_000_000 for _ in range(1_000_000)]  # ~1TB, crashes

# FIXED — adjacency list scales with actual edges
from collections import defaultdict
graph = defaultdict(list)
graph[0].append(1)  # O(V+E) space, not O(V^2)

4.3 When to Use What (Decision Matrix)

5. Now Try It

Write a function has_path(graph, start, end) that returns True or False depending on whether any path exists between start and end in an undirected graph, using BFS or DFS (your choice). Test it on this graph:

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

Check: has_path(graph, 'A', 'C') should be True; has_path(graph, 'A', 'D') should be False (two disconnected components). Then modify your function to return the actual path (list of nodes) instead of just a boolean, reusing the parent-tracking technique from Section 3.

Success looks like: your function correctly returns True/False for both test cases above, and the path-returning version prints a valid node-by-node route from A to C.