Top 10 Graph Algorithms for Coding Interviews (2026)

The short answer

Ten graph algorithms cover roughly 90 percent of coding interviews: BFS, DFS, topological sort, Dijkstra, Bellman-Ford, Floyd-Warshall, Union-Find, Kruskal, Prim, and Kosaraju for strongly connected components. Learn BFS, DFS, topological sort, Dijkstra, and Union-Find first. The other five appear in harder rounds.

Graph problems scare candidates because the input looks unstructured. But there are a small number of templates. Once you know which algorithm to reach for, implementation is mechanical.

This guide covers the ten algorithms you need, with clean Python implementations and the interview problems where each appears. Study patterns 1 through 5 until they are automatic. Patterns 6 through 10 are for senior rounds.

Pattern 1: BFS for shortest path on unweighted graphs

Breadth-first search explores level by level. Each node you reach, you reach by the fewest edges. That property makes BFS the right tool for shortest path on unweighted graphs and for level-order problems on trees.

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

Pattern 2: DFS for connectivity and path enumeration

Depth-first search uses a stack (explicit or recursion). It is the right tool for connectivity, cycle detection, backtracking enumeration, and problems that need the full reachable set.

def dfs(graph, start):
    visited = set()
    def walk(n):
        if n in visited: return
        visited.add(n)
        for nb in graph[n]:
            walk(nb)
    walk(start)
    return visited

For large inputs, use an iterative version with an explicit stack to avoid Python recursion limits.

Pattern 3: Topological sort (Kahn’s algorithm)

You get a linear ordering of nodes where every edge points forward. The classic use is scheduling tasks with dependencies, course prerequisites, build systems.

from collections import defaultdict, deque
def topo_sort(n, edges):
    graph = defaultdict(list)
    indeg = [0] * n
    for a, b in edges:
        graph[a].append(b)
        indeg[b] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            indeg[nb] -= 1
            if indeg[nb] == 0:
                q.append(nb)
    return order if len(order) == n else []

If the result length is less than n, there is a cycle. LeetCode 210 Course Schedule II.

Pattern 4: Dijkstra for shortest path with non-negative weights

A priority queue explores the lowest-known-distance node next. Works on non-negative weights only.

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

LeetCode 743 Network Delay Time. Time complexity O((V + E) log V).

Pattern 5: Union-Find for dynamic connectivity

Also called Disjoint Set Union. Processes a stream of union and find operations in near-constant time per operation with path compression and union by rank.

class UF:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0] * n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1
        return True

Appears in Number of Connected Components, Redundant Connection, Accounts Merge.

Pattern 6: Bellman-Ford for negative weights

Slower than Dijkstra at O(VE) but handles negative edge weights and detects negative cycles. If an edge still relaxes on iteration V, a negative cycle exists.

Pattern 7: Floyd-Warshall for all-pairs shortest path

Three nested loops over nodes. O(V^3). Works with negative weights without negative cycles. Appears in interviews when the problem asks for shortest path between every pair.

def floyd_warshall(dist):
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

Pattern 8: Kruskal for minimum spanning tree

Sort edges by weight. Use Union-Find to add edges that connect new components, skip edges that would form a cycle. Stop when you have V-1 edges.

Pattern 9: Prim for minimum spanning tree with a heap

Alternative to Kruskal. Grow the tree one node at a time, picking the minimum-weight edge to a new node. Priority queue drives the choice.

Pattern 10: Kosaraju for strongly connected components

Two passes of DFS. First pass fills a stack by finish time. Second pass, on the transposed graph in stack order, each DFS tree is one SCC. O(V + E).

Appears in senior interviews for dependency analysis, deadlock detection, software architecture problems.

Common pitfalls to avoid

  • Marking a node visited when popping from the stack or queue instead of when pushing. BFS is correct either way, but DFS with visited-on-pop can revisit nodes.
  • Forgetting to handle disconnected graphs. Many problems assume the input graph is connected; others do not. Check with a loop over all nodes outside the main DFS or BFS.
  • Using Python recursion on graphs with more than a few hundred nodes. Default recursion limit is 1000; use sys.setrecursionlimit or iterate explicitly.
  • Forgetting that Dijkstra on a grid with equal weights is just BFS. The simpler algorithm is always safer.
  • Not transforming the input into an adjacency list first. Repeated scans of an edge list inside the inner loop turn O(V + E) into O(V * E).

Practice routine that works

Pick two problems per algorithm and solve them without looking at code. Do them again a week later; most people remember the structure but forget the edge cases. When you can write Dijkstra from scratch in under 10 minutes, you are ready.

Frequently asked questions

When should I use BFS versus DFS?

BFS for shortest path on unweighted graphs and level-order traversal. DFS for connectivity, cycle detection, backtracking, and problems that need the reachable set. For "find any path" either works; for "find shortest path" BFS.

How is an adjacency list different from an adjacency matrix?

Adjacency list stores neighbors per node, O(V + E) space. Adjacency matrix is V by V, O(V^2) space. Use matrix for dense graphs or when you need O(1) edge lookup. Use list for sparse graphs, which is most interview cases.

Does Dijkstra work with negative edges?

No. Dijkstra assumes once a node is settled, its distance is final. Negative edges break that invariant. Use Bellman-Ford for negative weights or SPFA for a faster average case.

What is the time complexity of Union-Find?

With path compression and union by rank, O(alpha(n)) per operation, where alpha is the inverse Ackermann function. For practical input sizes, this is effectively constant.

How many of these ten algorithms show up in a typical FAANG interview?

Usually one or two per loop. Across a full interview loop (4 to 5 rounds), expect BFS or DFS at least once, topological sort or Dijkstra for a medium round, Union-Find for a hard round. The MST and SCC patterns are rare but appear in senior interviews.

How do I represent a graph in Python efficiently?

defaultdict(list) for adjacency list is the standard choice. For weighted graphs, store tuples: graph[u].append((v, weight)). For grids, do not build a graph; just use the 2D coordinates and the four-direction delta pattern.

Final checklist before the interview

Verify you can write BFS, DFS, topological sort, Dijkstra, and Union-Find from scratch in under 10 minutes each. Verify you can convert a 2D grid problem into graph form without drawing adjacency lists on paper. Practice articulating time complexity out loud; most interviewers care more about this than the code itself. If you are slow on any one of the five core algorithms, drill that one every day for a week before anything else.

Leave a Comment