Graph Algorithms for Coding Interviews: The 2026 Guide

Graph algorithms for coding interviews come down to six tools: breadth-first search (BFS), depth-first search (DFS), topological sort, Dijkstra's algorithm, union-find, and a minimum spanning tree (MST) algorithm. The hard part is rarely implementing them. It is recognizing which one a problem needs, especially when the problem never uses the word "graph."

This guide gives you a signal-to-algorithm decision table, a Python template for each algorithm, and a practice list ordered by difficulty.

Key Takeaways

• Six algorithms cover nearly every graph question you will see: BFS, DFS, topological sort, Dijkstra, union-find, and MST (Kruskal or Prim).
• "Fewest steps" in an unweighted graph means BFS. Weighted edges with non-negative costs mean Dijkstra. Negative weights or "at most k edges" point to Bellman-Ford.
• Dependencies and ordering mean topological sort. Groups that merge over time mean union-find.
• Most graph problems are disguised as grids, word transformations, locks, or account merging. Your first job is to name the nodes and edges.
• Build an adjacency list as a dict or list of lists and mark nodes visited when you enqueue them. Those two habits prevent most graph bugs in interviews.
• Most templates here run in O(V + E) or O(E log V); Bellman-Ford is the O(V × E) exception. If your solution is much slower than the table says, you probably picked the wrong tool.

The Decision Table: Which Graph Algorithm Fits the Problem?

This table is the core of the guide. Read the problem, find the matching signal, and start from that template. If two rows match, prefer the simpler algorithm.

Two tie-breakers: if every weight is equal, it is really BFS, and if the whole graph is given up front with nothing dynamic, plain DFS is usually shorter than union-find.

How Should You Represent a Graph in an Interview?

An adjacency list is the default representation for interview graphs. It maps each node to its neighbors and uses O(V + E) space, which matches the sparse graphs most problems describe.

from collections import defaultdict

def build_graph(edges, directed=False):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

def build_weighted(edges):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
    return graph

The three representations you should know:

Grids are implicit graphs. Each cell is a node, and its neighbors are the adjacent cells that are in bounds and passable, so you never build an adjacency list for them.

Watch the edge direction in prerequisite problems. LeetCode's Course Schedule gives pairs as [course, prerequisite], so the edge runs from prerequisite to course. Reading that backwards produces a reversed order, a bug that is easy to miss in a live round.

BFS Template: Shortest Paths in Unweighted Graphs

Breadth-first search explores a graph level by level using a queue. Because it reaches nodes in increasing order of distance, the first time BFS reaches a node is along a shortest path, as long as every edge has the same cost.

from collections import deque

def bfs_shortest(graph, start, target):
    queue = deque([start])
    dist = {start: 0}
    while queue:
        node = queue.popleft()
        if node == target:
            return dist[node]
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return -1

Three details separate a clean BFS from a buggy one:

1. Mark visited on enqueue, not dequeue. Otherwise the same node can sit in the queue many times, which can blow up runtime on dense grids.
2. Use collections.deque. Popping from the front of a Python list is O(n); popleft() is O(1).
3. Multi-source BFS is the same template with every source in the queue at distance 0. Rotting Oranges and Walls and Gates are this exact pattern.

For grids, swap the neighbor loop for a direction loop with a bounds check. If the problem asks for the number of levels or minutes, process the queue in batches with for _ in range(len(queue)) and count iterations.

DFS Template: Traversal, Components, and Cycle Detection

Depth-first search follows one branch as far as it goes before backtracking. It is the simplest way to explore everything reachable, count components, and detect cycles.

def count_components(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = set()

    def dfs(node):
        stack = [node]
        seen.add(node)
        while stack:
            cur = stack.pop()
            for nxt in graph[cur]:
                if nxt not in seen:
                    seen.add(nxt)
                    stack.append(nxt)

    components = 0
    for node in range(n):
        if node not in seen:
            dfs(node)
            components += 1
    return components

This version is iterative on purpose. CPython's default recursion limit is 1,000, so a recursive DFS on a 300 by 300 grid can raise RecursionError. Recursive DFS is fine on small inputs; just mention the limit.

Cycle detection in a directed graph

Undirected cycle detection only needs a seen set and a parent check. Directed graphs need three colors, because reaching an already finished node is not a cycle, but reaching a node still on the current path is.

def has_cycle_directed(n, graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True
            if color[nxt] == WHITE and dfs(nxt):
                return True
        color[node] = BLACK
        return False

    return any(color[i] == WHITE and dfs(i) for i in range(n))

BFS vs DFS: which should you pick?

If both work, pick whichever you write with fewer bugs. Correctness and clear reasoning matter more than the choice, as covered in what interviewers look for in coding interviews.

Topological Sort: Ordering With Dependencies

Topological sort orders the nodes of a directed acyclic graph (DAG) so that every edge points from an earlier node to a later one. Kahn's algorithm builds the order by repeatedly removing nodes that have no remaining incoming edges.

from collections import deque

def topo_sort(n, prerequisites):
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == n else []

If the order contains fewer than n nodes, the graph has a cycle and no valid order exists. That one check answers "can you finish all courses" without a separate cycle detector.

Kahn's algorithm is the safer interview choice over DFS post-order: it is iterative and detects cycles for free. Alien Dictionary is the classic disguised version: compare adjacent words, take the first differing character pair as an edge, then topologically sort the letters.

Shortest Paths: Dijkstra and Bellman-Ford

The rule of thumb for weighted shortest paths: non-negative weights mean Dijkstra, and negative weights or an edge-count limit mean Bellman-Ford.

Dijkstra's algorithm

Dijkstra's algorithm finds the shortest path from one source to every node in a graph with non-negative edge weights. It repeatedly expands the node with the smallest known distance, using a min-heap.

import heapq

def dijkstra(n, edges, source):
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue
        for nxt, w in graph[node]:
            nd = d + w
            if nd < dist[nxt]:
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))
    return dist

