Graph Algorithms

Start with the relationship and objective

Store neighbors, not accidental assumptions

An adjacency list includes a list for every vertex, including isolated nodes and destinations with no outgoing edges. Directed u→v adds only that direction. Undirected edges usually add both directions; parallel edges and self-loops need an explicit policy.

def adjacency_list(vertex_count, edges, directed=True):
    graph = [[] for _ in range(vertex_count)]
    for source, destination in edges:
        graph[source].append(destination)
        if not directed: graph[destination].append(source)
    return graph

The adjacency representation stores O(V+E) entries, counting an undirected edge's two incidences only as a constant factor. A dense matrix uses O(V²) space. Neighbor traversal through a matrix can change the cost of an otherwise linear algorithm.

The constructor expects vertex indices from zero through vertex_count−1 and a nonnegative vertex count. It keeps isolated vertices and does not deduplicate parallel incidences. An undirected self-loop appears twice under this incidence convention.

A grid is an implicit graph: cells are vertices and permitted moves are edges. Check bounds, obstacles and whether four or eight neighbors are permitted. Four-neighbor moves change one row or column index by one, never both. Height-based reachability may reverse the direction of the search; a reversed edge rule is not automatically an undirected relation.

DFS remembers what has been entered

Mark a vertex on entry before recursively exploring unvisited neighbors. Otherwise a cycle can revisit the active path forever. Repeat from every unvisited vertex to find all undirected components.

def reachable(graph, start):
    visited = set()
    def visit(node):
        if node in visited: return
        visited.add(node)
        for neighbor in graph[node]: visit(neighbor)
    visit(start)
    return visited

The function returns the reached vertices and creates a fresh set for each query. Every reached vertex must have an adjacency entry, even if that entry is empty.

This visited set means “already entered anywhere.” It is different from an on-path set used to enumerate simple paths. Removing a globally visited mark on return changes the algorithm into repeated path exploration. Tree returns and traversals → use simpler structure when there are no cycles or shared subtrees.

Cloning a graph needs an original-node→clone map before traversing its neighbors. A boolean visited flag alone does not provide the cloned endpoint. Recursive DFS uses stack depth up to O(V); an explicit stack avoids call-depth limits but still needs pending state.

BFS discovers shortest edge counts

A FIFO queue processes increasing edge-distance layers. Mark a vertex when enqueuing, not later when popping, so multiple incoming edges do not enqueue duplicate copies. Its first discovery is a shortest edge-count path.

def shortest_distance(graph, start, is_target):
    from collections import deque
    queue = deque([(start, 0)])
    visited = {start}
    while queue:
        node, distance = queue.popleft()
        if is_target(node): return distance
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
    return -1

Pass a target predicate such as lambda node: node == target. A target source returns zero; no reached target returns −1. To reconstruct one shortest path, also record parent[neighbor]=node at enqueue time. One parent per vertex does not encode every shortest path.

For multi-source BFS, enqueue all distinct sources at distance zero. A first discovery then gives distance to the nearest source. This handles spread from several origins or distance to the nearest marked cell; source ownership ties need a deterministic policy if reported.

Cycles and prerequisites need different state

For a simple undirected graph, a visited neighbor other than the traversal parent signals a cycle. In a multigraph, identify the parent edge rather than skipping every edge to the parent vertex: a parallel edge can itself close a cycle.

For directed DFS, distinguish unvisited, active on the recursive path and finished. An edge to an active vertex closes a directed cycle. An edge to a finished vertex can merely join an already explored branch.

Kahn's topological algorithm counts incoming edges, queues every zero-indegree vertex, removes one and decrements its outgoing neighbors. Processing fewer than V vertices means a directed cycle remains. A topological order respects every prerequisite edge; it need not be unique.

When deriving ordering constraints from adjacent dictionary words, the first differing character contributes an edge. A longer word before its own prefix is inconsistent even when no character-cycle is found. Include characters that have no inferred edges.

