MST & Advanced Graph Algorithms

Minimum spanning tree (MST)

Given a connected, undirected, weighted graph, a spanning tree connects all V nodes with V − 1 edges. The MST is the spanning tree with minimum total weight.

Both classic algorithms rely on the cut property: for any split of the nodes into two groups, the cheapest edge crossing the split belongs to some MST.

Kruskal's algorithm (sort edges + DSU)

Process edges from cheapest to most expensive; add an edge if it connects two different components.

def kruskal(n, edges):                   # edges: (w, u, v)
    edges.sort()
    dsu = DSU(n)                         # from the Union-Find topic
    total = used = 0
    for w, u, v in edges:
        if dsu.union(u, v):
            total += w
            used += 1
            if used == n - 1:
                break
    return total if used == n - 1 else -1   # -1: graph not connected

long long kruskal(int n, vector<array<int,3>>& edges) {   // {w, u, v}
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long total = 0; int used = 0;
    for (auto& [w, u, v] : edges)
        if (dsu.unite(u, v)) { total += w; if (++used == n - 1) break; }
    return used == n - 1 ? total : -1;
}

O(E log E). Best for sparse graphs given as edge lists.

Prim's algorithm (grow a tree with a heap)

Start from any node; repeatedly add the cheapest edge leaving the tree.

import heapq

def prim(n, adj):                        # adj[u] = [(v, w)]
    seen = [False] * n
    pq = [(0, 0)]                        # (cost to attach, node)
    total = count = 0
    while pq and count < n:
        w, u = heapq.heappop(pq)
        if seen[u]:
            continue
        seen[u] = True
        total += w
        count += 1
        for v, wv in adj[u]:
            if not seen[v]:
                heapq.heappush(pq, (wv, v))
    return total if count == n else -1

For dense / complete graphs (e.g. all pairs of points), the O(V²) array version beats both:

def min_cost_connect_points(points):
    n = len(points)
    INF = float("inf")
    best = [INF] * n                     # cheapest edge from the tree to each node
    best[0] = 0
    in_tree = [False] * n
    total = 0
    for _ in range(n):
        u = min((i for i in range(n) if not in_tree[i]), key=best.__getitem__)
        in_tree[u] = True
        total += best[u]
        for v in range(n):
            if not in_tree[v]:
                d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                if d < best[v]:
                    best[v] = d
    return total

Bridges and articulation points (Tarjan)

• A bridge is an edge whose removal disconnects the graph.
• An articulation point is a vertex whose removal disconnects the graph.

DFS assigns each node a discovery time disc[u] and a low-link low[u] = the earliest discovery time reachable from u's subtree using at most one back edge.

• Tree edge (u, v) is a bridge iff low[v] > disc[u] (v's subtree can't reach u or above without it).
• u is an articulation point iff (u is the root and has ≥ 2 DFS children) or (u is not the root and some child v has low[v] >= disc[u]).

def critical_connections(n, connections):
    adj = [[] for _ in range(n)]
    for u, v in connections:
        adj[u].append(v)
        adj[v].append(u)
    disc = [-1] * n
    low = [0] * n
    timer = 0
    bridges = []

    def dfs(u, parent):
        nonlocal timer
        disc[u] = low[u] = timer
        timer += 1
        for v in adj[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append([u, v])
            else:
                low[u] = min(low[u], disc[v])   # back edge
    for u in range(n):
        if disc[u] == -1:
            dfs(u, -1)
    return bridges

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    vector<vector<int>> adj(n), res;
    for (auto& e : connections) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    vector<int> disc(n, -1), low(n, 0);
    int timer = 0;
    function<void(int,int)> dfs = [&](int u, int p) {
        disc[u] = low[u] = timer++;
        for (int v : adj[u]) {
            if (v == p) continue;
            if (disc[v] == -1) {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u]) res.push_back({u, v});
            } else low[u] = min(low[u], disc[v]);
        }
    };
    for (int u = 0; u < n; u++) if (disc[u] == -1) dfs(u, -1);
    return res;
}

Strongly connected components (SCC)

In a directed graph, an SCC is a maximal set where every node reaches every other. Collapsing SCCs gives a DAG (the condensation), which you can then process with topological order.

Kosaraju's algorithm: (1) DFS on the graph recording finish order; (2) DFS on the reversed graph in decreasing finish order — each tree is one SCC.

def kosaraju(n, adj):
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)
    seen, order = [False] * n, []
    def dfs1(u):
        seen[u] = True
        for v in adj[u]:
            if not seen[v]:
                dfs1(v)
        order.append(u)
    for u in range(n):
        if not seen[u]:
            dfs1(u)
    comp = [-1] * n
    def dfs2(u, c):
        comp[u] = c
        for v in radj[u]:
            if comp[v] == -1:
                dfs2(v, c)
    c = 0
    for u in reversed(order):
        if comp[u] == -1:
            dfs2(u, c)
            c += 1
    return comp, c                   # component id per node, number of SCCs

Tarjan's SCC algorithm does it in one DFS using low-links and a stack. Applications: 2-SAT, finding “mother vertices”, simplifying dependency graphs.

Eulerian paths (Hierholzer)

An Eulerian path uses every edge exactly once.

• Undirected: exists iff 0 or 2 vertices have odd degree (and edges are connected).
• Directed: at most one node with out − in = 1 (start), one with in − out = 1 (end), all others balanced.

Hierholzer: DFS consuming edges; append a node after all its edges are used; reverse at the end.

from collections import defaultdict

def find_itinerary(tickets):
    adj = defaultdict(list)
    for a, b in sorted(tickets, reverse=True):
        adj[a].append(b)                 # reversed sort → pop() gives the smallest
    route = []
    def visit(u):
        while adj[u]:
            visit(adj[u].pop())
        route.append(u)
    visit("JFK")
    return route[::-1]

Also: Cracking the Safe (de Bruijn sequence as an Eulerian circuit).

Binary lifting (k-th ancestor, LCA)

Precompute up[j][v] = the 2ʲ-th ancestor of v. Any jump of k steps decomposes into powers of two.

class TreeAncestor:
    def __init__(self, n, parent):
        self.LOG = max(1, n.bit_length())
        self.up = [parent[:]]
        for j in range(1, self.LOG):
            prev = self.up[-1]
            self.up.append([prev[prev[v]] if prev[v] != -1 else -1 for v in range(n)])

    def getKthAncestor(self, node, k):
        for j in range(self.LOG):
            if k >> j & 1:
                node = self.up[j][node]
                if node == -1:
                    return -1
        return node

LCA with binary lifting: lift the deeper node to the same depth, then lift both together from the highest power down while their ancestors differ; the parent is the LCA. O(log n) per query.

Functional graphs (out-degree ≤ 1)

When every node has at most one outgoing edge (next[i]), each component is a cycle with trees hanging into it. Walk from each unvisited node with timestamps; revisiting a node from the current walk reveals a cycle and its length. Used in Longest Cycle in a Graph, Maximum Employees to Be Invited to a Meeting.

Complexity summary