Graphs

BFS, DFS, Dijkstra, Union-Find — and the four representations interviewers expect you to know cold.

advancedPractice Full theoryPrereq:Trees & BST, Stack & Queue

Start practice Read the theory See all problems

What you'll learn

Represent a graph as an adjacency list, matrix, or implicit grid
Run BFS for shortest path in an unweighted graph
Run DFS for connectivity, cycle detection, and topological sort
Apply Dijkstra for shortest paths with non-negative weights
Use Union-Find (DSU) for connectivity and grouping
Always track visited nodes to avoid infinite loops in cyclic graphs

When to reach for this

Signals (use it)

Things connected by relationships: maps, networks, prerequisites, friends
"Shortest path / fewest steps" in an unweighted graph → BFS
"Number of islands / connected components / can you reach" → DFS or Union-Find
"Course schedule / build order / dependencies" → topological sort
"Cheapest / shortest path with weights" → Dijkstra

Anti-signals (don't)

Acyclic hierarchy with a single root → it's a tree, use tree methods
Negative edge weights → Dijkstra fails, use Bellman-Ford
Tiny fixed structure → maybe direct simulation is clearer

Theory & deep dive

A graph is a set of vertices connected by edges. It's the most general data structure here — trees and linked lists are just special cases — and it models almost any 'things and relationships' problem: maps, networks, dependencies, friendships, states and transitions. The skill interviewers test is recognising a problem is a graph problem, then picking the right traversal.

The good news: a small toolkit covers the vast majority. BFS for shortest paths in unweighted graphs and level exploration. DFS for connectivity, cycle detection, and topological order. Dijkstra for shortest paths with non-negative weights. Union-Find for grouping and dynamic connectivity. Knowing when each applies — and how to represent the graph — is 90% of the battle.

This module covers the representations, the BFS/DFS templates with a visited set, topological sort, Dijkstra, and Union-Find — plus the trap of forgetting to mark nodes visited.

The big idea in plain words

A graph is a map: cities are dots (nodes) and roads are lines (edges) connecting them. A question like 'what's the fewest stops between two cities?' is answered by exploring outward in rings - first everything one stop away, then everything two stops away, like ripples spreading on a pond. That ring-by-ring search is BFS.

Example: counting islands in a grid. Treat each piece of land as a city joined to its neighbouring land cells. Start on one land cell and 'flood' outward to every connected land cell, marking each as visited. Every fresh flood you have to start counts as one more island - simple, and you touch each cell only once.

Vocabulary and representations

Term	Meaning
Directed / undirected	Edges one-way (a→b) or two-way (a—b)
Weighted	Edges carry a cost/distance
Cyclic / acyclic	Has a loop or not (a DAG is a directed acyclic graph)
Degree	Number of edges touching a vertex
Connected component	A maximal set of mutually reachable vertices

Four ways to store a graph — pick by density and access pattern:

Representation	Space	Edge lookup	Best for
Adjacency list	O(V+E)	O(degree)	most problems (sparse graphs)
Adjacency matrix	O(V²)	O(1)	dense graphs, fast edge tests
Edge list	O(E)	O(E)	Kruskal, simple iteration
Implicit grid	—	neighbours = 4/8 cells	matrix/maze problems

Adjacency list is the default. Grid problems are graphs in disguise: each cell is a vertex, edges go to adjacent cells.

Which algorithm? (decision flow)

BFS and DFS templates

Both explore the graph; the difference is the order. BFS uses a queue and explores in expanding rings — so the first time it reaches a node is via the fewest edges, giving shortest paths in unweighted graphs. DFS uses recursion (or a stack) and dives deep before backtracking — ideal for connectivity and ordering. Both must track a visited set, or a cycle sends them into an infinite loop.

Python· BFS shortest path (unweighted)

from collections import deque

def bfs_shortest(graph, start, goal):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        node, dist = q.popleft()
        if node == goal:
            return dist
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)          # mark on enqueue
                q.append((nxt, dist + 1))
    return -1

Python· DFS connectivity (count islands)

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'               # mark visited
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

Watch out

Mark a node visited when you ENQUEUE it in BFS, not when you dequeue it — otherwise the same node gets added to the queue multiple times before it's processed.

Topological sort (dependency ordering)

On a DAG, a topological order lists every vertex before the vertices that depend on it — the classic 'course schedule' / 'build order' problem. Kahn's algorithm (BFS): compute each node's in-degree, start from the zero-in-degree nodes, and repeatedly remove a node and decrement its neighbours' in-degrees. If you can't remove all nodes, the graph has a cycle (no valid order exists).

Python· Topological sort (Kahn's algorithm)

from collections import deque

def topo_sort(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:        # a -> b (a before b)
        adj[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 nxt in adj[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return order if len(order) == n else []   # [] means a cycle

Dijkstra and Union-Find

Dijkstra finds shortest paths from a source in a graph with non-negative weights. It's BFS with a min-heap: always expand the cheapest-so-far node. It fails with negative edges (use Bellman-Ford there).

Union-Find (Disjoint Set Union) tracks which vertices are in the same component under a stream of 'union these two' operations, with near-O(1) find and union using path compression and union by rank. It's the go-to for 'number of connected components', 'redundant connection', and Kruskal's MST.

Algorithm	Use	Complexity
BFS	unweighted shortest path	O(V+E)
DFS	connectivity, cycles, topo	O(V+E)
Dijkstra	non-negative weighted shortest path	O((V+E) log V)
Union-Find	dynamic connectivity, grouping	~O(α(n)) per op

Tip

Grid/maze problems ARE graph problems. Treat each cell as a vertex with edges to its 4 (or 8) neighbours — then BFS gives shortest path, DFS counts regions, no explicit graph build needed.

How to talk about this in the interview

“First, declare it's a graph and name the representation: "I'll model this as an adjacency list — or, since it's a grid, each cell is a node with edges to its four neighbours." Then justify the algorithm by the question: "Fewest steps in an unweighted graph means BFS, because the first time BFS reaches a node it's via the shortest path." Always mention the visited set up front — 'to avoid revisiting in a cyclic graph' — and give O(V+E) (or O((V+E) log V) for Dijkstra).”

Common mistakes

–Forgetting the visited set → infinite loop on cyclic graphs
–Marking visited on dequeue instead of enqueue in BFS → duplicate queue entries
–Using DFS for shortest path in an unweighted graph (BFS is the one that guarantees it)
–Running Dijkstra with negative edge weights (it gives wrong answers — use Bellman-Ford)
–Building an O(V²) adjacency matrix for a sparse graph that fits an O(V+E) list
–Topological sort without detecting the cycle case (order shorter than V)

Complexity summary

BFS and DFS are O(V+E) time and O(V) space. Topological sort (Kahn's) is O(V+E). Dijkstra with a binary heap is O((V+E) log V). Union-Find with path compression and union by rank is near-constant, O(α(n)), amortised per operation.

Practice problems

34 total