The if d > dist[node]: continue line matters. Python's heapq module provides a min-heap with no decrease-key operation, so the standard approach pushes a new entry whenever a distance improves and skips stale entries when they are popped. Without it, the code stays correct but does redundant work.

Complexity is O(E log V) with a binary heap. Network Delay Time is the textbook problem. Path With Minimum Effort and Swim in Rising Water use the same loop with a different cost rule (maximum edge on the path instead of the sum).

Bellman-Ford

Bellman-Ford computes single-source shortest paths by relaxing every edge V minus 1 times. It is slower than Dijkstra at O(V × E), but it handles negative edge weights and can detect a negative cycle with one extra pass.

Its most common interview use is not negative weights. It is the "at most k stops" constraint in Cheapest Flights Within K Stops, where round i of relaxation gives the cheapest cost using at most i edges.

def cheapest_with_k_edges(n, flights, src, dst, k):
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(k + 1):
        prev = dist[:]
        for u, v, w in flights:
            if prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return dist[dst] if dist[dst] != float("inf") else -1

Copying prev each round is the detail people miss. Without it, one round can chain several edges together and break the "at most k edges" guarantee.

Floyd-Warshall (all pairs, O(V³)) is worth recognizing by name but rarely needs to be written.

Union-Find: Dynamic Connectivity

Union-find, also called disjoint set union, is a data structure that tracks which elements belong to the same group and merges groups efficiently. With path compression and union by rank, each operation runs in O(α(n)) amortized time, where α is the inverse Ackermann function and is effectively constant.

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

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

union returning False means the two nodes were already connected. That single return value solves Redundant Connection and Graph Valid Tree (a valid tree has exactly n minus 1 edges and no union ever returns False).

Minimum spanning tree with Kruskal

A minimum spanning tree connects every node with the smallest possible total edge weight. Kruskal's algorithm sorts edges by weight and adds each one that joins two different components, which makes it a short extension of the union-find class above.

def kruskal(n, edges):
    uf = UnionFind(n)
    total = 0
    for w, u, v in sorted(edges):
        if uf.union(u, v):
            total += w
    return total if uf.count == 1 else -1

Min Cost to Connect All Points is the standard MST problem. Its graph is dense, so Prim's algorithm with a heap is an equally valid choice.

How Do You Recognize Graph Problems in Disguise?

A graph problem in disguise is any problem where you can name states and the moves between them. Ask two questions: what are the nodes, and what makes two nodes adjacent? If you can answer both, pick from the decision table.

The last row shows the advanced trick: when the same cell can be visited with different information (keys held, obstacles removed), the node becomes a tuple of position plus that state. Only the seen key changes.

Trees are graphs without cycles, so graph traversal is what you learned in our binary tree interview questions guide plus a seen set. Exhaustive path search with undo steps overlaps with recursion and backtracking, and some shortest-path problems on DAGs are really dynamic programming in topological order.

Practice List: 25 Graph Problems in Order

Work through these in order. Each group drills one template before moving on.

BFS and DFS foundations

1. Number of Islands (200)
2. Flood Fill (733)
3. Clone Graph (133)
4. Max Area of Island (695)
5. Pacific Atlantic Water Flow (417)
6. Surrounded Regions (130)

Shortest paths with BFS 7. Rotting Oranges (994) 8. Shortest Path in Binary Matrix (1091) 9. 01 Matrix (542) 10. Word Ladder (127) 11. Open the Lock (752)

Topological sort 12. Course Schedule (207) 13. Course Schedule II (210) 14. Alien Dictionary (269) 15. Minimum Height Trees (310)

Union-find and MST 16. Number of Provinces (547) 17. Redundant Connection (684) 18. Graph Valid Tree (261) 19. Accounts Merge (721) 20. Min Cost to Connect All Points (1584)

Weighted shortest paths 21. Network Delay Time (743) 22. Cheapest Flights Within K Stops (787) 23. Path With Minimum Effort (1631) 24. Swim in Rising Water (778)

Mixed recognition 25. Shortest Path to Get All Keys (864)

These overlap heavily with the graphs sections of the popular curated lists. If you want to know how those lists compare, see Blind 75 vs NeetCode 150 vs Grind 75. For the full set of non-graph patterns, the coding interview patterns cheat sheet uses the same template-first format as this guide.

How to Talk Through a Graph Problem in the Interview

Interviewers grade how you reach the algorithm, not just the final code. Graph problems give you a clean script.

1. Name the graph. "Each cell is a node, and edges connect adjacent land cells."
2. Name the algorithm and why. "All moves cost one, so BFS gives the shortest path."
3. State complexity before coding. O(V + E), or O(rows × cols) for grids. Our Big O notation cheat sheet covers how to phrase it.
4. Call out edge cases. Empty input, disconnected graph, unreachable target, self-loops, and duplicate edges.
5. Trace one small example after coding instead of rereading the code silently.

Our guide on how to think out loud in a coding interview has phrasing that works under pressure.