Advanced Graph Patterns for Coding Tests

On graph problems, the choice of algorithm made from reading the constraints separates a pass from a fail more often than implementation skill does.

Criteria for choosing an algorithm

Time limit failures on graph problems usually come from picking the wrong algorithm, not from a wrong solution. Whether edges are weighted, whether negative edges exist, and whether the distance is from one source or between all pairs are what decide the choice. Reading the constraints first and splitting them in a table fixes the direction before any code is written.

Below are the constraints that come up most often and the algorithm each one implies. V is the number of vertices and E the number of edges; the complexities are the standard worst case for each algorithm.

A directed acyclic graph (DAG) is a directed graph with no cycles, used to express task ordering or precedence. The last two rows of the table are not distance problems; they cover connectivity and ordering.

Drawing the constraints as a tree makes the choice clearer. The diagram below splits shortest-path algorithms by weights, negative edges, and whether all pairs are needed.

Without weights, a single breadth-first search finishes the job. With weights and no negatives it is Dijkstra; once negatives are mixed in it drops to Bellman-Ford.

BFS and Dijkstra

Shortest distances in an unweighted graph come from breadth-first search (BFS). A queue expands the frontier one level at a time, so the distance at which a vertex is first reached is its shortest distance.

With positive weights, replace the queue with a min heap and the algorithm becomes Dijkstra. Pop the nearest vertex, then repeatedly relax: if a path through that vertex is shorter, lower the recorded distance.

The key detail is that the same vertex can enter the heap several times. A new entry is pushed on every distance decrease, so if the popped distance is larger than the recorded shortest distance, it is a stale entry and gets skipped. Omitting that one line means processing the same vertex repeatedly and running slow.

import heapq
 
def dijkstra(n, adj, src):       # adj[u] = [(v, w), ...]
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:          # stale distance entry, discard it
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Number vertices A, B, C, D as 0 through 3 and add the edges A→B(1), A→C(4), B→C(2), B→D(5), C→D(1). The result is as follows.

dist = [0, 1, 3, 4]

A→C costs 4 directly, but A→B→C costs 3 and is shorter, and from there A→C→D settles at 4.

Negative edges and all-pairs shortest paths

Dijkstra is wrong on negative edges. It assumes a distance, once popped and finalized, cannot shrink any further, and a negative edge breaks that assumption.

When negative edges are present, use Bellman-Ford. Relax every edge one fewer time than the vertex count (V-1 rounds); if a distance still shrinks on the Vth round, a negative cycle exists.

Distances between all vertex pairs come from Floyd-Warshall in one pass. Put the intermediate vertex k in the outermost loop and update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) in a triple loop. Being $O(V^3)$, it suits vertex counts in the low hundreds or fewer.

Union-find and minimum spanning trees

Connectivity and cycles are handled by union-find (disjoint set union, DSU). It offers only two operations: find, which returns the set an element belongs to, and union, which merges two sets.

class DSU:
    def __init__(self, n):
        self.p = list(range(n))   # parent pointers
        self.r = [0] * n          # rank (upper bound on tree height)
 
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])   # path compression
        return self.p[x]
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False          # already the same set -> cycle
        if self.r[ra] < self.r[rb]:
            ra, rb = rb, ra       # the higher-rank side becomes the root
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1
        return True

find walks up the parent pointers to the root and applies path compression, attaching every node it passed directly to the root. union makes the side with the larger rank, the upper bound on height, the new root so the tree does not get deeper. With both optimizations, one operation finishes in nearly constant time (the inverse Ackermann function, $O(\alpha(n))$).

When union returns false, the two endpoints were already in the same set, so that edge would form a cycle. Using that property directly gives Kruskal's algorithm for a minimum spanning tree (MST).

def kruskal(n, edges):           # edges = [(w, a, b), ...]
    dsu = DSU(n)
    total = 0
    for w, a, b in sorted(edges):
        if dsu.union(a, b):      # take the edge only if it creates no cycle
            total += w
    return total

Sort edges by ascending weight and take, in order, only those that do not create a cycle. Suppose five vertices are given with the following edges.

(weight, endpoints) = (1, 0-1) (2, 0-2) (3, 1-2) (4, 2-3) (5, 3-4) (6, 2-4)

The edges of weight 1, 2, 4, and 5 are taken; 3 and 6 are dropped because their endpoints are already in the same set and they would form a cycle. The spanning tree therefore has a total weight of 12.

Topological sort and cycle detection

Task ordering and precedence are solved with topological sort. Kahn's method, which processes vertices with in-degree zero first, is the simplest to implement.

Put every vertex with in-degree zero in a queue and pop them one by one, appending each to the result. Remove the outgoing edges of the popped vertex, decrementing the in-degree of its neighbors, and enqueue any that reach zero.

from collections import deque
 
def topo_sort(n, adj):           # adj[u] = [v, ...]
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None   # None means a cycle

If the result is shorter than the vertex count, the queue emptied partway through, and the remaining vertices form a cycle among themselves. One topological sort handles both ordering and cycle detection.

Common mistakes and practice problems

Even with a correct implementation, these are the spots where things go wrong.

• Using Dijkstra on an unweighted graph and paying an unnecessary logarithmic factor.
• Omitting the stale-distance skip in Dijkstra, which slows things down through repeated processing.
• Missing a 1-indexed to 0-indexed conversion and hitting an index error.
• Using recursive DFS and overflowing the stack on a deep graph.

Practicing one problem per pattern is the efficient approach. Below are representative problems from Baekjoon Online Judge (BOJ) and Programmers; difficulties are the solved.ac tier and the Programmers level as of 2026-06.

Each problem turns on a different single line, so writing down which constraint decided the algorithm after solving it makes classification faster on the next one.

Summary

Graph problems are mostly decided at the point where the constraints are read and the algorithm is chosen. Weights and negative edges split BFS, Dijkstra, and Bellman-Ford, and all-pairs distances call for Floyd-Warshall. Union-find is the standard tool for connectivity and cycles, and topological sort for precedence. Remembering the one easily forgotten line in each template, such as the stale-distance skip in Dijkstra or the cycle check in topological sort, is what cuts down mistakes.