Graph problems are a hot topic in technical interviews. They test your algorithmic thinking, problem-solving skills, and ability to model real-world problems. Whether you’re facing FAANG interviews or coding challenges on LeetCode, understanding graph algorithms is a must.
In this guide, we’ll walk through 12 classic graph problems, along with the core concepts, relevant algorithms, and example use cases.
🔁 1. DFS & BFS Traversals
Problem: Traverse a graph using DFS and BFS.
Use Cases: Find connected components, detect cycles, search.
✅ Algorithms:
- DFS (Recursive or Stack-based)
- BFS (Queue-based)
📘 Example:
Perform DFS and BFS starting from a given node in an undirected graph.
🔗 2. Shortest Path Algorithms
Problem: Find the shortest path between nodes.
✅ Algorithms:
- Dijkstra’s Algorithm – For non-negative weights
- Bellman-Ford Algorithm – Handles negative weights
- Floyd-Warshall Algorithm – All-pairs shortest path
📘 Example:
Find the shortest path from a source to all other nodes in a weighted graph.
🧱 3. Topological Sorting
Problem: Linear ordering of vertices in a Directed Acyclic Graph (DAG).
✅ Algorithms:
- DFS-based Topological Sort
- Kahn’s Algorithm (BFS)
📘 Example:
Task scheduling with dependencies: What is the correct order?
🔁 4. Cycle Detection
Problem: Check if a graph contains any cycles.
✅ Algorithms:
- DFS (with parent tracking for undirected graphs)
- Union-Find (Disjoint Set)
- Topological Sort (for directed graphs)
📘 Example:
Detect if a course prerequisite graph has circular dependencies.
🔄 5. Strongly Connected Components (SCC)
Problem: Find all SCCs in a directed graph.
✅ Algorithms:
- Kosaraju’s Algorithm
- Tarjan’s Algorithm
📘 Example:
Break a web of links into independent navigable sections.
🌲 6. Minimum Spanning Tree (MST)
Problem: Connect all vertices with minimum edge weight.
✅ Algorithms:
- Kruskal’s Algorithm (Union-Find)
- Prim’s Algorithm (Min Heap)
📘 Example:
Design a network with minimal wiring cost.
🎨 7. Graph Coloring
Problem: Color vertices so no adjacent vertices share the same color.
📘 Example:
Check if a graph is bipartite (2-colorable).
✅ Techniques:
- BFS/DFS with color tracking
- Backtracking (for n-color problems)
💧 8. Maximum Flow (Flow Networks)
Problem: Calculate max flow from source to sink.
✅ Algorithms:
- Ford-Fulkerson
- Edmonds-Karp (BFS-based improvement)
📘 Example:
Optimize water, traffic, or data flow in a network.
🔀 9. All-Pairs Shortest Path
Problem: Compute shortest paths between all node pairs.
✅ Algorithm:
📘 Example:
Precompute delivery times between all cities.
✈️ 10. Traveling Salesman Problem (TSP)
Problem: Visit every node exactly once, return to start, and minimize cost.
✅ Approaches:
- Dynamic Programming (Exponential)
- Approximation (Genetic Algorithms, Greedy)
📘 Example:
Route planning for a delivery truck.
🧩 11. Connected Components
Problem: Count or extract all connected components in an undirected graph.
✅ Techniques:
📘 Example:
Count the number of isolated social groups.
🛤 12. Longest Path in DAG
Problem: Find the longest path in a DAG.
✅ Algorithm:
- Topological Sort + Dynamic Programming
📘 Example:
Find the critical path in a project management schedule.
Bonus Interview Questions
🏝 Number of Islands
Given a 2D grid (1 = land, 0 = water), count the number of islands.
Type: Connected component counting
Approach: DFS/BFS
🔤 Word Ladder
Transform a word into another by changing one letter at a time using a word list.
Type: Shortest path in unweighted graph
Approach: BFS
📌 Interview Tips for Graph Problems
✅ Know the Algorithms: Understand DFS, BFS, Union-Find, Dijkstra, etc.
✅ Practice on Paper: Get used to dry runs, especially for recursion.
✅ Use Adjacency Lists: Especially for sparse graphs
✅ Analyze Time/Space Complexity: Interviewers love optimization insights
✅ Practice Platforms: LeetCode, HackerRank, Codeforces, CodeSignal
Final Thoughts
Graphs unlock a wide world of real-world modeling and algorithmic thinking. Whether you’re scheduling tasks, optimizing routes, or solving puzzles — graph problems are interview gold.