Graph Algorithms

Graph Fundamentals

A graph is a data structure consisting of nodes (vertices) and edges that connect pairs of nodes. Graphs are used to represent relationships, networks, and connections in various domains. Understanding graph algorithms is essential for solving problems involving networks, social connections, routing, and more.

Graphs can be:

• Directed: Edges have a direction (A → B)
• Undirected: Edges have no direction (A — B)
• Weighted: Edges have associated weights/costs
• Unweighted: All edges are equal

Common graph representations include adjacency lists and adjacency matrices. In this chapter, we'll explore fundamental graph traversal, pathfinding, and analysis algorithms.

Prerequisites: Before studying graph algorithms, you should understand trees (see Trees), as trees are a special case of graphs and many graph traversal concepts build upon tree traversal.

Graph Algorithms

This chapter covers 7 core graph algorithms in depth, plus topological sort, strongly connected components and minimum spanning trees below:

Union-Find Data Structure

The Union-Find data structure, also known as Disjoint Set Union (DSU), is a powerful data structure used to efficiently manage and query disjoint sets. It provides an elegant solution for tracking which elements belong to the same set and for merging sets together.

Union-Find uses path compression and union by rank optimizations to achieve nearly constant amortized time complexity. It's essential for problems involving connected components, cycle detection, and minimum spanning trees.

Shortest Path Algorithms

Finding the shortest path between nodes is a fundamental graph problem. Different algorithms are used depending on whether the graph is weighted or unweighted, and whether it contains negative edges.

BFS for Unweighted Graphs

For unweighted graphs, BFS finds the shortest path in terms of number of edges. This is because BFS explores nodes level by level, ensuring the first path found is the shortest.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It uses a priority queue to always explore the closest unvisited node first.

Time complexity: O((V + E) log V) with a binary heap, or O(V²) with an array. See the Dijkstra's Algorithm page for detailed explanation, implementation, and examples.

Bellman-Ford Algorithm

Bellman-Ford can handle graphs with negative edge weights (but not negative cycles). It relaxes edges repeatedly to find shortest paths.

Time complexity: O(V × E). See the Bellman-Ford Algorithm page for detailed explanation, implementation, and examples.

Floyd-Warshall Algorithm

Floyd-Warshall finds shortest paths between every pair of vertices in a weighted graph. It's a dynamic programming approach that works for graphs with negative weights (but not negative cycles).

Time complexity: O(V³). See the Floyd-Warshall Algorithm page for detailed explanation, implementation, and examples.

A* Algorithm

A* is a heuristic-based pathfinding algorithm that combines Dijkstra's optimality with best-first search efficiency. It uses a heuristic function to guide the search toward the goal.

Time complexity: O(b^d) worst case, but much better with a good heuristic. See the A* Algorithm page for detailed explanation, implementation, and examples.

Topological Sort

Given a directed acyclic graph (DAG), produce a linear ordering of vertices such that every edge u → v places u before v. This is the algorithm behind build systems, package managers, task schedulers, course prerequisites, and spreadsheet recalculation — anywhere dependencies must be resolved in a valid order.

A topological order exists if and only if the graph is acyclic. Both algorithms below detect cycles as a side effect, which is usually how "circular dependency" errors get reported.

Kahn's Algorithm (BFS-based)

Repeatedly take a vertex with no remaining incoming edges, output it, and remove its outgoing edges.

from collections import deque

def topological_sort(graph, n):
    """graph: adjacency list, n vertices. Returns an order, or None if cyclic."""
    in_degree = [0] * n
    for u in range(n):
        for v in graph[u]:
            in_degree[v] += 1

    # Start from every vertex that has no dependencies
    queue = deque(u for u in range(n) if in_degree[u] == 0)
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1          # u is placed, so this dependency is satisfied
            if in_degree[v] == 0:
                queue.append(v)

    # Fewer than n vertices emitted means some cycle never reached in-degree 0
    return order if len(order) == n else None

# Time: O(V + E)    Space: O(V)

Using a min-heap instead of a queue yields the lexicographically smallest valid ordering, at O((V + E) log V) — often wanted for reproducible builds.

DFS-based Topological Sort

Run DFS and push each vertex onto a list when it finishes. Since a vertex finishes only after all of its descendants, reverse finishing order is a valid topological order.

WHITE, GREY, BLACK = 0, 1, 2