Union-Find maintains components

Disjoint Set Union (DSU) stores a representative for each connected component under edge additions. find returns a root; union joins two different roots or reports that the endpoints were already connected. It does not store a traversal path.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, node):
        while node != self.parent[node]:
            self.parent[node] = self.parent[self.parent[node]]
            node = self.parent[node]
        return node
    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b: return False
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
        return True

The class expects n nonnegative and every queried vertex in range(n). Its parent links start as a valid forest. Union by rank attaches the lower-rank root; only equal ranks cause an increment. Rank is a bound used for linking, not the current exact height after compression. With both mechanisms, total operation cost is amortized O(α(V)) in the usual model.

DSU detects redundant undirected edges and supports Kruskal's algorithm. A standard DSU does not directly handle arbitrary edge deletions or directed reachability. A successful union returns True; repeated connections and self-unions return False.

A tentative path can improve

Initialize the source to zero and others to infinity. A strict improvement updates the predecessor. Equal-cost routes can leave the existing predecessor unchanged; a different tie policy must preserve correctness and avoid cycles in reconstruction.

In the example, B is first discovered at cost 8. A→C→B lowers that to 2, and B→D then lowers D to 3. Any policy that freezes B on first discovery misses this route.

Finalize the current minimum, not the first discovery

Pop the smallest tentative distance. If the entry no longer matches the stored distance, discard it as stale. Otherwise nonnegative weights make this current minimum final: another unsettled route cannot cross the frontier and reduce it below that minimum.

def dijkstra(graph, source):
    from heapq import heappop, heappush
    from itertools import count
    serial = count()
    distances = {source: 0}
    heap = [(0, next(serial), source)]
    while heap:
        distance, _, node = heappop(heap)
        if distance != distances[node]: continue
        for neighbor, weight in graph[node]:
            if weight < 0: raise ValueError('negative reachable edge')
            candidate = distance + weight
            if candidate < distances.get(neighbor, float('inf')):
                distances[neighbor] = candidate
                heappush(heap, (candidate, next(serial), neighbor))
    return distances

The function expects finite nonnegative weights and an adjacency entry for each vertex. It returns only reached distances. It rejects a negative edge if encountered; callers still own the complete input contract. A monotonically increasing serial breaks equal-distance heap ties without comparing vertex objects. Do not mark a node final when pushing. Early exit for a target is safe at its current-minimum pop, not at its first discovery.

A lazy heap can retain O(E) entries, with O((V+E) log(V+E)) as a safe general bound. An indexed decrease-key heap has different storage and accounting. The lab sorts a tiny candidate list to display exact priority order; it is not a performance implementation.

Two distance levels replace the heap

When every edge costs zero or one, the ordered frontier needs only two adjacent distance levels. A zero-cost improvement stays at the current level; a one-cost improvement waits behind it. Use a deque: add the first to its front and the second to its back. Strict relaxation, not first-discovery marking, permits a cheaper route to replace an earlier one.

Consider directed edges A→B with cost1, A→C with cost0, and C→B with cost0. Ordinary edge-count BFS prefers the direct route. The minimum weighted cost is instead zero:

def zero_one_bfs(graph, source):
    from collections import deque
    distances, frontier = {source: 0}, deque([(source, 0)])
    while frontier:
        node, distance = frontier.popleft()
        if distance != distances[node]: continue
        for neighbor, weight in graph[node]:
            if weight not in (0, 1): raise ValueError('0/1 weights required')
            candidate = distance + weight
            if candidate >= distances.get(neighbor, float('inf')): continue
            distances[neighbor] = candidate
            entry = (neighbor, candidate)
            if weight == 0: frontier.appendleft(entry)
            else: frontier.append(entry)
    return distances

