Internship← Competitive Programming learning pathCompetitive Programming · Module 9 of 10
Graphs: BFS, DFS and shortest paths
Model connections and travel them efficiently.
📖 Key ideas
- Store graphs as adjacency lists.
- BFS explores level by level: shortest path in unweighted graphs.
- DFS goes deep: components, cycles, topological sort.
- Dijkstra finds shortest paths with non-negative weights in O((V+E) log V).
- Union-Find (DSU) merges sets and checks connectivity fast.
💡 Real-life example: BFS is ripples spreading in a pond; DFS is exploring one corridor to its end before turning back.
BFSLevel-by-level search
DFSDepth-first search
DijkstraShortest paths with non-negative weights
DSUDisjoint set union for connectivity