Advanced Graph Patterns for Coding Tests

In graph problems, choosing an algorithm from the constraints often affects success more than implementation skill does.

Criteria for choosing an algorithm

Graph problems often exceed the time limit because the chosen algorithm is unsuitable. First, identify whether the graph has weights or negative edges. Then determine whether the problem needs distances from one source or between all pairs. A table of these constraints guides algorithm selection before implementation.

The table lists common constraints and their corresponding algorithms. V is the number of vertices, and E is the number of edges. Each complexity is the algorithm's standard worst-case bound.

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.

flowchart TD
    S["Shortest path problem"] --> Q1{"Do the edges<br/>have weights"}
    Q1 -->|No| BFS["Breadth-first search (BFS)<br/>O(V+E)"]
    Q1 -->|Yes| Q2{"Are there<br/>negative edges"}
    Q2 -->|Yes| BF["Bellman-Ford<br/>O(VE)"]
    Q2 -->|No| Q3{"Are all vertex pairs<br/>required"}
    Q3 -->|No| DJ["Dijkstra + min heap<br/>O((V+E) log V)"]
    Q3 -->|Yes| FW["Floyd-Warshall<br/>O(V cubed)"]

Without weights, a single breadth-first search finds the shortest distances. With weights and no negatives, use Dijkstra. With negative weights, use Bellman-Ford.

BFS and Dijkstra

Breadth-first search (BFS) finds shortest distances in an unweighted graph. A queue expands the search one level at a time. The distance at which the search first reaches a vertex 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 same vertex can enter the heap several times. Each distance decrease adds a new entry. If a popped distance exceeds the recorded shortest distance, skip that stale entry. Omitting this check causes repeated processing and slows the algorithm.

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 decreases 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

Union-find (disjoint set union, DSU) handles connectivity and cycles. The find operation returns the set that contains an element. The union operation 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

The find operation follows parent pointers to the root. Path compression then attaches every visited node directly to the root. The union operation chooses the side with the larger rank as the new root. Rank is an upper bound on height, and this choice limits increases in tree depth. With both optimizations, an operation takes 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 algorithm accepts edges with weights 1, 2, 4, and 5. It rejects edges with weights 3 and 6 because their endpoints already belong to the same set. Adding either edge would create a cycle. The spanning tree 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. Pop each vertex and append it to the result. Remove its outgoing edges and decrease the in-degree of its neighbors. Enqueue any neighbor whose in-degree reaches 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 before processing all vertices. The remaining vertices form a cycle among themselves. One topological sort therefore 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.

Practice one problem for each pattern. The table lists representative problems from Baekjoon Online Judge (BOJ) and Programmers. Difficulties use the solved.ac tier and the Programmers level as of 2026-06.

After solving a problem, record which constraint determined the algorithm. These conditions differ between problems. The record helps you classify later problems more quickly.

Summary

Graph problems largely depend on reading the constraints and choosing an algorithm. Weights and negative edges determine the choice between BFS, Dijkstra, and Bellman-Ford. All-pairs distances call for Floyd-Warshall. Union-find handles connectivity and cycles, while topological sort handles precedence.

Each template has an easily omitted check. Examples include the stale-distance check in Dijkstra and cycle detection in topological sort. Remembering these checks reduces mistakes.