Graph Traversal • Shortest Paths • Dynamic Programming
Compiled & Formatted by Ankush Raj
Graph traversal means visiting all vertices and edges of a graph in a systematic order. Useful for:
Explores graph level by level.
Where used?
Steps:
Explores deep path first, then backtracks.
Where used?
Steps:
| Feature | BFS | DFS |
|---|---|---|
| Data Structure | Queue | Stack/Recursion |
| Exploration | Level-wise | Depth-wise |
| Shortest Path? | ✔ Yes | ❌ No |
| Applications | Unweighted shortest path | Cycle detect, topo sort |
Finds shortest path from one source to every vertex in graphs with non-negative weights.
A lossless compression technique using variable-length prefix codes.
A spanning tree that connects all nodes with minimum total edge weight, no cycles.
| Feature | Prim's | Kruskal's |
|---|---|---|
| Method | Vertex-based | Edge-based |
| Best For | Dense graphs | Sparse graphs |
| Cycle Checking | Not needed | Required |
DP solves problems by breaking them into overlapping subproblems and storing answers to avoid repetition.
Used when:
Big problem → built from small optimal solutions.
Same subproblems repeat many times. DP stores them in table.
F(n) = F(n-1) + F(n-2), stored in table.
Max profit under weight limit. Used in: resource allocation, investments.
For DNA comparison, plagiarism check.
Minimizes multiplications.
Minimum coins or number of ways.
Used in stock prediction, rankings.
Insert/Delete/Replace operations. Used in spell check, NLP.