Graphs

What is a graph?#

A graph is the most general data structure covered in this course: a collection of nodes (called vertices) connected by edges, with no restriction on how many connections a node can have or in what pattern. A tree, in fact, is just a special kind of graph — one with no cycles and exactly one path between any two nodes. Graphs drop those restrictions entirely, which makes them the right model for an enormous range of real-world relationships.

Analogy: a map of a city's roads, a social network's friendships, or a flight route map between airports. Cities/people/airports are vertices; roads/friendships/flights are edges. Unlike a tree, there's no single "root" and no rule against loops — you can fly from New York to Chicago and back to New York, and two friends can each be friends with the same third person, forming a triangle a tree could never represent.

Core terminology#

• Directed graph — edges have a direction, like a one-way street. An edge from A to B doesn't imply you can go from B to A. Think "Alice follows Bob on social media" — that doesn't mean Bob follows Alice back.
• Undirected graph — edges go both ways equally. Think "Alice and Bob are Facebook friends" — friendship is mutual by definition.
• Weighted graph — each edge carries a number (a "cost," "distance," or "weight"). A road map is naturally weighted — the edge between two cities has a distance or travel time attached.
• Unweighted graph — every edge is treated as equally "costly" — all that matters is whether a connection exists at all.

These two dimensions are independent — you can have a directed and weighted graph (flights, with direction and distance), an undirected and unweighted graph (a simple friendship network), and every other combination.

Representing a graph: adjacency list vs adjacency matrix#

There are two standard ways to actually store a graph in memory, and the right choice depends heavily on how dense the graph's connections are.

Adjacency list#

Store, for each vertex, a list of the vertices it directly connects to. This is by far the most common representation in practice, especially for sparse graphs (relatively few edges compared to the number of possible ones).

# An undirected, unweighted graph as an adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}

# A weighted graph stores (neighbor, weight) pairs instead
weighted_graph = {
    "A": [("B", 5), ("C", 2)],
    "B": [("A", 5), ("D", 1)],
    "C": [("A", 2), ("D", 7)],
    "D": [("B", 1), ("C", 7)],
}

• Space: O(V + E) — proportional to the number of vertices plus the number of edges, which is efficient whenever the graph isn't densely connected.
• Checking "are A and B connected?": O(degree of A) — you scan A's neighbor list, which is fast if A doesn't have many neighbors.
• Iterating over all of a vertex's neighbors: very efficient — you already have exactly that list.

Adjacency matrix#

Store an V x V grid (where V is the number of vertices), where matrix[i][j] is 1 (or the edge weight) if an edge exists from vertex i to vertex j, and 0/None otherwise.

# Same undirected graph as an adjacency matrix
# Order: A=0, B=1, C=2, D=3
matrix = [
    [0, 1, 1, 0],   # A connects to B, C
    [1, 0, 0, 1],   # B connects to A, D
    [1, 0, 0, 1],   # C connects to A, D
    [0, 1, 1, 0],   # D connects to B, C
]

# Checking whether A (0) and D (3) are connected: O(1) — a single lookup
print(matrix[0][3])   # 0 — not directly connected
print(matrix[0][1])   # 1 — A and B ARE directly connected

• Space: O(V²) — always, regardless of how many edges actually exist. This is wasteful for sparse graphs, but perfectly reasonable for dense graphs (where most vertices connect to most others).
• Checking "are A and B connected?": O(1) — a single array lookup, no scanning required. This is the matrix's biggest advantage over the list.
• Iterating over all of a vertex's neighbors: O(V) — you must scan an entire row, even if that vertex only has one real neighbor.

In practice, the adjacency list is the default choice for the vast majority of real graphs — social networks, road networks, and web page links are all sparse (each node connects to a small fraction of all other nodes), so the matrix's O(V²) space cost is rarely worth paying.

Breadth-First Search (BFS)#

BFS explores a graph level by level — visit a starting node, then all of its direct neighbors, then all of their unvisited neighbors, and so on outward, like ripples expanding from a stone dropped in water. This should feel familiar: it's the exact same queue-based pattern used for level-order tree traversal on the previous page, generalized to graphs (which requires one extra piece of bookkeeping — a visited set, since graphs can have cycles that trees can't).

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)      # mark visited the moment it's enqueued
                queue.append(neighbor)

    return order


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

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

