Algorithms in C++ Part 5: Graph Algorithms

✍ Scribed by Sedgewick, Robert; Wyk, Christopher J. van

• Publisher: Addison-Wesley Professional
• Year: 2001
• Tongue: English
• Leaves: 520
• Edition: 3rd ed
• Category: Library

✦ Synopsis

Providing exercises to help students learn the properties of algorithms, this text places a greater emphasis on abstract data types, modular programming, object-oriented programming and C++ classes.

✦ Table of Contents

Contents......Page 18
PART FIVE: Graph Algorithms......Page 22
Chapter 17. Graph Properties and Types......Page 24
17.1 Glossary......Page 28
17.2 Graph ADT......Page 37
17.3 Adjacency-Matrix Representation......Page 46
17.4 Adjacency-Lists Representation......Page 52
17.5 Variations, Extensions, and Costs......Page 57
17.6 Graph Generators......Page 67
17.7 Simple, Euler, and Hamilton Paths......Page 77
17.8 Graph-Processing Problems......Page 91
Chapter 18. Graph Search......Page 102
18.1 Exploring a Maze......Page 103
18.2 Depth-First Search......Page 108
18.3 Graph-Search ADT Functions......Page 112
18.4 Properties of DFS Forests......Page 119
18.5 DFS Algorithms......Page 126
18.6 Separability and Biconnectivity......Page 133
18.7 Breadth-First Search......Page 142
18.8 Generalized Graph Search......Page 152
18.9 Analysis of Graph Algorithms......Page 161
Chapter 19. Digraphs and DAGs......Page 170
19.1 Glossary and Rules of the Game......Page 173
19.2 Anatomy of DFS in Digraphs......Page 181
19.3 Reachability and Transitive Closure......Page 190
19.4 Equivalence Relations and Partial Orders......Page 203
19.5 DAGs......Page 207
19.6 Topological Sorting......Page 212
19.7 Reachability in DAGs......Page 222
19.8 Strong Components in Digraphs......Page 226
19.9 Transitive Closure Revisited......Page 237
19.10 Perspective......Page 242
Chapter 20. Minimum Spanning Trees......Page 248
20.1 Representations......Page 251
20.2 Underlying Principles of MST Algorithms......Page 261
20.3 Prim’s Algorithm and Priority-First Search......Page 268
20.4 Kruskal’s Algorithm......Page 279
20.5 Boruvka’s Algorithm......Page 285
20.6 Comparisons and Improvements......Page 288
20.7 Euclidean MST......Page 295
Chapter 21. Shortest Paths......Page 298
21.1 Underlying Principles......Page 306
21.2 Dijkstra’s Algorithm......Page 314
21.3 All-Pairs Shortest Paths......Page 325
21.4 Shortest Paths in Acyclic Networks......Page 334
21.5 Euclidean Networks......Page 343
21.6 Reduction......Page 349
21.7 Negative Weights......Page 366
21.8 Perspective......Page 384
Chapter 22. Network Flow......Page 388
22.1 Flow Networks......Page 394
22.2 Augmenting-Path Maxflow Algorithms......Page 403
22.3 Preflow-Push Maxflow Algorithms......Page 431
22.4 Maxflow Reductions......Page 446
22.5 Mincost Flows......Page 464
22.6 Network Simplex Algorithm......Page 474
22.7 Mincost-Flow Reductions......Page 493
22.8 Perspective......Page 503
References for Part Five......Page 508
C......Page 510
D......Page 511
F......Page 512
L......Page 513
N......Page 514
R......Page 515
S......Page 516
W......Page 517

✦ Subjects

Computer Science;Programming;Science;Nonfiction;Algorithms