Graphs
Practice & Revision
Graph algorithm pattern recognition decision tree, cheat sheet, and Top 15 must-solve graph interview problems.
1. Introduction
This section serves as your comprehensive reference and practice guide for Graphs. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.
2. Graph Algorithm Decision Tree
Use this flow chart to determine the correct graph algorithm based on your problem:
3. Revision Cheat Sheet
Graph Algorithm Complexities
| Algorithm | Primary Use Case | Time Complexity | Space Complexity |
|---|---|---|---|
| DFS | Connectivity, Cycle Detection, Pathfinding | O(V + E) | O(V) stack |
| BFS | Shortest path (unweighted), flood fill | O(V + E) | O(V) queue |
| Dijkstra | Shortest path (non-negative weights) | O((V+E)log V) | O(V) queue |
| Bellman-Ford | Shortest path with negative edge weights | O(V × E) | O(V) distances |
| Kahn's (BFS) | Topological sort on DAG dependencies | O(V + E) | O(V) indegree |
| DSU (Union-Find) | Dynamic connectivity, partition sets | O(\alpha(N)) | O(N) parent array |
| Kruskal's MST | Minimum Spanning Tree (edge-driven) | O(E log E) | O(V + E) |
| Prim's MST | Minimum Spanning Tree (vertex-driven) | O(E log V) | O(V) heap |
4. Top 15 Must-Solve Graph Problems
5. Problem-Solving Framework
When coding Graph solutions, follow this 3-step checklist:
1. Explicitly Track Visited States:
- Graphs are not Trees. They can contain cycle paths. You must declare a visited set or boolean array visited before traversing to avoid entering infinite loops.
2. Handle Multi-Source Scenarios Correctly:
- In problems like Rotting Oranges, do not run BFS from each source one by one. Instead, queue all initial source nodes at the start of BFS, then expand level-by-level to ensure optimal shortest path coordinates.
3. Optimize Edge Checks:
- Build adjacency lists from flat array lists immediately instead of querying edge arrays repeatedly. Flat lookups take O(1) while array searches take O(E) time.
6. Quiz
Question 1: In 'Accounts Merge', why is DSU (Union-Find) preferred over standard DFS connected component search?
Answer: DSU is extremely clean for merging dynamic components based on shared items (email addresses). As we scan each account, we can rununion on common emails. Reconstructing components at the end is simplified compared to building explicit graph nodes and run recursive DFS search cycles.
Question 2: What occurs if a Directed Graph has a cycle during Kahn's Topological Sort algorithm?
Answer: Nodes involved in the cycle will have their indegrees remain≥ 1 permanently (since they depend on each other). They will never enter the queue. The resulting sorted list will be smaller than the total vertex count, signaling a dependency loop deadlock.
Question 3: In grid traversals (like 'Pacific Atlantic Water Flow'), why do we traverse from the ocean borders inward rather than from each land cell outward?
Answer: Traversing from every cell outward leads to redundant searches and takesO((R × C)²) time. Traversing inward from ocean boundaries marks all reachable cells in a single pass of DFS/BFS, running in optimal O(R × C) time.
Question 4: True or False: Prim's algorithm works on graphs containing negative edge weights.
Answer: True. Prim's algorithm finds the Minimum Spanning Tree correctly on graphs with negative weights as long as there are no negative cycles. However, Dijkstra's algorithm for shortest paths fails on negative edge weights.Question 5: What is the space complexity of BFS on a 2D grid of size R x C?
Answer:O(R × C) space in the worst case, as the queue can hold up to the boundary size of nodes during level expansion, which is proportional to the grid area.