Graphs come up in about 35-40% of coding interviews at major tech companies. Social networks, map routing, dependency chains, web crawlers. If you don't know graph patterns, you'll easily fail the interview.
I've seen candidates stuck on problems like "Number of Islands" because they hadn't practiced grid traversal. These problems become straightforward once you know the patterns.
In this post, I'll show you 7 graph algorithms that cover about 85% of graph-related interview questions. For each one, you'll learn what it does, when to use it, how it works, and which LeetCode problems to practice.
This post is based on Repovive's Graph Theory roadmap. Let's get into it.
TL;DR: Algorithm Reference Table
| Algorithm | Use When | Time | Space |
|---|---|---|---|
| BFS | Shortest path in unweighted graph | O(V + E) | O(V) |
| DFS | Cycle detection, connected components | O(V + E) | O(V) |
| Dijkstra | Shortest path in weighted graph | O((V + E) log V) | O(V) |
| Topological Sort | Task scheduling with dependencies | O(V + E) | O(V) |
| Union-Find | Dynamic connectivity, cycle detection | O(α(n)) ≈ O(1) | O(V) |
| Kruskal's MST | Minimum cost to connect all nodes | O(E log E) | O(V) |
| Bipartite Check | 2-coloring, group assignments | O(V + E) | O(V) |
1. Breadth-First Search (BFS)
What it is: You explore a graph level by level. You visit all nodes at distance 1 first, then distance 2, then distance 3.
When to use it:
- Finding the shortest path in an unweighted graph
- Level-order traversal
- Finding all nodes within K distance
- Any problem that asks for "minimum steps" or "shortest path" without weights
How it works:
You use a queue. You start by adding the source node. Then you repeat: remove the front node, process it, and add all its unvisited neighbors to the back of the queue.
The queue enforces the level-by-level order. By the time you reach a node, you've visited all closer nodes first. This guarantees the first path you find is the shortest.
text
queue = [start]
visited = {start}
while queue is not empty:
node = queue.pop_front()
for neighbor in node.neighbors:
if neighbor not in visited:
visited.add(neighbor)
queue.push_back(neighbor)
Grid Problems (Flood Fill)
BFS works well on 2D grids. Each cell is a node. Adjacent cells (up, down, left, right) are neighbors. Problems like "Number of Islands" and "Rotting Oranges" are grid-based BFS.
For flood fill, you start at a cell and spread to all connected cells matching a condition. You stop at boundaries or cells that don't match. This is the algorithm behind the paint bucket tool in image editors.
[DIAGRAM: Grid showing BFS expansion from a starting cell, with numbered levels radiating outward]
Practice these LeetCode problems:
- Shortest Path in Binary Matrix (Medium)
- Rotting Oranges (Medium)
- Number of Islands (Medium)
- 01 Matrix (Medium)
- Word Ladder (Hard)
2. Depth-First Search (DFS)
What it is: You explore as deep as possible before backtracking. If you're at a node with three neighbors, you fully explore the first neighbor's subtree before looking at the second.
When to use it:
- Detecting cycles
- Finding connected components
- Path finding (when you don't need the shortest path)
- Backtracking problems
- Tree traversals
How it works:
Imagine solving a maze with chalk. You pick a path and start walking. You mark your turns. When you hit a dead end, you backtrack to the last unmarked fork and try a different direction.
You use a stack (or recursion, which is an implicit stack). The most recent node gets processed first, pushing you deeper into the graph.
text
function dfs(node):
if node in visited:
return
visited.add(node)
for neighbor in node.neighbors:
dfs(neighbor)
Cycle Detection
You use DFS to detect cycles. The approach differs for directed vs undirected graphs.
For undirected graphs: if you reach a visited node that isn't your immediate parent, you've found a cycle.
For directed graphs: you use three states (unvisited, in-progress, completed). If you reach an in-progress node, you've found a back edge, which means a cycle.
text
// Directed graph cycle detection
state = [UNVISITED] * n
function hasCycle(node):
state[node] = IN_PROGRESS
for neighbor in node.neighbors:
if state[neighbor] == IN_PROGRESS:
return true // cycle found
if state[neighbor] == UNVISITED:
if hasCycle(neighbor):
return true
state[node] = COMPLETED
return false
[DIAGRAM: Graph showing DFS traversal order with numbered nodes, and a separate diagram showing cycle detection with colored states]
Practice these LeetCode problems:
- Clone Graph (Medium)
- Number of Provinces (Medium)
- Max Area of Island (Medium)
- Course Schedule (Medium)
- All Paths From Source to Target (Medium)
3. Dijkstra's Algorithm
What it is: You find the shortest path in a weighted graph with non-negative edge weights. Unlike BFS, you can handle edges with different costs.
When to use it:
- Shortest path with weighted edges
- Navigation and routing (Google Maps)
- Network routing with latency costs
- Any problem mentioning "minimum cost path"
How it works:
BFS doesn't work on weighted graphs because one step doesn't equal one unit of distance. A direct path might cost 10 while a two-step path costs 2.
You use a greedy approach: process the closest unvisited node first. You use a priority queue (min-heap) to find the node with the smallest distance.
text
dist = [infinity] * numNodes
dist[source] = 0
pq = [(0, source)] // (distance, node)
while pq is not empty:
d, node = pq.pop_min()
if d > dist[node]:
continue // found a better path already
for (neighbor, weight) in node.edges:
newDist = d + weight
if newDist < dist[neighbor]:
dist[neighbor] = newDist
pq.push((newDist, neighbor))
Sample Problem: Network Delay Time
You have n network nodes. You're given travel times as directed edges (u, v, w) where w is the time. You send a signal from node k. How long until all nodes receive it?
You run Dijkstra from node k. Your answer is the maximum distance among all reachable nodes. If any node is unreachable, you return -1.
[DIAGRAM: Weighted graph showing Dijkstra's expansion, with distances labeled at each node]
Practice these LeetCode problems:
- Network Delay Time (Medium)
- Path with Minimum Effort (Medium)
- Cheapest Flights Within K Stops (Medium)
- Swim in Rising Water (Hard)
4. Topological Sort
What it is: You order nodes in a directed acyclic graph (DAG) so that for each edge u→v, node u comes before node v. You use this for scheduling tasks with dependencies.
When to use it:
- Course scheduling with prerequisites
- Build systems and dependency resolution
- Task ordering
- Any problem that mentions "prerequisites" or "dependencies"
How it works (Kahn's Algorithm):
A node's in-degree is the number of edges pointing to it. If a node has in-degree 0, it has no dependencies and you can process it.
You start by adding all nodes with in-degree 0 to a queue. You process them one by one. When you process a node, you decrement the in-degree of its neighbors. If a neighbor's in-degree drops to 0, you add it to the queue.
If you process all nodes, you have a valid topological order. If the queue empties before you've processed all nodes, you've found a cycle.
text
inDegree = count incoming edges for each node
queue = all nodes with inDegree 0
result = []
while queue is not empty:
node = queue.pop()
result.append(node)
for neighbor in node.outgoing:
inDegree[neighbor] -= 1
if inDegree[neighbor] == 0:
queue.push(neighbor)
if len(result) < numNodes:
return "cycle detected"
Sample Problem: Course Schedule II
You have numCourses courses. Some have prerequisites: [0, 1] means you take course 1 before course 0. You return any valid order to finish all courses, or an empty array if impossible.
You build a directed graph where edge b→a means "take b before a". You run Kahn's algorithm. If you can't process all courses, you've found a cyclic dependency.
[DIAGRAM: DAG of courses with arrows showing prerequisites, and the resulting topological order]
Practice these LeetCode problems:
- Course Schedule (Medium)
- Course Schedule II (Medium)
- Alien Dictionary (Hard)
- Parallel Courses (Medium)
5. Union-Find (Disjoint Set Union)
What it is: You use this data structure to track elements partitioned into disjoint sets. It supports two operations: find (which set does this element belong to?) and union (merge two sets).
When to use it:
- Dynamic connectivity queries
- Detecting cycles in undirected graphs
- Kruskal's MST algorithm
- Grouping elements as edges are added
How it works:
Each set has a leader (representative). Two elements are in the same set if they have the same leader. You store a parent array where parent[i] points to i's parent. The root is the leader (where parent[i] = i).
You use two optimizations to make operations nearly O(1):
- Path compression: When you find the leader, you make each node on the path point directly to the leader.
- Union by rank/size: When you merge, you attach the smaller tree under the larger tree.
text
parent = [0, 1, 2, ..., n-1] // each node is its own leader
rank = [0] * n
function find(x):
if parent[x] != x:
parent[x] = find(parent[x]) // path compression
return parent[x]
function union(x, y):
px, py = find(x), find(y)
if px == py:
return false // already connected
if rank[px] < rank[py]:
parent[px] = py
else if rank[px] > rank[py]:
parent[py] = px
else:
parent[py] = px
rank[px] += 1
return true
Sample Problem: Redundant Connection
You have a graph that started as a tree (connected, no cycles), then one edge was added. You find the edge that can be removed to restore the tree.
You process edges one by one. For each edge (u, v), you check if u and v are already connected using find(). If yes, this edge creates a cycle. If no, you union them. The first edge that connects already-connected nodes is your answer.
[DIAGRAM: Graph showing Union-Find trees merging as edges are added]
Practice these LeetCode problems:
- Redundant Connection (Medium)
- Number of Provinces (Medium)
- Accounts Merge (Medium)
- Satisfiability of Equality Equations (Medium)
6. Minimum Spanning Tree (MST)
What it is: A spanning tree connects all nodes in a graph using exactly n-1 edges with no cycles. The minimum spanning tree is the one with the smallest total edge weight.
When to use it:
- Connecting all nodes with minimum cost
- Network design (cables, roads, pipelines)
- Clustering algorithms
- Approximation algorithms for NP-hard problems
How it works (Kruskal's Algorithm):
You sort all edges by weight. You process them in order. For each edge, you use Union-Find to check if it connects two different components. If yes, you add it to the MST. If no, you skip it to avoid a cycle.
text
edges.sort(by weight)
mst = []
uf = UnionFind(n)
for edge in edges:
u, v, weight = edge
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append(edge)
if len(mst) == n - 1:
break
return mst
Sample Problem: Min Cost to Connect All Points
You're given points on a 2D plane. The cost to connect two points is their Manhattan distance. You return the minimum cost to connect all points.
You treat each pair of points as a potential edge. You generate all edges, sort by weight, and run Kruskal's. The MST gives you the minimum total cost.
[DIAGRAM: Points on a plane with MST edges highlighted]
Practice these LeetCode problems:
- Min Cost to Connect All Points (Medium)
- Connecting Cities With Minimum Cost (Medium)
- Find Critical and Pseudo-Critical Edges in MST (Hard)
7. Bipartite Graph Check
What it is: A bipartite graph is one you can split into two groups where each edge connects nodes from different groups. No edge connects two nodes within the same group. Another way to think about it: can you 2-color the graph so no adjacent nodes share a color?
When to use it:
- Team or group assignments
- Matching problems
- Checking for odd-length cycles (a graph is bipartite if and only if it has no odd-length cycles)
- Scheduling with conflicts
How it works:
You use BFS or DFS. You assign the starting node color 0. You assign all its neighbors color 1. You assign their neighbors color 0. You continue alternating.
If you try to assign a color to a node that already has the opposite color, the graph isn't bipartite.
text
color = [-1] * n // uncolored
function isBipartite(start):
queue = [start]
color[start] = 0
while queue is not empty:
node = queue.pop()
for neighbor in node.neighbors:
if color[neighbor] == -1:
color[neighbor] = 1 - color[node]
queue.push(neighbor)
else if color[neighbor] == color[node]:
return false
return true
Sample Problem: Is Graph Bipartite?
You're given an undirected graph. You return true if it's bipartite.
You run BFS from each unvisited node to handle disconnected components. You try to 2-color the graph. If you succeed for all components, the graph is bipartite.
[DIAGRAM: Graph with nodes colored in two colors, showing the bipartite partition]
Practice these LeetCode problems:
- Is Graph Bipartite? (Medium)
- Possible Bipartition (Medium)
What to Do Next
You now have 7 algorithms that cover most graph problems in coding interviews. Here's how to retain them:
-
Practice in order. Start with BFS and DFS. They're the foundation the others build on.
-
Match patterns to algorithms. "Shortest path" without weights → BFS. "Prerequisites" or "dependencies" → topological sort. "Minimum cost to connect" → MST.
-
Implement from scratch. Don't just read the code. Write it yourself. Debug it. That's how you learn.
-
Practice with time limits. In interviews, you have 20-30 minutes per problem. Get comfortable working under that constraint.
For a structured approach to learn, feel free to take a look at our roadmaps. It covers these algorithms plus topics like Strongly Connected Components, Lowest Common Ancestor, and Network Flow.
Comments (0)