17. Graph Properties and Types.
Variations, Extensions, and Costs.
Simple, Euler, and Hamilton Paths.
18. Graph Search.
Exploring a Maze.
Graph-Search ADT Functions.
Properties of DFS Forests.
Separability and Biconnectivity.
Generalized Graph Search.
Analysis of Graph Algorithms.
19. Digraphs and DAGs.
Glossary and Rules of the Game.
Anatomy of DFS in Digraphs.
Reachability and Transitive Closure.
Equivalence Relations and Partial Orders.
Reachability in DAGs.
Strong Components in Digraphs.
Transitive Closure Revisited.
20. Minimum Spanning Trees.
Underlying Principles of MST Algorithms.
Prim's Algorithm and Priority-First Search.
Comparisons and Improvements.
21. Shortest Paths.
All-Pairs Shortest Paths.
Shortest Paths in Acyclic Networks.
22. Network Flow.
Augmenting-Path Maxflow Algorithms.
Preflow-Push Maxflow Algorithms.
Network Simplex Algorithm.
References for Part Five.