Graphs

What it is

A graph models objects as vertices and relationships as edges. Edges may be directed or undirected, weighted or unweighted. Unlike a tree, a graph may contain cycles, disconnected components, or multiple routes between vertices.

Graph algorithms organize exploration so that shared work is not repeated. Enumerating every possible route can take exponential time; breadth-first search and depth-first search visit each vertex and edge only a constant number of times.

Choose a representation first:

• Adjacency list: stores each vertex’s neighbors; usually the best default, using O(V + E) space.
• Adjacency matrix: supports constant-time edge lookup but uses O(V²) space.
• Edge list: convenient when sorting edges or processing connectivity updates.

For an undirected adjacency list, add each edge in both directions. Include isolated vertices even when they never appear in the edge list.

How to recognize it

Look for relationships rather than explicit graph terminology:

• Objects linked by roads, connections, transitions, or dependencies.
• Questions about reachability, connected groups, or separation after removals.
• Minimum numbers of moves or transitions with equal cost.
• Cheapest routes when transitions have different costs.
• Assignments requiring neighbors to receive opposite labels.
• Ordering tasks while respecting prerequisites.
• Connecting all vertices with minimum total edge weight.

Before choosing an algorithm, establish whether edges are directed, whether weights can be negative, whether cycles are possible, and whether the answer concerns one source or every component.

The core technique

1. Traversal: BFS, DFS, and components

Breadth-first search (BFS) explores vertices in increasing distance from a source. With unit-cost edges, the first discovery of a vertex gives its shortest distance. Mark vertices when enqueuing them, not when removing them.

from collections import deque

def bfs(adj, source):
    dist = [-1] * len(adj)
    dist[source] = 0
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

Store a parent on discovery when a route is needed. For multi-source BFS, initialize every source at distance zero. This computes distance to the nearest source. To compute distances to destinations in a directed graph, reverse the edges and start from those destinations.

Depth-first search (DFS) follows one branch before returning. Use recursion or an explicit stack. It is useful for reachability, components, and structural properties.

To find undirected connected components, start a traversal from every unvisited vertex. During each traversal, aggregate size, minimum vertex, or other properties. Each vertex belongs to exactly one component.

For bipartite testing, assign an uncolored start vertex color zero, then assign every neighbor the opposite color. An edge joining equal colors proves failure. Repeat across all components; a self-loop immediately fails.

2. Directed structure: cycles and dependency order

In directed DFS, distinguish unseen, active, and finished vertices. An edge to an active vertex identifies a directed cycle. An edge to a finished vertex does not.

A topological order places every prerequisite before its dependents. It exists only for a directed acyclic graph (DAG). Kahn’s algorithm repeatedly removes vertices with zero indegree:

from collections import deque

def topological_order(adj):
    indegree = [0] * len(adj)
    for neighbors in adj:
        for v in neighbors:
            indegree[v] += 1
    queue = deque(u for u, d in enumerate(indegree) if d == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == len(adj) else None

A topological order also enables dynamic programming. For each edge u → v, propagate the best value from u to v. Minimum gives shortest paths; maximum gives longest paths. Unlike general graphs, DAGs permit longest-path computation efficiently because no cycle can keep extending a route.

For scheduling, a forward pass computes earliest feasible times. A reverse pass, given a completion deadline, computes latest feasible times. Their difference gives scheduling slack.

Reverse-graph processing is useful beyond distances: outdegree elimination can propagate properties backward when a vertex qualifies only after all its successors qualify. The initial qualifying terminals must match the intended definition.

3. Weighted paths and expanded states

Use Dijkstra’s algorithm for nonnegative edge weights. Maintain tentative distances in a min-heap, relax outgoing edges, and ignore stale heap entries.

import heapq

def dijkstra(adj, source):  # adj[u] contains (v, weight)
    dist = [float('inf')] * len(adj)
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d != dist[u]:
            continue
        for v, weight in adj[u]:
            candidate = d + weight
            if candidate < dist[v]:
                dist[v] = candidate
                heapq.heappush(heap, (candidate, v))
    return dist

Multi-source Dijkstra initializes several zero-distance sources. When ties require a preferred source, compare labels such as (distance, source_id) and propagate the complete label.

For weights restricted to zero and one, 0–1 BFS uses a deque: zero-cost relaxations go to the front, unit-cost relaxations to the back. Negative weights require another method, such as Bellman–Ford, unless the graph is a DAG.

When future moves depend on limited resources or previous actions, the visited state must include that information: (vertex, resource_state). Run the appropriate shortest-path algorithm on this expanded graph. If route tie-breaking matters, compute remaining optimal distances and reconstruct by choosing the smallest next step that preserves optimality.

4. Connectivity, spanning trees, and critical structure

Disjoint-set union (DSU) maintains undirected components using find and union. Path compression and union by size make operations nearly constant-time. Store component size at each root. DSU supports additions, not arbitrary deletions; offline deletion queries can sometimes be reversed into additions.

For a minimum spanning tree, Kruskal’s algorithm sorts edges by weight and accepts an edge only when DSU says its endpoints are in different components. Prim’s algorithm instead grows a tree using the cheapest edge crossing its boundary. Disconnected graphs produce a spanning forest.

DFS low-link values identify bridges and articulation vertices. Record each vertex’s discovery time and the earliest discovery reachable from its subtree through tree edges followed by a back edge. A child subtree with low[child] > discovery[parent] makes its tree edge a bridge. For articulation tests, use >=; the DFS root instead needs at least two tree children. Subtree sizes quantify the resulting separated groups.

When analyzing equal-weight spanning-tree choices, process a whole weight group before merging it. Contract lower-weight connectivity, then inspect the resulting multigraph; bridges distinguish forced connections.

Common mistakes

• Using BFS to minimize unequal edge weights.
• Exploring only one component when the property is global.
• Treating directed reachability as undirected connectivity.
• Using vertex-only visited flags when additional state affects legal moves.
• Applying Dijkstra to negative weights.
• Confusing a spanning tree with shortest paths from a source.
• Skipping the parent vertex in bridge DFS; with parallel edges, skip only the parent edge identifier.
• Assuming recursive DFS fits the language’s recursion limit.

Complexity

Let V be vertices and E be edges, including unreachable portions of the input.

• BFS, DFS, topological sorting, and low-link analysis: O(V + E) time, O(V) auxiliary space.
• DAG path passes: O(V + E) time.
• Binary-heap Dijkstra: O((V + E) log V) for simple graphs; lazy heaps may hold O(E) entries.
• 0–1 BFS: O(V + E) time.
• Bellman–Ford: O(VE) time.
• DSU: amortized O(α(V)) per operation, O(V) space.
• Kruskal: O(E log E) time, dominated by sorting.

Adjacency-list storage adds O(V + E) space. For expanded-state searches, substitute the number of states and transitions for V and E.