Graph Algorithms That Show Up Everywhere (And How to Spot Them)

Graph problems have a reputation for being exotic. They're not. Once you learn five core primitives, you'll start seeing graph structure in problems that don't even mention "graph" in the title.

BFS: shortest path in unweighted graphs

BFS explores a graph level by level. The first time you reach a node, you've found the shortest path to it (in terms of edge count). This makes BFS the right tool for:

• Shortest path in an unweighted graph
• Finding all nodes within k hops
• Multi-source BFS (start from multiple sources simultaneously)

LeetCode signal: "minimum steps to reach..." or "minimum operations to transform..."

Word Ladder is the canonical example: each word is a node, two words are connected if they differ by one letter. Find the shortest path from start to end word.

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    queue = deque([(beginWord, 1)])
    while queue:
        word, length = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word == endWord:
                    return length + 1
                if next_word in wordSet:
                    wordSet.remove(next_word)
                    queue.append((next_word, length + 1))
    return 0

DFS: connectivity and cycle detection

DFS dives deep before backtracking. Use it for:

• Checking if a graph is connected
• Detecting cycles
• Topological sort (with a modification)
• Finding all paths between two nodes

LeetCode signal: "all possible paths..." or "can you reach..." or "detect cycle..."

Dijkstra: shortest path in weighted graphs

When edges have weights, BFS can't be used directly. Dijkstra uses a min-heap to always extend the cheapest known path:

import heapq

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

LeetCode signal: "minimum cost path..." with weighted edges.

Union-Find: connected components and cycle detection in undirected graphs

Union-Find (Disjoint Set Union) is the cleanest structure for grouping nodes into components and checking if two nodes are in the same component:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already connected — adding this edge creates a cycle
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

LeetCode signal: "number of connected components", "redundant connection", "accounts merge"

Topological Sort: ordering with dependencies

For directed acyclic graphs where you need to order nodes such that every edge points forward:

from collections import deque

def topological_sort(n, prerequisites):
    in_degree = [0] * n
    graph = [[] for _ in range(n)]
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == n else []  # empty = cycle exists

LeetCode signal: "course schedule", "task ordering", "dependency resolution"

The meta-skill: graph modeling

The hardest part isn't the algorithm — it's recognizing that a problem is a graph problem and modeling it correctly. Ask:

• What are the nodes? (states, positions, words, people)
• What are the edges? (valid transitions, connections, relationships)
• Is the graph directed or undirected?
• Are edges weighted?

Once you've answered those four questions, the algorithm choice is usually obvious.