Real use case: shortest path in an unweighted graph#

Because BFS visits nodes in increasing order of distance from the start (everyone 1 step away, then everyone 2 steps away, and so on), the first time BFS reaches a target node, it has necessarily done so via the fewest possible edges — giving you the shortest path for free, as long as every edge counts equally (unweighted). This is precisely how "find the fewest number of hops between two people in a social network" or "solve a maze in the fewest moves" get solved.

def shortest_path_bfs(graph, start, target):
    visited = {start}
    queue = deque([(start, [start])])   # track the path taken so far alongside each node

    while queue:
        node, path = queue.popleft()
        if node == target:
            return path

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None   # target unreachable from start


print(shortest_path_bfs(graph, "A", "D"))   # ['A', 'B', 'D']  (or ['A', 'C', 'D'] — both length 3)

Depth-First Search (DFS)#

DFS explores as deep as possible down one path before backtracking — go to a neighbor, then that neighbor's neighbor, continuing until you hit a dead end (or an already-visited node), then back up and try the next unexplored branch. This is naturally expressed with recursion (using the call stack), mirroring pre-order tree traversal.

def dfs(graph, start, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []

    visited.add(start)
    order.append(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)

    return order


print(dfs(graph, "A"))   # ['A', 'B', 'D', 'C']  — goes deep before coming back for C

Compare the two traces on the same graph starting from "A": BFS visits ['A', 'B', 'C', 'D'] (both direct neighbors of A before going further), while DFS visits ['A', 'B', 'D', 'C'] (all the way down through B and D first, only backtracking to C once that branch is exhausted). Same graph, same starting point, genuinely different exploration order — and each order is useful for different problems.

Real use case: cycle detection#

DFS is the natural tool for detecting a cycle in a graph, because it's already tracking "the path I'm currently exploring." For a directed graph specifically, you need to track two things: nodes visited overall, and nodes currently "in progress" on the active recursive path (often called the recursion stack) — a cycle exists if you ever reach a node that's already on that active path.

def has_cycle_directed(graph):
    visited = set()
    in_progress = set()   # nodes on the current DFS path

    def visit(node):
        visited.add(node)
        in_progress.add(node)

        for neighbor in graph.get(node, []):
            if neighbor in in_progress:
                return True                    # back-edge to an ancestor: a cycle!
            if neighbor not in visited and visit(neighbor):
                return True

        in_progress.remove(node)   # done exploring this node's branch
        return False

    return any(node not in visited and visit(node) for node in graph)


cyclic_graph = {"A": ["B"], "B": ["C"], "C": ["A"]}   # A -> B -> C -> A
acyclic_graph = {"A": ["B"], "B": ["C"], "C": []}      # A -> B -> C, no way back

print(has_cycle_directed(cyclic_graph))    # True
print(has_cycle_directed(acyclic_graph))   # False

This exact "DFS + in-progress tracking" pattern is also the foundation of topological sort — producing a valid ordering of tasks that respects dependency constraints (e.g., "course B requires course A first") — which only exists at all when the dependency graph is acyclic (a cyclic dependency, like "A requires B, which requires A," has no valid order).

Common mistakes#

• Forgetting to track visited nodes. Unlike a tree, a graph can have cycles — without a visited set, BFS/DFS can loop forever, endlessly re-visiting the same nodes.
• Marking a node visited at the wrong time in BFS. Mark a node visited the moment it's enqueued, not when it's dequeued — otherwise the same node can be added to the queue multiple times before it's processed, wasting work (and in some variants, causing incorrect results).
• Choosing an adjacency matrix for a huge sparse graph. A social network with a million users but an average of 100 friends each would need a trillion-cell matrix — wildly wasteful compared to an adjacency list's proportional-to-actual-edges cost.
• Assuming BFS and DFS always visit nodes in the same order, or that either is "more correct" — they're both correct, complete traversals; which one to use depends entirely on the problem (shortest paths and "closest first" favor BFS; exhaustive exploration, cycle detection, and topological sort favor DFS).