This unit covers the basic graph traversal algorithms, and several of their applications:
- Depth First Search (DFS)
- Breath First Search (BFS)
- Shortest path with BFS
- Connected components
- Topological sort (zero in-degree and DFS)
- Bipartite check
- Strongly connected components (Kosaraju's algorithm)
- Unit 1: Complexity
- Unit 6: Graph basics
For BFS shortest path exercises, see unit 17
- UVa 11831 - Sticker Collector Robot (just graph traversal)
- UVa 11953 - Battleships (flood fill)
- UVa 10305 - Ordering Tasks (toposort)
- UVa 10004 - Bicoloring (bipartite check)
- UVa 247 - Calling circles (SCC)
- UVa 12442 - Forwarding emails
- UVa 200 - Rare Order
- UVa 11902 - Dominator
- UVa 872 - Ordering
- UVa 11396 - Claw Decomposition
- Kattis - Cantina of Babel
- UVa 705 - Slash Maze
- UVa 11504 - Dominos
- UVa 295 - Fatman
- Kattis - Cleaning pipes (NWERC 2015 C)