def topological_sort_dfs(graph, n):
    colour = [WHITE] * n
    order = []

    def visit(u):
        colour[u] = GREY
        for v in graph[u]:
            if colour[v] == GREY:          # back edge -> cycle -> no valid order
                return False
            if colour[v] == WHITE and not visit(v):
                return False
        colour[u] = BLACK
        order.append(u)                    # record on FINISH
        return True

    for u in range(n):
        if colour[u] == WHITE and not visit(u):
            return None

    return order[::-1]                     # reverse finishing order

Kahn's is usually preferable in practice: it is iterative (no recursion limit), and the queue makes it easy to detect which vertices form the cycle when one exists.

Strongly Connected Components

In a directed graph, a strongly connected component is a maximal set of vertices in which every vertex can reach every other. Contracting each SCC to a single node turns any directed graph into a DAG — the condensation — which is why SCC decomposition is so often the first step in analysing directed graphs. Uses include deadlock detection, 2-SAT solving, finding circular module dependencies, and community detection.

Kosaraju's Algorithm

Two passes of DFS, and conceptually the easier of the two to see why it works:

1. DFS over the graph, pushing vertices onto a stack as they finish.
2. Reverse every edge.
3. Pop vertices off the stack and DFS on the reversed graph; each traversal reaches exactly one SCC.

def kosaraju(graph, n):
    visited = [False] * n
    finish_order = []

    def dfs1(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs1(v)
        finish_order.append(u)

    for u in range(n):
        if not visited[u]:
            dfs1(u)

    # Reverse all edges
    reverse = [[] for _ in range(n)]
    for u in range(n):
        for v in graph[u]:
            reverse[v].append(u)

    visited = [False] * n
    components = []

    def dfs2(u, component):
        visited[u] = True
        component.append(u)
        for v in reverse[u]:
            if not visited[v]:
                dfs2(v, component)

    for u in reversed(finish_order):
        if not visited[u]:
            component = []
            dfs2(u, component)
            components.append(component)

    return components

# Time: O(V + E)    Space: O(V + E) for the reversed graph

Tarjan's algorithm finds the same components in a single DFS pass by tracking, for each vertex, the lowest discovery index reachable from its subtree (its low-link). It is faster in practice and does not need the reversed graph, but the invariant is harder to see. The same low-link technique also finds bridges (edges whose removal disconnects the graph) and articulation points (vertices whose removal does) — both central to network reliability analysis.

Minimum Spanning Trees

A minimum spanning tree connects every vertex of a weighted undirected graph using a subset of edges with the least possible total weight. Two greedy algorithms solve it, and both are covered in detail in Greedy Algorithms:

• Kruskal's — sort all edges by weight and add each one that does not create a cycle, using Union-Find to test. O(E log E). Better on sparse graphs.
• Prim's — grow a single tree from a start vertex, always adding the cheapest edge leaving it, using a priority queue. O(E log V). Better on dense graphs.

Both rest on the cut property: for any partition of the vertices into two sets, the lightest edge crossing the partition belongs to some MST. That single fact is what makes greedy correct here.

Further Graph Topics

Beyond the algorithms covered here, these are the next ones worth learning:

• Maximum flow: Ford-Fulkerson, Edmonds-Karp (O(V E²)), and Dinic's (O(V²E), much faster in practice). The max-flow min-cut theorem connects these to a surprising range of problems that do not look like flow at first sight.
• Bipartite matching: Hopcroft-Karp in O(E√V). Reducible to max flow, but the specialised algorithm is faster.
• Johnson's algorithm: all-pairs shortest paths on sparse graphs with negative weights, in O(V E + V² log V) — see Floyd-Warshall.
• Eulerian and Hamiltonian paths: the first is solvable in linear time (Hierholzer's algorithm), the second is NP-complete. A good illustration of how small a change in problem statement can flip tractability.
• Graph colouring: NP-hard in general; greedy heuristics are used in register allocation.

DFS vs BFS: When to Use Which?

What's Next?

Continue your graph algorithm journey:

• Trees - Review tree fundamentals (prerequisite for graph algorithms)
• Dynamic Programming - Solve optimization problems (Floyd-Warshall uses DP)
• Greedy Algorithms - Kruskal's and Prim's MST algorithms in full, plus the matroid theory that explains why greedy works on graphs
• Union-Find - The structure underpinning Kruskal's