finelybook
Algorithms in C,Part 5: Graph Algorithms (3rd Edition) (Pt.5)
by 作者: Robert Sedgewick
ISBN-10 书号: 0201316633
ISBN-13 书号: 9780201316636
Edition 版本: 3
Publisher Finelybook 出版日期: 2001-08-26
Pages: 512
Book Description
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 includes:
A complete overview of graph properties and types
Diagraphs and DAGs
Minimum spanning trees
Shortest paths
Network flows
Diagrams,sample C code,and detailed algorithm descriptions
The Web site for this book (http://www.cs.princeton.edu/~rs/) 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.
Contents
Graph Algorithms
Chapter 17.Graph Properties and Types
17.1Glossary
17.2 Graph ADT
17.3Adjacency-Matrix Representation
17.4 Adjacency-Lists Representation
17.5Variations.Extensions.and Costs
17.6Graph Generators
17.7 Simple.Euler.and Hamilton Paths
17.8Graph-Processing Problems
Chapter 18.Graph Search
18.1Exploring a Maze
18.2Depth-First Search
18.3 Graph-Search ADT Functions
18.4Properties of DFS Forests
18.5DFS Algorithms
18.6Separability and Biconnectivity
18.7Breadth-First Search
18.8Generalized 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.3Reachability and Transitive Closure
19.4Equivalence Relations and Partial Orders
19.5DAGs
19.6 Topological Sorting
19.7 Reachability in DAGs
19.8Strong Components in Digraphs
19.9Transitive Closure Revisited
19.10 Perspective
Chapter 20. Minimum Spanning Trees
20.1Representations
20.2Underlying Principles of MST Algorithms
20.3 Prim's Algorithm and Priority-First Search
20.4Kruskal's Algorithm
20.5Boruvka's Algorithm
20.6Comparisons and Improvements
20.7Euclidean MST
Chapter 21. Shortest Paths
21.1Underlying Principles
21.2 Diikstra's algorithm
21.3All-Pairs Shortest Paths
21.4Shortest Paths in Acyclic Networks
21.5Euclidean Networks
21.6Reduction
21.7Negative Weights
21.8Perspective
Chapter 22. Network Flows
22.1Flow Networks
22.2 Augmenting-Path Maxflow Algorithms
22.3Preflow-Push Maxflow Algorithms
22.4 Maxflow Reductions
22.5Mincost Flows
22.6Network Simplex Algorithm
22.7Mincost-Flow Reductions
22.8Perspective
