The Vocabulary of Relationships

Trees were the warm-up

A tree is a graph with no cycles and exactly one path between any two nodes. Every technique you learned for trees generalises to graphs, with one new concern: cycles. Traversing a tree, you cannot revisit a node by accident. Traversing a graph, you will, unless you maintain a visited set. That set is the single most important line of code in any graph algorithm.

The representation matters. For most problems, an adjacency list (a dictionary mapping each node to its list of neighbours) is the right choice. It uses O(V + E) memory and lets you enumerate a node's neighbours in O(degree). An adjacency matrix (a V×V boolean grid) uses O(V²) memory, which is prohibitive for sparse graphs but lets you check whether two specific nodes are connected in O(1). Dense graphs favour the matrix; sparse graphs, which is almost all graphs, favour the list.

Breadth-first search

BFS explores a graph in waves. You start at a source node, visit all its neighbours, then all their neighbours, and so on. The data structure is a FIFO queue. The invariant is that at any moment, the queue contains all nodes whose distance from the source is either d or d + 1, for some d.

from collections import deque

def bfs_shortest(graph, source):
    dist = {source: 0}
    q = deque([source])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

Because BFS expands nodes in order of distance from the source, dist[v] is the shortest number of edges from source to v. This is why BFS is the correct algorithm for unweighted shortest paths, not because it's fast (it's O(V + E) regardless), but because the order of discovery matches the metric you want.

Depth-first search

DFS is BFS with a stack instead of a queue, or, more naturally, a recursive function. You explore as far down one path as you can before backtracking. The order of discovery is no longer by distance, but the traversal visits every reachable node in O(V + E) time, and the recursion structure is beautifully suited to problems where the answer depends on the recursive structure of the exploration.

def dfs(graph, u, visited):
    visited.add(u)
    for v in graph[u]:
        if v not in visited:
            dfs(graph, v, visited)

def connected_components(graph):
    seen = set()
    components = 0
    for node in graph:
        if node not in seen:
            dfs(graph, node, seen)
            components += 1
    return components

DFS naturally detects cycles, classifies edges (tree, back, forward, cross), and produces topological orderings of DAGs. It is also the algorithm you adapt into backtracking, the family of exhaustive-search algorithms that solve N-queens, Sudoku, and constraint satisfaction.

Topological sort

A topological ordering of a directed acyclic graph (DAG) is a linear sequence of its nodes in which every edge goes from an earlier node to a later one. Useful for course prerequisites, build systems, package resolution, any scenario where tasks have dependencies.

Two algorithms produce it. Kahn's algorithm: repeatedly pluck a node with zero in-degree, output it, remove its outgoing edges, repeat. DFS post-order: run a DFS and output nodes in the reverse order in which they finish. Both are O(V + E); Kahn's is more intuitive when you want to detect cycles at the same time (if the queue runs dry before all nodes are output, there is a cycle).

def topo_sort(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]: indeg[v] += 1
    q = deque([u for u, d in indeg.items() if d == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    if len(order) != len(graph):
        raise ValueError("graph has a cycle")
    return order

Dijkstra, shortest paths with weights

When edges have non-negative weights, BFS no longer suffices, closer-in-edge-count is not the same as closer-in-weight. Dijkstra's algorithm generalises BFS by replacing the FIFO queue with a min-priority-queue keyed on cumulative distance. At each step, pop the node with the smallest tentative distance, finalise it, and relax its outgoing edges. The invariant is that whenever a node is popped, its distance is already final.

import heapq

def dijkstra(graph, source):
    dist = {source: 0}
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')): continue
        for v, w in graph[u]:              # graph[u] = list of (neighbour, weight)
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

The if d > dist.get(u, float('inf')): continue is the lazy-deletion trick, the heap may contain stale entries from when we pushed a larger distance, and skipping them costs nothing. Running time: O((V + E) log V) with a binary heap. Dijkstra does not work with negative weights; Bellman-Ford does, at cost O(V·E).

Complexity, reasoned

BFS and DFS on a graph with V nodes and E edges both run in O(V + E), because each node is popped once and each edge is examined once. Topological sort is also O(V + E). Dijkstra with a binary heap is O((V + E) log V); with a Fibonacci heap it's O(V log V + E), though in practice the binary heap wins on real workloads. Bellman-Ford is O(V·E). Floyd-Warshall (all-pairs shortest paths) is O(V³), a polynomial blow-up that's only justified when you actually need all pairs.

Recognising graph problems

Some problems say "graph" in the title. Most do not. A problem is a graph problem when (a) there are discrete entities, (b) some relation connects them, and (c) you are asked a question about paths, reachability, connectivity, or ordering. Grid problems ("shortest path in a maze") are graph problems where each cell is a node and adjacency is the graph structure. Dependency problems ("can you finish all courses given prerequisites?") are topological-sort problems. Network problems (routing, flow, matching) are graph problems with specific algorithmic pedigrees. The recognition is half the work.

Where beginners go wrong

• Forgetting the visited set. In trees you don't need one; in graphs you always do. Without it, a cycle produces infinite recursion.
• Using DFS for unweighted shortest paths. DFS finds paths, but not shortest paths. Use BFS for shortest in terms of edge count.
• Using Dijkstra on graphs with negative weights. Dijkstra's correctness argument depends on edge weights being non-negative. Use Bellman-Ford if you have negatives.
• Representing graphs as matrices by default. For sparse graphs, adjacency lists are orders of magnitude more memory-efficient and almost always faster in practice.

What to read next

Continue with Module 08 · Sorting & Searching, which covers the algorithms graph code quietly depends on. Dynamic programming reappears inside graph algorithms. Bellman-Ford is a DP, and the Floyd-Warshall all-pairs shortest-path algorithm is a three-layer DP over the vertex set.