Graph Algorithms

Chapter 17．Graph Properties and Types

17.1 Glossary

17.2 Graph ADT

17.3 Adjacency-Matrix Representation

17.4 Adjacency-Lists Representation

17.5 Variations,Extensions,and Costs

17.6 Graph Generators

17.7 Simple,Euler,and Hamilton Paths

17.8 Graph-Processing Problems

Chapter 18．Graph Search

18.1 Exploring a Maze

18.2 Depth-First Search

18.3 Graph-Search ADT Functions

18.4 Properties of DFS Forests

18.5 DFS Algorithms

18.6 Separability and Biconnectivity

18.7 Breadth-First Search

18.8 Generalized Graph Search

18.9 Analysis of Graph Algorithms

Chapter 19．Digraphs and DAGs

19.1 Glossary and Rules of the Game

19.2 Anatomy of DFS in Digraphs

19.3 Reachability and Transitive Closure

19.4 Equivalence Relations and Partial Orders

19.5 DAGs

19.6 Topological Sorting

19.7 Reachability in DAGs

19.8 Strong Components in Digraphs

19.9 Transitive Closure Revisited

19.10 Perspective

Chapter 20．Minimum Spanning Trees

20.1 Representations

20.2 Underlying Principles of MST Algorithms

20.3 Prim's Algorithm and Priority-First Search

20.4 Kruskal's Algorithm

20.5 Boruvka's Algorithm

20.6 Comparisons and Improvements

20.7 Euclidean MST

Chapter 21．Shortest Paths

21.1 Underlying Principles

21.2 Dijkstra's algorithm

21.3 All-Pairs Shortest Paths

21.4 Shortest Paths in Acyclic Networks

21.5 Euclidean Networks

21.6 Reduction

21.7 Negative Weights

21.8 Perspective

Chapter 22．Network Flows

22.1 Flow Networks

22.2 Augmenting-Path Maxflow Algorithms

22.3 Preflow-Push Maxflow Algorithms

22.4 Maxflow Reductions

22.5 Mincost Flows

22.6 Network Simplex Algorithm

22.7 Mincost-Flow Reductions

22.8 Perspective

References for Part Five

Index