Graph Algorithms

A weighted graph attaches a cost to each edge, which breaks BFS: BFS finds minimum edge COUNT, not minimum total weight. Representation drives everything downstream.

from collections import defaultdict

# adjacency list — O(V + E), right for sparse graphs
g = defaultdict(list)
def add_edge(u, v, w, directed=False):
    g[u].append((v, w))
    if not directed:
        g[v].append((u, w))    # do not forget this

# adjacency matrix — O(V^2), O(1) edge lookup
INF = float("inf")
m = [[INF] * n for _ in range(n)]
m[u][v] = w

# edge list — for Kruskal / Bellman-Ford
edges = [(w, u, v), ...]

# BFS gives fewest EDGES. Weighted shortest path needs Dijkstra.

Dijkstra grows a set of settled vertices in non-decreasing distance order, using a min-heap keyed by tentative distance. Each pop settles a vertex; each edge may trigger a decrease-key, implemented in practice by pushing a duplicate and skipping stale pops.

import heapq

def dijkstra(g, src):
    dist = {src: 0}
    parent = {}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue                     # stale entry
        for v, w in g[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u            # for path recovery
                heapq.heappush(pq, (nd, v))
    return dist, parent

# O((V + E) log V). NON-NEGATIVE weights only.

Bellman-Ford relaxes all E edges V−1 times, which suffices because any shortest path uses at most V−1 edges. This gives O(V·E) — slower than Dijkstra but it tolerates negative weights, because it never commits to a vertex being settled.

def bellman_ford(n, edges, src):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0

    for _ in range(n - 1):               # V-1 rounds
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                        # early exit

    for u, v, w in edges:                 # one extra round
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle reachable")
    return dist

# O(V * E) — handles negative weights

Floyd-Warshall is dynamic programming over the set of permitted intermediate vertices: after processing k, dist[i][j] is the shortest path using only vertices 1..k as waypoints. Hence the loop order is non-negotiable — k must be the OUTER loop.

def floyd_warshall(dist):
    n = len(dist)
    for k in range(n):            # k MUST be outermost
        for i in range(n):
            dik = dist[i][k]
            if dik == float("inf"):
                continue
            for j in range(n):
                if dik + dist[k][j] < dist[i][j]:
                    dist[i][j] = dik + dist[k][j]
    for i in range(n):
        if dist[i][i] < 0:
            raise ValueError("negative cycle through", i)
    return dist

# O(V^3) time, O(V^2) space. Negative edges fine.

A topological order exists if and only if the directed graph is acyclic. Two standard algorithms, both O(V+E): Kahn's algorithm repeatedly removes vertices with in-degree zero using a queue and reports a cycle if it terminates before emitting all vertices; the DFS approach emits vertices on post-order and reverses, detecting cycles via a node currently on the recursion stack (grey in the white/grey/black colouring).

from collections import deque, defaultdict

def topo_sort(n, edges):
    g = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:            # u must come before v
        g[u].append(v)
        indeg[v] += 1

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    if len(order) != n:
        raise ValueError("cycle — no valid order exists")
    return order

import graphlib          # stdlib since 3.9
list(graphlib.TopologicalSorter(deps).static_order())

Kruskal sorts all edges by weight and greedily accepts an edge unless it would form a cycle, tested in near-constant time with union-find. Complexity is O(E log E) dominated by the sort.

def kruskal(n, edges):        # edges: (w, u, v)
    dsu = DSU(n)
    mst, total = [], 0
    for w, u, v in sorted(edges):        # cheapest first
        if dsu.union(u, v):              # False => cycle, skip
            mst.append((u, v, w))
            total += w
        if len(mst) == n - 1:
            break                        # spanning tree complete
    return mst, total

# O(E log E) — the sort dominates
# maximum spanning tree: sorted(edges, reverse=True)

Prim maintains a connected tree and repeatedly adds the minimum-weight edge crossing from the tree to an unvisited vertex, using a min-heap of candidate edges. With a binary heap it is O(E log V); with a Fibonacci heap O(E + V log V); with a plain array O(V²), which is actually optimal for dense graphs.

import heapq

def prim(g, start=0):
    visited = set()
    pq = [(0, start)]
    total, edges = 0, 0
    while pq and len(visited) < len(g):
        w, u = heapq.heappop(pq)
        if u in visited:
            continue                 # stale entry
        visited.add(u)               # mark on POP
        total += w
        for v, wt in g[u]:
            if v not in visited:
                heapq.heappush(pq, (wt, v))   # key = EDGE weight,
                                              # not accumulated dist
    return total

# O(E log V). Compare Dijkstra: nd = d + w  <- accumulates

A* orders its frontier by f(n) = g(n) + h(n), where g is the cost so far and h is a heuristic estimate of the remaining cost. If h is admissible (never overestimates) A* returns an optimal path; if h is also consistent/monotone, no node is expanded twice.

import heapq

def astar(start, goal, neighbours, h):
    g = {start: 0}
    pq = [(h(start), 0, start)]
    parent = {}
    while pq:
        f, gu, u = heapq.heappop(pq)
        if u == goal:
            return gu, parent
        if gu > g.get(u, float("inf")):
            continue
        for v, w in neighbours(u):
            ng = gu + w
            if ng < g.get(v, float("inf")):
                g[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng + h(v), ng, v))
    return None, parent

# 4-dir grid: h = abs(dx) + abs(dy)      (Manhattan)
# 8-dir grid: h = octile distance
# h = 0  ->  this IS Dijkstra

A strongly connected component is a maximal set of vertices mutually reachable in a directed graph. Kosaraju finds them with two passes: DFS to get a finishing order, then DFS on the reversed graph in that order.

def kosaraju(n, g, rg):
    seen, order = set(), []

    def dfs1(u):
        seen.add(u)
        for v in g[u]:
            if v not in seen:
                dfs1(v)
        order.append(u)              # finishing order

    for u in range(n):
        if u not in seen:
            dfs1(u)

    comp, sccs = {}, []
    def dfs2(u, cid):
        comp[u] = cid
        sccs[cid].append(u)
        for v in rg[u]:              # REVERSED graph
            if v not in comp:
                dfs2(v, cid)

    for u in reversed(order):
        if u not in comp:
            sccs.append([])
            dfs2(u, len(sccs) - 1)
    return sccs      # contract these -> always a DAG

Ford-Fulkerson repeatedly finds an augmenting path in the residual graph and pushes flow along it. Edmonds-Karp uses BFS to pick shortest augmenting paths, giving O(V·E²); Dinic's algorithm uses level graphs and blocking flows for O(V²·E), and O(E·√V) on unit-capacity graphs.

from collections import deque

def bfs_augment(cap, s, t, parent):
    parent.clear()
    parent[s] = None
    q = deque([s])
    while q:
        u = q.popleft()
        for v, c in cap[u].items():
            if c > 0 and v not in parent:
                parent[v] = u
                if v == t:
                    return True
                q.append(v)
    return False

def edmonds_karp(cap, s, t):
    flow, parent = 0, {}
    while bfs_augment(cap, s, t, parent):
        # bottleneck along the found path
        v, push = t, float("inf")
        while parent[v] is not None:
            u = parent[v]
            push = min(push, cap[u][v]); v = u
        v = t
        while parent[v] is not None:
            u = parent[v]
            cap[u][v] -= push
            cap[v][u] = cap[v].get(u, 0) + push   # RESIDUAL edge
            v = u
        flow += push
    return flow