Graphs problems, grouped by pattern
Graphs show up as grids, dependencies and networks. BFS finds shortest paths in unweighted graphs, DFS explores components, topological sort orders dependencies, and Dijkstra handles weighted edges.
When to reach for it
- A grid where you move between neighbours
- Tasks with prerequisites
- Shortest path, connected components or cycles
Mistakes to watch for
- Marking visited on pop instead of on push in BFS
- Missing disconnected components
- Using BFS on weighted edges
The 75 problems
1BFS / DFS Basics
- BFS - Normal + Level by Level Animated Easy
- DFS - Recursive + Iterative Animated Easy
- Clone Graph Medium
- All Paths From Source to Target Medium
- Maximum Candies You Can Get from Boxes Hard
- Employee Importance Medium
- Web Crawler Medium
- Time Needed to Inform All Employees Medium
- Web Crawler Multithreaded Medium
2Matrix Graphs
- Flood Fill Animated Easy
- Maximum Number of Points From Grid Queries Hard
- Contain Virus Hard
- Number of Distinct Islands Medium
- Max Area of Island Medium
- Number of Closed Islands Medium
3Connected Components
- Number of Provinces Animated Medium
- Number of Islands Animated Medium
- Evaluate Division Medium
- Making A Large Island Hard
- Accounts Merge Medium
- Number of Islands II Hard
- Satisfiability of Equality Equations Medium
- Number of Operations to Make Network Connected Medium
- The Earliest Moment When Everyone Become Friends Medium
- Most Stones Removed with Same Row or Column Medium
- Smallest String With Swaps Medium
4BFS for shortest path
- Shortest Path in Binary Matrix Animated Medium
- Word Ladder Hard
- Bus Routes Hard
- Minimum Knight Moves Medium
- Word Ladder II Hard
- Minimum Number of Flips to Convert Binary Matrix to Zero Matrix Hard
- Sliding Puzzle Hard
- Open the Lock Medium
- Shortest Path in a Grid with Obstacles Elimination Hard
- Snakes and Ladders Medium
- Shortest Path to Get All Keys Hard
- Zuma Game Hard
5DFS - Complement Trick
- Surrounded Regions Animated Medium
6Multi source BFS
- Rotting Oranges Animated Medium
- 01 Matrix Animated Medium
- Pacific Atlantic Water Flow Medium
- Escape the Spreading Fire Hard
- Find the Safest Path in a Grid Medium
- Shortest Bridge Medium
- Walls and Gates Medium
7Cycle Detection
- Undirected Graph Cycle Animated Medium
- Directed Graph Cycle Animated Medium
- Is Graph Bipartite? Animated Medium
- Detect Cycles in 2D Grid Medium
- Possible Bipartition Medium
8Topological Sort
- Topological sort using BFS Animated Medium
- Course Schedule Animated Medium
- Course Schedule II Animated Medium
- Alien Dictionary Animated Hard
- Longest Increasing Path in a Matrix Hard
- Find All Possible Recipes from Given Supplies Medium
- Loud and Rich Medium
- Parallel Courses Medium
- Parallel Courses III Hard
- Minimum Height Trees Medium
- Collect Coins in a Tree Hard
9Dijkstra
- Network Delay Time Animated Medium
- Find the City With the Smallest Number of Neighbors at a Threshold Distance Animated Medium
- Cheapest Flights Within K Stops Medium
- Swim in Rising Water Hard
- Minimum Time to Visit a Cell In a Grid Hard
- Minimum Cost to Reach City With Discounts Medium
10Eulerian Path (Hierholzer)
11Candidate Elimination
- Find the Celebrity Medium