Graphs

Back to Index

Use when: connectivity, shortest weighted path, cycle detection, minimum spanning tree, topological ordering.

Union Find

Best for: connected components, cycle detection in undirected graphs, Kruskal’s MST.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n
 
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # path compression
        return self.parent[u]
 
    def union(self, u, v):
        ru, rv = self.find(u), self.find(v)
        if ru == rv:
            return False  # already connected (cycle)
        if self.rank[ru] < self.rank[rv]:
            ru, rv = rv, ru
        self.parent[rv] = ru
        if self.rank[ru] == self.rank[rv]:
            self.rank[ru] += 1
        return True

Dijkstra (shortest path, weighted)

import heapq
 
def dijkstra(graph, src):
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    heap = [(0, src)]  # (cost, node)
 
    while heap:
        cost, u = heapq.heappop(heap)
        if cost > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

Topological Sort (Kahn’s Algorithm)

from collections import deque
 
def topo_sort(n, edges):
    indegree = [0] * n
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
 
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == n else []  # empty = cycle exists

---

Problems Using This Pattern