Graph Problems
Now let's apply graph algorithms to classic problems that appear in interviews.
1. Number of Islands (DFS/BFS on grid)
Given a 2D grid of '1's (land) and '0's (water), count islands. Use DFS to mark visited cells.
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') {
dfsIsland(grid, i, j);
count++;
}
}
}
return count;
}
2. Clone Graph
Deep copy a graph using DFS or BFS with a HashMap to track cloned nodes.
3. Course Schedule (Detect cycle in prerequisites)
Given courses and prerequisites, determine if you can finish all courses (topological sort check).
These problems test your ability to adapt graph algorithms to real scenarios.
Two Minute Drill
- Number of Islands: classic DFS/BFS on grid.
- Clone Graph: use map to avoid duplicate clones.
- Course Schedule: cycle detection in directed graph.
- Practice these to solidify graph skills.
Need more clarification?
Drop us an email at career@quipoinfotech.com