This function returns reached distances and does not mutate adjacency. Every vertex needs an adjacency entry; labels must be hashable. Invalid encountered weights raise an error. Strict improvement terminates zero-cost cycles. Stored distances identify stale entries without comparing vertex labels. With bounded-cost operations, traversal takes O(V+E) work; lazy frontier storage can take O(E), besides O(V) distances. General nonnegative weights still need another frontier. 0–1 frontier argument ↗

Negative weights and bounded-edge states

Bellman–Ford repeatedly relaxes every edge. Without a reachable negative cycle, a shortest simple path needs at most V−1 edges, so V−1 passes suffice. A further successful relaxation detects a source-reachable negative cycle; unreachable cycles do not affect that source's finite paths.

Which targets have no finite minimum depends on whether they are reachable from such a cycle. State this rather than returning a normal distance for every vertex. Runtime is O(VE); an unchanged pass can stop early.

A weighted directed acyclic graph permits one topological relaxation pass even with negative weights, because dependencies never lead back. For a maximum edge budget, use a separate distance layer for each allowed edge count. Read only the previous layer to enforce that budget. K stops normally permits K+1 edges; check the definition.

Floyd–Warshall adds allowed intermediates

Initialize diagonal distances to zero and each direct edge to its smallest weight if parallel edges exist. Use infinity for missing edges and avoid invalid arithmetic with sentinels. The usual in-place recurrence uses intermediate k as the outer loop; arbitrary loop reordering changes its meaning.

Time is O(V³), storage O(V²). A negative diagonal reveals a negative cycle. Paths that can pass through such a cycle need a separate “unbounded below” result, not a finite shortest-distance claim.

A spanning tree has another objective

An undirected minimum spanning tree connects every vertex without cycles while minimizing total selected edge weight. It does not minimize each source-to-vertex route. In a disconnected graph, the analogous result is a minimum spanning forest.

Kruskal sorts edges by weight and uses DSU to accept an edge only when it joins different components. Prim grows one tree by its cheapest outgoing crossing edge. Their cut argument makes a light crossing edge safe for some MST; ties can produce several optimal trees.

Negative weights are allowed for MSTs, unlike Dijkstra's standard invariant. Counting a source path and summing all connecting edges are different objectives even when both implementations use heaps. Kruskal costs sorting plus near-linear DSU work; Prim's bound depends on its queue implementation.

Use every edge: defer route output until stuck

An Euler route uses every edge exactly once; revisiting vertices is permitted. A Hamiltonian route instead visits vertices, which is a different and generally harder task.

Hierholzer follows unused edges on a stack. When the top has none left, pop that vertex into the output. Reverse the resulting postorder list. Use edge identities so parallel edges remain distinct. Mutating adjacency consumes input unless it was copied.

For directed routes, an open trail has one vertex with outdegree−indegree=1, one with −1 and all others balanced; a circuit has every vertex balanced. The nonzero-degree vertices must be connected in the appropriate underlying support. Undirected routes need zero or two odd-degree vertices and connected non-isolated support. Verify that output uses E edges; do not silently return a partial traversal.

Lexical ordering adds an ordered unused-edge policy and valid start selection. Sorting adjacency in reverse for pop-from-end can provide that policy, but degree and connectivity feasibility still come first.

Check the graph contract and total work

Record direction, parallel edges, self-loops, weights, isolated vertices, source set and objective. DFS/BFS on adjacency lists take O(V+E) traversal work and O(V) auxiliary state; the representation itself also occupies O(V+E). A four-neighbor grid has O(rows·columns) vertices and edges.

Test unreachable targets, several components, repeated edges, a diamond with two discoveries, zero weights, a tempting expensive direct route and a negative cycle when supported. Restore shared grids after path-specific search when the API requires it.

Dynamic Programming → explains layer states and dependency order. It is directly connected to bounded-edge paths, DAG relaxation and all-pairs intermediates.

Sources and related patterns

Traversal and representations ↗ · Weighted path conditions ↗ · Spanning-tree objective and cut property ↗

Heap invariants → and priority keys and ties → explain the ordered frontier used here.