Graph Algorithm Interview Patterns: BFS, DFS, Dijkstra, Topological Sort

By /

Graph Algorithm Interview Patterns: BFS, DFS, Dijkstra, Topological Sort

Graph problems are a staple of coding interviews. The key is pattern recognition: identifying which algorithm to apply based on what the problem asks for. This guide covers the four essential graph algorithms and the exact problem types each solves.

Graph Representations

# Adjacency list (preferred for sparse graphs)
graph = defaultdict(list)
graph[0].append(1)
graph[0].append(2)

# Adjacency matrix (for dense graphs or when edge existence is the question)
matrix = [[0]*n for _ in range(n)]
matrix[0][1] = 1

# Edge list (input format for many problems)
edges = [(0,1), (1,2), (2,3)]
# Convert to adjacency list:
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # for undirected

BFS — Shortest Path in Unweighted Graph

BFS explores level by level, guaranteeing the shortest path in terms of edge count.

from collections import deque

def bfs_shortest_path(graph, start, end):
    queue = deque([(start, [start])])
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == end: return path
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                queue.append((nei, path + [nei]))
    return []  # no path

# Pattern: use BFS for "minimum number of steps/hops/moves"
# LeetCode: 127 Word Ladder, 1091 Shortest Path Binary Matrix, 752 Open Lock

DFS — Connected Components, Cycle Detection, All Paths

def dfs(graph, node, visited, result):
    visited.add(node)
    result.append(node)
    for nei in graph[node]:
        if nei not in visited:
            dfs(graph, nei, visited, result)

# Count connected components:
def count_components(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v); graph[v].append(u)
    visited = set()
    count = 0
    for i in range(n):
        if i not in visited:
            dfs(graph, i, visited, [])
            count += 1
    return count

# Cycle detection (undirected graph):
def has_cycle(graph, node, visited, parent):
    visited.add(node)
    for nei in graph[node]:
        if nei not in visited:
            if has_cycle(graph, nei, visited, node): return True
        elif nei != parent:   # back edge (not to direct parent) = cycle
            return True
    return False

Dijkstra — Shortest Path in Weighted Graph

Use when edges have non-negative weights and you need the shortest distance from one source to all nodes.

import heapq

def dijkstra(graph, src, n):
    # graph[u] = [(cost, v), ...]
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]   # (distance, node)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue  # stale entry
        for cost, v in graph[u]:
            if dist[u] + cost < dist[v]:
                dist[v] = dist[u] + cost
                heapq.heappush(heap, (dist[v], v))
    return dist

# Time: O((V + E) log V) with binary heap
# Pattern: "cheapest/fastest/shortest path with weights"
# LeetCode: 743 Network Delay Time, 787 Cheapest Flights Within K Stops, 1514 Path with Max Probability

Topological Sort — DAG Ordering

Topological sort orders nodes in a DAG such that every edge points from earlier to later. Used for dependency resolution (build systems, course prerequisites).

# Kahn's algorithm (BFS-based):
from collections import deque

def topological_sort(n, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * 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 nei in graph[node]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)

    return order if len(order) == n else []  # empty = cycle detected
# LeetCode: 207 Course Schedule, 210 Course Schedule II, 1203 Sort Items by Groups

Union-Find for Graph Problems

# Faster than DFS for: connected components, cycle detection in undirected graphs
class UF:
    def __init__(self, n):
        self.p = list(range(n))
    def find(self, x):
        if self.p[x] != x: self.p[x] = self.find(self.p[x])
        return self.p[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False  # already connected = cycle
        self.p[px] = py
        return True

# Redundant Connection (LeetCode 684):
def find_redundant_connection(edges):
    uf = UF(len(edges) + 1)
    for u, v in edges:
        if not uf.union(u, v): return [u, v]

Algorithm Selection Guide

Problem Type Algorithm
Shortest path, unweighted BFS
Shortest path, non-negative weights Dijkstra
Shortest path, negative weights Bellman-Ford
All-pairs shortest path Floyd-Warshall
Connected components DFS or Union-Find
Cycle detection (undirected) Union-Find or DFS
Cycle detection (directed) DFS with color marking
Dependency ordering Topological Sort (Kahn)
Minimum spanning tree Kruskal (Union-Find) or Prim

Interview Tips

  • State the algorithm choice before coding: “This is shortest path in an unweighted graph, so BFS”
  • For Dijkstra, always check if d > dist[u]: continue — this handles stale heap entries
  • Topological sort: mention that an empty result from Kahn's means there is a cycle (used for cycle detection in directed graphs)
  • Union-Find is almost always faster to code than DFS for connected component problems — use it when given a choice
  • BFS state is (node, extra_state) — e.g., (node, stops_used) for Cheapest Flights Within K Stops

  • Atlassian Interview Guide
  • Lyft Interview Guide
  • Uber Interview Guide
  • LinkedIn Interview Guide
  • Apple Interview Guide
  • Meta Interview Guide
    • Scroll to Top