Graph Algorithms Interview Patterns: BFS, DFS, Dijkstra & Cycle Detection

By /

Graph Algorithms Interview Patterns: BFS, DFS, Dijkstra & More

Graph problems appear in roughly 25% of FAANG algorithm interviews. Mastering BFS, DFS, shortest path, and cycle detection gives you a systematic toolkit for grids, trees, network flow, and dependency problems.

Graph Representations

Choose your representation based on density and operations:

  • Adjacency list — O(V+E) space, O(degree) neighbor lookup. Best for sparse graphs (most interview problems).
  • Adjacency matrix — O(V²) space, O(1) edge existence. Best for dense graphs or when you need quick edge weight lookups.
  • Edge list — O(E) space. Used in Kruskal’s MST algorithm.
from collections import defaultdict, deque

# Build adjacency list
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # undirected

BFS — Breadth-First Search

Use BFS for: shortest path in unweighted graphs, level-order traversal, minimum steps problems.

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    dist = {start: 0}
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist

Grid BFS template (most common in interviews):

def bfs_grid(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    visited = {(start_r, start_c)}
    queue = deque([(start_r, start_c, 0)])  # (row, col, dist)
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    while queue:
        r, c, d = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr,nc) not in visited and grid[nr][nc] != '#':
                visited.add((nr, nc))
                queue.append((nr, nc, d+1))

DFS — Depth-First Search

Use DFS for: cycle detection, topological sort, connected components, path existence, backtracking.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# Iterative DFS (avoids recursion limit)
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node])

Cycle Detection

Undirected graph — track parent in DFS:

def has_cycle_undirected(graph, n):
    visited = set()
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False
    for node in range(n):
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

Directed graph — use 3-color DFS (white/gray/black or 0/1/2):

def has_cycle_directed(graph, n):
    color = [0] * n  # 0=unvisited, 1=in-stack, 2=done
    def dfs(node):
        color[node] = 1
        for neighbor in graph[node]:
            if color[neighbor] == 1:
                return True  # back edge = cycle
            if color[neighbor] == 0 and dfs(neighbor):
                return True
        color[node] = 2
        return False
    return any(color[i] == 0 and dfs(i) for i in range(n))

Dijkstra’s Algorithm — Shortest Path (Weighted)

Time: O((V+E) log V) with min-heap. Use for non-negative edge weights.

import heapq

def dijkstra(graph, src, n):
    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 v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

When to use Bellman-Ford instead: negative edge weights (detect negative cycles). Time: O(V·E).

Union-Find for Connected Components

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

Classic Graph Interview Problems

Problem Algorithm Key Insight
Number of Islands BFS/DFS Mark visited cells, count components
Word Ladder BFS Shortest path, each word = node
Course Schedule DFS cycle detection Directed graph, detect back edge
Network Delay Time Dijkstra Single-source shortest path
Minimum Spanning Tree Kruskal / Prim Union-Find or min-heap
Alien Dictionary Topological sort Build ordering constraints from char pairs
Bipartite Check BFS 2-coloring Alternate colors; conflict = not bipartite

Interview Checklist

  • Clarify: directed vs undirected, weighted vs unweighted, connected vs disconnected
  • Ask: can there be cycles? self-loops? multiple edges?
  • For grid problems: confirm movement directions (4-directional vs 8-directional)
  • Always track visited to avoid infinite loops
  • State whether you’d use BFS (shortest) or DFS (existence/backtracking) and why
  • Know time complexity: BFS/DFS = O(V+E), Dijkstra = O((V+E) log V)

  • DoorDash Interview Guide
  • Atlassian Interview Guide
  • Apple Interview Guide
  • Uber Interview Guide
  • LinkedIn Interview Guide
  • Meta Interview Guide

    • Asked at: Coinbase Interview Guide

    Scroll to Top