Algorithms in C, Part 5: Graph Algorithms

✍ Scribed by Sedgewick, Robert

• Publisher: Addison-Wesley Professional
• Year: 2001;2002
• Tongue: English
• Leaves: 501
• Edition: 3. ed
• Category: Library

✦ Synopsis

Graph algorithms are increasingly critical for a wide range of applications, including network connectivity, circuit design, scheduling, transaction processing, and resource allocation. The latest book in Robert Sedgewick's classic series on algorithms focuses entirely on graph algorithms, introducing many new implementations and figures, extensive new commentary, more detailed descriptions, and hundreds of new exercises. For developers, researchers and students alike, this is the definitive guide to graph algorithms. The book contains six chapters covering graph properties and types, graph search, directed graphs, minimal spanning trees, shortest paths, and networks -- each with diagrams, sample code, and detailed descriptions intended to help readers understand the basic properties of as broad a range of fundamental graph algorithms as possible. The basic properties of these algorithms are developed from first principles; discussion of advanced mathematical concepts is brief, general, and descriptive, but proofs are rigorous and many open problems are discussed. Sedgewick focuses on practical applications, giving readers all the information and real (not pseudo-) code they need to confidently implement, debug, and use the algorithms he covers. For all developers, computer science researchers, engineers, and students of algorithms. (Also available: the companion book Algorithms in C: Parts 1-4, Third Edition, ISBN: 0-201-314525).

✦ Table of Contents

Contents......Page 16
Graph Algorithms......Page 20
Chapter 17. Graph Properties and Types......Page 22
17.1 Glossary......Page 26
17.2 Graph ADT......Page 35
17.3 Adjacency-Matrix Representation......Page 40
17.4 Adjacency-Lists Representation......Page 46
17.5 Variations, Extensions, and Costs......Page 50
17.6 Graph Generators......Page 59
17.7 Simple, Euler, and Hamilton Paths......Page 69
17.8 Graph-Processing Problems......Page 83
Chapter 18. Graph Search......Page 94
18.1 Exploring a Maze......Page 95
18.2 Depth-First Search......Page 100
18.3 Graph-Search ADT Functions......Page 105
18.4 Properties of DFS Forests......Page 110
18.5 DFS Algorithms......Page 118
18.6 Separability and Biconnectivity......Page 125
18.7 Breadth-First Search......Page 133
18.8 Generalized Graph Search......Page 143
18.9 Analysis of Graph Algorithms......Page 152
Chapter 19. Digraphs and DAGs......Page 160
19.1 Glossary and Rules of the Game......Page 163
19.2 Anatomy of DFS in Digraphs......Page 171
19.3 Reachability and Transitive Closure......Page 180
19.4 Equivalence Relations and Partial Orders......Page 193
19.5 DAGs......Page 197
19.6 Topological Sorting......Page 202
19.7 Reachability in DAGs......Page 212
19.8 Strong Components in Digraphs......Page 216
19.9 Transitive Closure Revisited......Page 227
19.10 Perspective......Page 232
Chapter 20. Minimum Spanning Trees......Page 238
20.1 Representations......Page 241
20.2 Underlying Principles of MST Algorithms......Page 247
20.3 Prim’s Algorithm and Priority-First Search......Page 254
20.4 Kruskal’s Algorithm......Page 265
20.5 Boruvka’s Algorithm......Page 271
20.6 Comparisons and Improvements......Page 274
20.7 Euclidean MST......Page 280
Chapter 21. Shortest Paths......Page 284
21.1 Underlying Principles......Page 292
21.2 Dijkstra’s algorithm......Page 299
21.3 All-Pairs Shortest Paths......Page 309
21.4 Shortest Paths in Acyclic Networks......Page 319
21.5 Euclidean Networks......Page 327
21.6 Reduction......Page 333
21.7 Negative Weights......Page 350
21.8 Perspective......Page 369
Chapter 22. Network Flows......Page 372
22.1 Flow Networks......Page 378
22.2 Augmenting-Path Maxflow Algorithms......Page 389
22.3 Preflow-Push Maxflow Algorithms......Page 415
22.4 Maxflow Reductions......Page 430
22.5 Mincost Flows......Page 448
22.6 Network Simplex Algorithm......Page 458
22.7 Mincost-Flow Reductions......Page 476
22.8 Perspective......Page 486
References for Part Five......Page 492
C......Page 494
D......Page 495
F......Page 496
L......Page 497
N......Page 498
R......Page 499
S......Page 500
W......Page 501

✦ Subjects

Computer Science;Programming;Algorithms;Science;Computers