Module Review: Graphs
[!NOTE] You have traversed the web, solved the maze, and optimized the grid. Time to consolidate your knowledge.
Key Takeaways
- Modeling: Almost any relationship problem can be modeled as a Graph.
- Traversal:
- BFS (Queue) finds shortest paths in unweighted graphs.
- DFS (Stack/Recursion) explores deep and is key for topological sort.
- Shortest Path:
- Dijkstra (Priority Queue) is standard for weighted graphs.
- Bellman-Ford handles negative weights.
- Connectivity:
- Union-Find is the fastest way to track connected components dynamically.
Complexity Cheat Sheet
| Algorithm | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Shortest Path (Unweighted) |
| DFS | O(V + E) | O(V) | Puzzles, Cycle Detection |
| Dijkstra | O(E log V) | O(V) | Shortest Path (Weighted) |
| Bellman-Ford | O(VE) | O(V) | Negative Weights |
| Prim’s | O(E log V) | O(V) | MST (Dense/General) |
| Kruskal’s | O(E log E) | O(V) | MST (Sparse) |
| Union-Find | O(α(N)) | O(N) | Dynamic Connectivity |
| Topo Sort | O(V + E) | O(V) | Dependency Resolution |
Interactive: Flashcards
Test your knowledge. Click to flip.
Question
What data structure does BFS use?
Click to flip
Answer
A Queue (FIFO).
1 / 7
Next Steps
Now that you understand the connections, it’s time to learn how to solve problems efficiently. Next Chapter: Dynamic Programming