Algorithms in C, Part 5: Graph Algorithms (Third Edition)

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). 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 Once again, Robert Sedgewick provides a current and comprehensive introduction to important algorithms. The focus this time is on graph algorithms, which are increasingly critical for a wide range of applications, such as network connectivity, circuit design, scheduling, transaction processing, and resource allocation. In this book, Sedgewick offers the same successful blend of theory and practice with concise implementations that can be tested on real applications, which has made his work popular with programmers for many years. Algorithms in C, Third Edition, Part 5: Graph Algorithms is the second book in Sedgewick's thoroughly revised and rewritten series. The first book, Parts 1-4 , addresses fundamental algorithms, data structures, sorting, and searching. A forthcoming third book will focus on strings, geometry, and a range of advanced algorithms. Each book's expanded coverage features new algorithms and implementations, enhanced descriptions and diagrams, and a wealth of new exercises for polishing skills. A focus on abstract data types makes the programs more broadly useful and relevant for the modern object-oriented programming environment. Coverage The Web site for this book ( ) provides additional source code for programmers along with numerous support materials for educators. A landmark revision, Algorithms in C, Third Edition, Part 5 provides a complete tool set for programmers to implement, debug, and use graph algorithms across a wide range of computer applications. Robert Sedgewick has thoroughly rewritten and substantially expanded his popular work to provide current and comprehensive coverage of important algorithms and data structures. Many new algorithms are presented, and the explanations of each algorithm are much more detailed than in previous editions. A new text design and detailed, innovative figures, with accompanying commentary, greatly enhance the presentation. The third edition retains the successful blend of theory and practice that has made Sedgewick's work an invaluable resource for more than 250,000 programmers! Whether you are a student learning the algorithms for the first time or a professional interested in having up-to-date reference material, you will find a wealth of useful information in this book Defines and explores the implementation and figures of the algorithms required for various applications, offering commentary, descriptions, and exercises for developers, researchers, and students. V. [1], Pts. 1-4. Fundamentals, Data Structures, Sorting, Searching -- V. [2], Pt. 5. Graph Algorithms. Robert Sedgewick. Includes Bibliographical References And Index.