Graph Algorithms

Graph algorithms interview questions

BFS, DFS, topological sort, shortest-path, union-find. Graph problems show up disguised as ‘connectivity’, ‘dependency’, ‘maze’, ‘islands’. Recognize the graph; the algorithm is the easy part.

BFS — shortest path in unweighted graphs

Level-order traversal, queue-based. Used for: shortest path in maze, word ladder, graph distance, level-order traversals on trees.

DFS — recursion + backtracking

Stack-based or recursive. Used for: connectivity, cycle detection, topological sort, path-finding, flood fill, island counting.

Topological sort — dependency ordering

DAGs only. Two ways: DFS-based (post-order reverse) or Kahn’s algorithm (in-degree). Used for: course scheduling, build systems, task ordering.

Shortest path — Dijkstra and friends

Dijkstra for non-negative weights, Bellman-Ford for negative weights, Floyd-Warshall for all-pairs. Knowing when to use which matters more than memorizing implementations.

Union-Find — connectivity in O(α(n))

Disjoint Set Union. Used for: Kruskal’s MST, dynamic connectivity, redundant connection detection, account merging.

Recognizing graph problems in disguise

Most graph problems aren’t explicitly graphs. Islands, mazes, dependency chains, word transformations — all graphs. Recognition first; algorithm second.

Recognition cues

Recognize a graph problem in disguise

Most graph interview questions don’t say ‘graph’. They say ‘islands’ or ‘course schedule’. Here’s how to spot graphs fast.

Grid + adjacency — “island”, “flood fill”, “maze”, “number of regions”. The grid is the graph; adjacent cells are edges.
Dependency — “course schedule”, “build order”, “task scheduling”. Dependencies are directed edges → topological sort or cycle detection.
Connectivity — “friend circles”, “number of connected components”, “redundant connection”. Union-find shines here.
Word/state transformation — “word ladder”, “open the lock”. States are nodes; valid transitions are edges → BFS.
Shortest/longest path with weights — explicit graphs → Dijkstra, Bellman-Ford, or Floyd-Warshall.

BFS vs DFS — when to use which

Use case	BFS	DFS
Shortest path in unweighted graph	✅ Use this	❌ Don’t
All connected components	✅ Works	✅ Often easier (recursion)
Detect cycle in undirected graph	✅ Works	✅ Cleaner
Topological sort	❌ Use Kahn’s (different from BFS)	✅ Post-order DFS
Path with state (visited set)	✅ Layer-by-layer	✅ Backtrack natural
Island counting	✅ Works	✅ Most common choice

The 8 most common graph interview questions

Number of islands — Grid + DFS/BFS (the canonical ‘graph in disguise’)
Course schedule (I and II) — Topological sort, cycle detection
Word ladder — BFS on state graph
Clone graph — DFS/BFS with hashmap
Number of connected components — Union-find or DFS
Pacific Atlantic water flow — Multi-source DFS from edges
Network delay time — Dijkstra
Redundant connection — Union-find

Union-find in 60 seconds

Union-find (Disjoint Set Union) is the underrated graph algorithm. Three operations: find(x), union(x, y), is-same-set(x, y). With path compression and union by rank, all operations are effectively O(1) (technically O(α(n))) amortized.

Build it once, then forget the details. The implementation is 20 lines. Once written, you stop thinking about it.
Use when connectivity matters. “Are these two nodes in the same group?” or “How many groups are there?”
MST and Kruskal’s. Minimum spanning tree builds union-find under the hood.

Full deep-dive on graph algorithms: Graph algorithms — complete pattern guide and interview questions.

Frequently asked questions

How do I know if a problem is a graph problem?

Most graph problems aren't labeled 'graph'. Watch for these cues: grid + adjacency (islands, mazes), dependency chains (course schedule), connectivity questions (friend circles), state transformations (word ladder), or any 'shortest/longest path' question. The graph is usually implicit.

Should I learn graphs as adjacency lists or matrices?

Adjacency lists for sparse graphs (most interview problems). Adjacency matrices for dense graphs or when you need O(1) edge existence checks. Most FAANG problems use sparse graphs, so default to adjacency lists. For grid problems, the grid itself is the graph — no separate representation needed.

BFS or DFS — which one should I use?

BFS for shortest path in unweighted graphs (only BFS guarantees minimum distance per level). DFS for everything else — connectivity, cycle detection, topological sort, path-finding with state. Default to DFS unless you need shortest path.

How important is Dijkstra's for FAANG interviews?

Important enough to know cold. Comes up in ~10-15% of graph interview rounds at FAANG. You need the priority-queue implementation memorized, plus understanding of when it fails (negative weights → use Bellman-Ford instead).

Can AI tools help with graph interview practice?

Yes. PhantomCode's coach grades your graph recognition speed — how fast you identify the underlying graph from a problem statement. The drills also cover the algorithm selection step (BFS vs DFS vs Dijkstra vs union-find), which is where many candidates choose wrong.