Top 50 Graph Problems
Graph problems often appear in interviews for senior roles. They test your ability to model relationships and apply traversal algorithms.
Essential Graph Problems:
- Number of Islands (DFS/BFS on grid)
- Clone Graph
- Course Schedule (topological sort)
- Alien Dictionary (topological sort)
- Graph Valid Tree (union-find or DFS)
- Redundant Connection (union-find)
- Minimum Height Trees
- Word Ladder (BFS)
- Pacific Atlantic Water Flow
- Surrounded Regions
- Longest Increasing Path in a Matrix
- Snakes and Ladders (BFS)
- Dijkstra's algorithm (Network Delay Time)
- Bellman-Ford (Cheapest Flights Within K Stops)
- Prim's / Kruskal's (Minimum Cost to Connect All Points)
- Floyd-Warshall
- Bipartite Graph (DFS coloring)
- Evaluate Division (graph + DFS)
- Reconstruct Itinerary (Eulerian path)
- Critical Connections in a Network (Tarjan's algorithm)
Strategies:
- DFS and BFS are the foundation.
- Union-Find for connectivity.
- Topological sort for DAGs.
- Shortest path algorithms for weighted graphs.
Example: Number of Islands (DFS on grid)
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
grid[i][j] = '0';
dfs(grid, i+1, j);
dfs(grid, i-1, j);
dfs(grid, i, j+1);
dfs(grid, i, j-1);
}
Two Minute Drill
- Graph problems require understanding of DFS, BFS, union-find, topological sort.
- Practice grid-based BFS/DFS for island problems.
- Know shortest path algorithms (Dijkstra, Bellman-Ford).
- Model relationships as graphs and apply appropriate traversal.
Need more clarification?
Drop us an email at career@quipoinfotech.com