Graph representations, traversals, shortest paths, and topological sorting.
Time
BFS/DFS: O(V+E), Dijkstra: O((V+E) log V)
Space
O(V+E)
Problems
4 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Number of Islands | Medium | Amazon Google Microsoft |
| 2 | Clone Graph | Medium | Google Meta Amazon |
| 3 | Course Schedule (Topological Sort) | Medium | Google Amazon Microsoft |
| 4 | Word Ladder | Hard | Google Amazon Meta |
Adjacency list is preferred over matrix for sparse graphs
BFS finds shortest path in unweighted graphs
DFS is used for cycle detection, connected components, topological sort
Union-Find is efficient for connectivity queries and MST
