Graphs

Graphs show up in interviews more than almost any other data structure because so many real problems are secretly graphs: friend networks, road maps, course prerequisites, word ladders, image grids. A graph is just a set of nodes (vertices) connected by edges. Edges can be directed (one-way, like "course A must come before course B") or undirected (two-way, like "these two people are friends"), and they can be weighted (each edge has a cost, like distance or time) or unweighted (every edge counts the same).

Representations. The two workhorses are the adjacency list and the adjacency matrix. An adjacency list maps each node to a list of its neighbors — this is compact (O(V+E) space) and is what you'll use in almost every interview problem. An adjacency matrix is a V x V grid where cell (i, j) is truthy if an edge exists between i and j; it costs O(V^2) space but gives O(1) edge lookups, which occasionally matters for dense graphs. Grids (2D arrays of cells) are graphs in disguise: each cell is a node, and its up/down/left/right neighbors are its edges.

The core traversal toolkit.

DFS (depth-first search) dives as deep as possible before backtracking, using recursion or an explicit stack. Reach for DFS when you need to explore every path, detect connectivity, find any path (not necessarily shortest), or when a problem naturally decomposes into "solve this cell, then recurse into its neighbors" — cloning a graph, counting connected components, or finding the longest path in a DAG with memoization.

BFS (breadth-first search) explores level by level using a queue. BFS is the tool for "shortest path in an unweighted graph" because it visits nodes in increasing order of distance from the source — the first time you reach a target, you've found the shortest route. BFS is also the natural fit for "multi-source spreading" problems (infection spreading through a grid, rotting oranges) where you seed the queue with every starting point at once and let time increase one BFS layer at a time.

Union-Find (disjoint set union, DSU) answers "are these two nodes connected" and "merge these two groups" without doing a full traversal each time. Each node points to a parent; find walks up to the root (with path compression, flattening the chain as it goes), and union attaches one root under another (using union by rank/size to keep trees shallow). This combination gives near-O(1) amortized time per operation. Union-Find shines whenever a problem is fundamentally about "which group does this belong to" over a sequence of merge operations, rather than about paths or distances.

Dijkstra's algorithm finds shortest paths in a weighted graph with non-negative edge weights. It's a greedy BFS variant that always expands the closest known unvisited node next, using a min-heap (priority queue) keyed on current best distance. Whenever weights are negative, Dijkstra breaks down and you'd need Bellman-Ford instead — but for interview-level problems, non-negative weights are the norm.

Recognizing which tool a problem wants. "Shortest path, unweighted" -> BFS. "Shortest path, weighted, non-negative" -> Dijkstra. "Are these connected, or merge groups over time" -> Union-Find. "Does a cycle exist in a directed graph, or can these items be ordered" -> topological sort, either DFS-based (using a recursion-stack "currently visiting" set to catch back edges) or Kahn's algorithm (BFS-based, repeatedly removing nodes with in-degree zero).

BFS template (pseudocode):

queue = [start]
visited = {start}          # mark visited when ENQUEUED, not when dequeued
distance = {start: 0}
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            distance[neighbor] = distance[node] + 1
            queue.append(neighbor)

Union-Find template (pseudocode):

parent = {x: x for x in nodes}
rank = {x: 0 for x in nodes}

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   # path compression
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1

Complexity. DFS and BFS both run in O(V + E) time and O(V) space. Union- Find with path compression and union by rank runs in O(alpha(V)) amortized per operation, where alpha is the inverse Ackermann function — effectively constant for any realistic input size. Dijkstra with a binary heap runs in O(E log V) time and O(V) space.

Common pitfalls. In BFS, mark a node visited the moment you enqueue it, not when you dequeue it — otherwise the same node can be pushed onto the queue multiple times before it's ever processed, wasting time and sometimes producing wrong distances. When detecting cycles, remember that undirected graphs need a "don't immediately walk back to your parent" check, while directed graphs need a proper "currently on the recursion stack" set (a node can be fully visited overall but still safe to revisit from a different branch). And in grid problems, guard every neighbor step with boundary checks (0 <= r < rows and 0 <= c < cols) before you index into the grid, and double- check your direction deltas — a swapped row/column offset is a classic silent bug.

This subject walks through ten classic problems that put these ideas into practice: cloning a graph, counting islands, multi-source infection spread, bipartite validation, the longest increasing path in a matrix, word-ladder shortest transformation, union-find community merging, course-schedule cycle detection, Dijkstra's shortest path, and a minimum-spanning-tree problem for connecting points on a plane.