Home > Store

Algorithms in C++ Part 5: Graph Algorithms, 3rd Edition

Register your product to gain access to bonus material or receive a coupon.

Algorithms in C++ Part 5: Graph Algorithms, 3rd Edition

Best Value Purchase

Book + eBook Bundle

  • Your Price: $60.79
  • List Price: $87.98
  • We're temporarily out of stock, but order now and we'll send it to you later.
  • Includes EPUB, MOBI, and PDF
  • About eBook Formats
  • This eBook includes the following formats, accessible from your Account page after purchase:

    ePub EPUB The open industry format known for its reflowable content and usability on supported mobile devices.

    MOBI MOBI The eBook format compatible with the Amazon Kindle and Amazon Kindle applications.

    Adobe Reader PDF The popular standard, used most often with the free Adobe® Reader® software.

    This eBook requires no passwords or activation to read. We customize your eBook by discreetly watermarking it with your name, making it uniquely yours.

More Purchase Options

Book

  • Your Price: $50.99
  • List Price: $59.99
  • We're temporarily out of stock, but order now and we'll send it to you later.

eBook (Watermarked)

  • Your Price: $23.79
  • List Price: $27.99
  • Includes EPUB, MOBI, and PDF
  • About eBook Formats
  • This eBook includes the following formats, accessible from your Account page after purchase:

    ePub EPUB The open industry format known for its reflowable content and usability on supported mobile devices.

    MOBI MOBI The eBook format compatible with the Amazon Kindle and Amazon Kindle applications.

    Adobe Reader PDF The popular standard, used most often with the free Adobe® Reader® software.

    This eBook requires no passwords or activation to read. We customize your eBook by discreetly watermarking it with your name, making it uniquely yours.

About

Features

    Description

    • Copyright 2002
    • Dimensions: 7-3/4" x 9-1/4"
    • Pages: 528
    • Edition: 3rd
    • Book
    • ISBN-10: 0-201-36118-3
    • ISBN-13: 978-0-201-36118-6

    Graph algorithms are critical for a wide range of applications, including network connectivity, circuit design, scheduling, transaction processing, and resource allocation. The latest in Robert Sedgewick's classic series on algorithms, this is the field's definitive guide to graph algorithms for C++. Far more than a "revision," this is a thorough rewriting, five times as long as the previous edition, with a new text design, innovative new figures, more detailed descriptions, and many new exercises -- all designed to dramatically enhance the book's value to developers, students, and researchers alike. 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. (Also available: Algorithms in C++: Parts 1-4, Third Edition, ISBN: 0-201-35088-2).

    Downloads

    Source Code

    Code for Algorithms in C++, Third Edition, Part 5

    Supplements

    Click below for Supplements related to this title:
    Supplements

    Extras

    Web Resources

    Click below for Web Resources related to this title:
    Author's Web Site

    Author's Site

    Click for the Author's Web Site related to this title.

    Sample Content

    Table of Contents



    17. Graph Properties and Types.

    Glossary.

    Graph ADT.

    Adjacency-Matrix Representation.

    Adjacency-Lists Representation.

    Variations, Extensions, and Costs.

    Graph Generators.

    Simple, Euler, and Hamilton Paths.

    Graph-Processing Problems.



    18. Graph Search.

    Exploring a Maze.

    Depth-First Search.

    Graph-Search ADT Functions.

    Properties of DFS Forests.

    DFS Algorithms.

    Separability and Biconnectivity.

    Breadth-First Search.

    Generalized Graph Search.

    Analysis of Graph Algorithms.



    19. Digraphs and DAGs.

    Glossary and Rules of the Game.

    Anatomy of DFS in Digraphs.

    Reachability and Transitive Closure.

    Equivalence Relations and Partial Orders.

    DAGs.

    Topological Sorting.

    Reachability in DAGs.

    Strong Components in Digraphs.

    Transitive Closure Revisited.

    Perspective.



    20. Minimum Spanning Trees.

    Representations.

    Underlying Principles of MST Algorithms.

    Prim's Algorithm and Priority-First Search.

    Kruskal's Algorithm.

    Boruvka's Algorithm.

    Comparisons and Improvements.

    Euclidean MST.



    21. Shortest Paths.

    Underlying Principles.

    Dijkstra's algorithm.

    All-Pairs Shortest Paths.

    Shortest Paths in Acyclic Networks.

    Euclidean Networks.

    Reduction.

    Negative Weights.

    Perspective.



    22. Network Flow.

    Flow Networks.

    Augmenting-Path Maxflow Algorithms.

    Preflow-Push Maxflow Algorithms.

    Maxflow Reductions.

    Mincost Flows.

    Network Simplex Algorithm.

    Mincost-Flow Reductions.

    Perspective.



    References for Part Five.


    Index. 0201361183T12172001

    Preface

    Graphs and graph algorithms are pervasive in modern computing applications. This book describes the most important known methods for solving the graph-processing problems that arise in practice. Its primary aim is to make these methods and the basic principles behind them accessible to the growing number of people in need of knowing them. The material is developed from first principles, starting with basic information and working through classical methods up through modern techniques that are still under development. Carefully chosen examples, detailed figures, and complete implementations supplement thorough descriptions of algorithms and applications.

    Algorithms

    This book is the second of three volumes that are intended to survey the most important computer algorithms in use today. The first volume (Parts 1-4) covers fundamental concepts (Part 1), data structures (Part 2), sorting algorithms (Part 3), and searching algorithms (Part 4); this volume (Part 5) covers graphs and graph algorithms; and the (yet to be published) third volume (Parts 6-8) covers strings (Part 6), computational geometry (Part 7), and advanced algorithms and applications (Part 8).

    The books are useful as texts early in the computer science curriculum, after students have acquired basic programming skills and familiarity with computer systems, but before they have taken specialized courses in advanced areas of computer science or computer applications. The books also are useful for self-study or as a reference for people engaged in the development of computer systems or applications programs because they contain implementations of useful algorithms and detailed information on these algorithms' performance characteristics. The broad perspective taken makes the series an appropriate introduction to the field.

    Together the three volumes comprise the Third Edition of a book that has been widely used by students and programmers around the world for many years. I have completely rewritten the text for this edition, and I have added thousands of new exercises, hundreds of new figures, dozens of new programs, and detailed commentary on all the figures and programs. This new material provides both coverage of new topics and fuller explanations of many of the classic algorithms. A new emphasis on abstract data types throughout the books makes the programs more broadly useful and relevant in modern object-oriented programming environments. People who have read previous editions will find a wealth of new information throughout; all readers will find a wealth of pedagogical material that provides effective access to essential concepts.

    These books are not just for programmers and computer science students. Everyone who uses a computer wants it to run faster or to solve larger problems. The algorithms that we consider represent a body of knowledge developed during the last 50 years that is the basis for the efficient use of the computer for a broad variety of applications. From N-body simulation problems in physics to genetic-sequencing problems in molecular biology, the basic methods described here have become essential in scientific research; and from database systems to Internet search engines, they have become essential parts of modern software systems. As the scope of computer applications becomes more widespread, so grows the impact of basic algorithms, particularly the fundamental graph algorithms covered in this volume. The goal of this book is to serve as a resource so that students and professionals can know and make intelligent use of graph algorithms as the need arises in whatever computer application they might undertake.

    Scope

    This book, Algorithms in C++, Third Edition, Part 5: Graph Algorithms, contains six chapters that cover graph properties and types, graph search, directed graphs, minimal spanning trees, shortest paths, and networks. The descriptions here are intended to give readers an understanding of the basic properties of as broad a range of fundamental graph algorithms as possible.

    You will most appreciate the material here if you have had a course covering basic principles of algorithm design and analysis and programming experience in a high-level language such as C++, Java, or C. Algorithms in C++, Third Edition, Parts 1-4 is certainly adequate preparation. This volume assumes basic knowledge about arrays, linked lists, and ADT design, and makes use of priority-queue, symbol table, and union-find ADTs--all of which are described in detail in Parts 1-4 (and in many other introductory texts on algorithms and data structures).

    Basic properties of graphs and graph algorithms are developed from first principles, but full understanding often can lead to deep and difficult mathematics. Although the discussion of advanced mathematical concepts is brief, general, and descriptive, you certainly need a higher level of mathematical maturity to appreciate graph algorithms than you do for the topics in Parts 1-4. Still, readers at various levels of mathematical maturity will be able to profit from this book. The topic dictates this approach: some elementary graph algorithms that should be understood and used by everyone differ only slightly from some advanced algorithms that are not understood by anyone. The primary intent here is to place important algorithms in context with other methods throughout the book, not to teach all of the mathematical material. But the rigorous treatment demanded by good mathematics often leads us to good programs, so I have tried to provide a balance between the formal treatment favored by theoreticians and the coverage needed by practitioners, without sacrificing rigor.

    Use in the Curriculum

    There is a great deal of flexibility in how the material here can be taught, depending on the taste of the instructor and the preparation of the students. The algorithms described have found widespread use for years, and represent an essential body of knowledge for both the practicing programmer and the computer science student. There is sufficient coverage of basic material for the book to be used in a course on data structures and algorithms, and there is sufficient detail and coverage of advanced material for the book to be used for a course on graph algorithms. Some instructors may wish to emphasize implementations and practical concerns; others may wish to emphasize analysis and theoretical concepts.

    For a more comprehensive course, this book is also available in a special bundle with Parts 1-4; thereby instructors can cover fundamentals, data structures, sorting, searching, and graph algorithms in one consistent style. A set of slide masters for use in lectures, sample programming assignments, interactive exercises for students, and other course materials may be found by accessing the book's home page.

    The exercises--nearly all of which are new to this edition--fall into several types. Some are intended to test understanding of material in the text, and simply ask readers to work through an example or to apply concepts described in the text. Others involve implementing and putting together the algorithms, or running empirical studies to compare variants of the algorithms and to learn their properties. Still other exercises are a repository for important information at a level of detail that is not appropriate for the text. Reading and thinking about the exercises will pay dividends for every reader.

    Algorithms of Practical Use

    Anyone wanting to use a computer more effectively can use this book for reference or for self-study. People with programming experience can find information on specific topics throughout the book. To a large extent, you can read the individual chapters in the book independently of the others, although, in some cases, algorithms in one chapter make use of methods from a previous chapter.

    The orientation of the book is to study algorithms likely to be of practical use. The book provides information about the tools of the trade to the point that readers can confidently implement, debug, and put to work algorithms to solve a problem or to provide functionality in an application. Full implementations of the methods discussed are included, as are descriptions of the operations of these programs on a consistent set of examples. Because we work with real code, rather than write pseudo-code, the programs can be put to practical use quickly. Program listings are available from the book's home page.

    Indeed, one practical application of the algorithms has been to produce the hundreds of figures throughout the book. Many algorithms are brought to light on an intuitive level through the visual dimension provided by these figures.

    Characteristics of the algorithms and of the situations in which they might be useful are discussed in detail. Connections to the analysis of algorithms and theoretical computer science are developed in context. When appropriate, empirical and analytic results are presented to illustrate why certain algorithms are preferred. When interesting, the relationship of the practical algorithms being discussed to purely theoretical results is described. Specific information on performance characteristics of algorithms and implementations is synthesized, encapsulated, and discussed throughout the book.

    Programming Language

    The programming language used for all of the implementations is C++. The programs use a wide range of standard C++ idioms, and the text includes concise descriptions of each construct.

    Chris Van Wyk and I developed a style of C++ programming based on classes, templates, and overloaded operators that we feel is an effective way to present the algorithms and data structures as real programs. We have striven for elegant, compact, efficient, and portable implementations. The style is consistent whenever possible, so that programs that are similar look similar.

    A goal of this book is to present the algorithms in as simple and direct a form as possible. For many of the algorithms, the similarities remain regardless of which language is used: Dijkstra's algorithm (to pick one prominent example) is Dijkstra's algorithm, whether expressed in Algol-60, Basic, Fortran, Smalltalk, Ada, Pascal, C, C++, Modula-3, PostScript, Java, or any of the countless other programming languages and environments in which it has proved to be an effective graph-processing method. On the one hand, our code is informed by experience with implementing algorithms in these and numerous other languages (a C version of this book is also available, and a Java version will appear soon); on the other hand, some of the properties of some of these languages are informed by their designers' experience with some of the algorithms and data structures that we consider in this book. In the end, we feel that the code presented in the book both precisely defines the algorithms and is useful in practice.
    Robert Sedgewick

    C++ Consultant's Preface

    Bob Sedgewick and I wrote many versions of most of these programs in our quest to implement graph algorithms in clear and natural programs. Because there are so many kinds of graphs and so many different questions to ask about them, we agreed early on not to pursue a single class scheme that would work across the whole book. Remarkably, we ended up using only two schemes: a simple one in Chapters 17 through 19, where the edges of a graph are either present or absent; and an approach similar to STL containers in Chapters 20 through 22, where more information is associated with edges.

    C++ classes offer many advantages for presenting graph algorithms. We use classes to collect useful generic functions on graphs (like input/output). In Chapter 18, we use classes to factor out the operations common to several different graph-search methods. Throughout the book, we use an iterator class on the edges emanating from a vertex so that the programs work no matter how the graph is stored. Most important, we package graph algorithms in classes whose constructor processes the graph and whose member functions give us access to the answers discovered. This organization allows graph algorithms to readily use other graph algorithms as subroutines--see, for example, Program 19.13 (transitive closure via strong components), Program 20.8 (Kruskal's algorithm for minimum spanning tree), Program 21.4 (all shortest paths via Dijkstra's algorithm), Program 21.6 (longest path in a directed acyclic graph). This trend culminates in Chapter 22, where most of the programs are built at a higher level of abstraction, using classes that are defined earlier in the book.

    For consistency with Algorithms in C++, Third Edition, Parts 1-4, our programs rely on the stack and queue classes defined there, and we write explicit pointer operations on singly-linked lists in two low-level implementations. We have adopted two stylistic changes from Parts 1-4: Constructors use initialization rather than assignment and we use STL vectors instead of arrays. Here is a summary of the STL vector functions we use in our programs:

    • The default constructor creates an empty vector.
    • The constructor vec(n) creates a vector of n elements.
    • The constructor vec(n, x) creates a vector of n elements each initialized to the value x.
    • Member function vec.assign(n, x) makes vec a vector of n elements each initialized to the value x.
    • Member function vec.resize(n) grows or shrinks vec to have capacity n.
    • Member function vec.resize(n, x) grows or shrinks vec to have capacity n and initializes any new elements to the value x.

    The STL also defines the assignment operator, copy constructor, and destructor needed to make vectors first-class objects.

    Before I started working on these programs, I had read informal descriptions and pseudocode for many of the algorithms, but had only implemented a few of them. I have found it very instructive to work out the details needed to turn algorithms into working programs, and fun to watch them in action. I hope that reading and running the programs in this book will also help you to understand the algorithms better.
    Christopher Van Wyk



    0201361183P12182001

    Index

    Abstract transitive closure, 174-175, 216-220
    Active vertex, 411
    Acyclic graph. See Digraph; Directed acyclic graph (DAG)
    Acyclic network, 313-321, 334-335
       maxflow, 427-429
    Adjacency-lists representation, 31-35
       DFS, 90, 95, 102
       digraphs, 36-37, 153, 155, 179
       edge connectivity, 115-116
       find/remove edge, 40
       flow networks, 379
       performance, 33-35, 37-40, 145-146
       removing vertices, 41
       standard adjacency-lists DFS, 97, 161
       transitive closure, 174
       weighted graphs/networks, 37, 230, 235-238, 278
    Adjacency-matrix representation, 25-30
       DFS, 90, 95, 101
       digraphs, 36-37, 153, 154-155, 169-172, 176, 179
       flow networks, 379
       linear-time algorithm, 59
       performance, 29-30, 37-40, 144-146
       removing vertices, 41
       standard adjacency-matrix DFS, 97, 161
       weighted graphs/networks, 37, 230, 233-238, 278
    Adjacent vertices, 9
    ADT, graph. See Graph ADT
    Airline route, 283
    All-pairs shortest path, 281, 304-311
       acyclic networks, 318-320
       BFS, 127-129
       negative weights, 356-360
       path relaxation, 288-290
       and transitive closure, 175, 328-329
    Arbitrage, 348-349
    Arbitrary weight, 229
    Arc, 8, 14
    Articulation point, 117-118
    Assignment problem, 74, 476-477
    A* algorithm, 325
    Augmenting-path method, 382-407
       cycle canceling, 451
       longest augmenting path, 396
       maximum-capacity, 394, 399-401, 405-406
       network simplex algorithm, 460-461
       performance, 393, 395-406, 434-436
       and preflow-push, 411
       random flow networks, 402-404
       randomized, 402
       shortest augmenting path, 393-394, 398-399, 405-407
       stack-based, 400

    Back edge, 99, 113-115, 161-165, 202-203
    Back link, 99-100
    Bellman-Ford algorithm, 350-356, 358-360, 447
    BFS tree, 124-129
    Binary DAG, 188-190
    Binary decision diagram (BDD), 189
    Binary tree, 188-190
    Bioconnectivity, 117-119
    Bipartite graph, 13, 110-111
    Bipartite matching, 73-74, 433-436, 476, 482
    Boolean matrix multiplication, 169-172, 176-177
    Boruvka's algorithm, 244, 263-267
    Breadth-first search (BFS), 81-82, 121-130
       and DFS, 127-134
       forest, 125
       fringe size, 137-138
       PFS, 253, 302
    Bridge, 113-117
    Bridges of Konigsberg problem, 62-64

    Call, program, 5
    Capacity, flow, 372, 375
       st-cut, 385
       vertex-capacity constraints, 426
    change priority operation, 253
    Circuit, 4
    Circulation, flow network, 377-378, 429
    Class
       augmenting-paths, 391
       cycle canceling, 449
       DFS, 96
       flow networks, 379, 432
       network simplex algorithm, 466-467
       weighted graphs, 233-236
       see also Graph ADT
    Clique, 12, 75
    Colorability problem, 75
       two-coloring, 110-111
    Communications network, 367-369
    Complement, 12
    Complete graph, 12
    Computer science, 365
    Connection, 3
    Connectivity, 11-12
       bioconnectivity, 117-119
       digraphs, 158
       edge, 438-439
       equivalence relations, 184
       general connectivity, 74, 119
       k-connected graph, 119
       maxflow, 437-438
       random, 141-144
       simple connectivity, 72, 106-109
       st-connectivity, 119
       strong connectivity, 72, 156-158, 205
       vertex connectivity, 119, 438
    Construct operation, 262
    Constraint, 186
    Cost, 227, 372, 443
       convex/nonlinear, 483
       edge, 474
       flow, 443
       negative, 446-447
       reduced, 454-457
       see also Performance; Weighted graph
    Critical edge, 398-399
    Cross edge, 161-162, 202, 204
    Crossing edge, 241, 385
    Cut, 241
       mincut, 386-387
       property, 240-241, 245
       set, 385
       st-cut, 0-427-428, 385-387
       vertex, 117-118
    Cut problem, 369-370, 385-386
    Cycle, 10-11
       DFS, 105-106
       directed, 14, 155, 162-165
       even, 74, 224
       flow networks, 377-378, 427
       MSTs, 240-244
       negative, 279-280, 348-350, 446-454
       odd, 110
       property, 242-243
    Cycle-canceling algorithm, 372, 447-452
       see also Network simplex algorithm
    Cyclic path, 10, 156, 477-478

    DAG. See Directed acyclic graph (DAG)
    de Bruijn graph, 53
    Decrease key operation, 255, 268-269, 297
    Degrees-of-separation graph, 53
    Delauney triangulation, 274
    Dense graph, 13, 29-30
    Depth-first search (DFS), 81-82, 87-91
       and BFS, 127-134
       classes, 96
       cycle detection, 105-106
       digraphs, 160-168
       fringe size, 137-138
       PFS, 253
       running time, 95-96
       simple connectivity, 106-109
       simple path, 57-59, 106
       spanning forest, 93, 110
       standard adjacency representations, 97, 161
       strong components algorithms, 207-214
       topological sorting, 193-195, 201-204
       transitive closure, 177-179
       tree links, 99-100
       and Tremaux exploration, 87-90
       two-colorability, 110-111
       two-way Euler tour, 66, 109
       and union-find, 108-109
       vertex search, 109-110
       see also DFS tree
    Destination vertex, 14
    DFS forest, 98-103, 124-125
       DAGs, 194
       digraphs, 161-162, 164
       spanning forest, 110
    DFS tree, 90, 98-103
       bridges, 113-117
       diagraphs, 161-162
    d-heap, 269, 271-272
    Diameter, network, 304
    Difference constraints, 332-336, 338, 347
    Digraph, 14-15, 149-224
       adjacency-lists representation, 36-37, 153, 155, 179
       adjacency-matrix representation, 36-37, 153, 154-155, 169-172, 176, 179
       connectivity, 158, 438
       decomposing, 166
       defined, 152
       DFS in, 160-168
       directed cycle detection, 162-166, 187
       directed path, 152, 155
       edge direction, 149-150
       even cycles, 74
       grid, 152
       isomorphism, 150
       map, 154
       random, 220
       and relations, 182-183
       reverse, 154-155
       running time, 221-222
       single-source reachability, 166-167
       strong components, 157-158, 205-214
       strongly connected, 72, 156-158, 205
       transitive closure, 169-180, 216-220
       and undirected graphs, 153, 155-162, 165-167, 179-180
       uniconnected, 224
       weighted, 277-278
    Dijkstra's algorithm, 256, 293-302
       acyclic networks, 320
       all-pairs shortest paths, 305-307
       Euclidean networks, 323-326
       negative weights, 349, 354-360
       and Prim's algorithm, 294-296
    Directed acyclic graph (DAG), 14, 150, 186-204
       binary, 188-190
       defined, 155
       detection, 162-165, 187
       dominators, 223
       kernel, 157, 216-220
       longest path, 199
       partial orders, 184-185
       scheduling problem, 186-187
       sink/source, 195-199
       strong components, 157
       topological sorting, 187, 191-199
       transitive closure, 201-204
       weighted, 313-321
    Directed cycle, 14, 155, 162-165, 187
    Directed graph. See Digraph; Directed acyclic graph (DAG)
    Directed path, 72, 152, 155, 224
    Disjoint paths, 11, 117
    Distances matrix, 289, 306, 360
    Distribution network, 444-445
    Distribution problem, 368, 430, 444-445, 475
    Dominator, 223
    Down link, 99-100, 161-162, 202-204
    Dummy edge, 447-451, 454-455, 472
    Dummy vertex, 376-377
    Dynamic algorithm, 21-22, 50
    Dynamic reachability, 223

    Edge, 7-10
       back, 99, 113-115, 161-165, 202-203
       backward/forward, 383-384
       class, 379
       connectivity, 438-439
       costs, 474
       critical, 398-399
       cross, 161-162, 202, 204
       crossing, 241, 385
       directed, 14
       disjoint, 11, 117, 437
       down, 99-100, 161-162, 202-204
       dummy, 447-451, 454-455, 472
       eligible, 412, 455-457, 462-468
       flows, 375
       incident, 9
       marking vertices, 93
       parallel, 8, 18, 27, 34, 47, 237, 278
       pointers, 232, 235-237, 277-278, 432
       random, 47
       relaxation, 286-287, 292, 323
       separation, 112
       tree, 99, 113-115, 161-162, 202
       uncapacitated, 380
       vector-of-edges, 24, 37
    Edge data type, 17, 37, 231-232, 379, 390
    Edge-based preflow-push algorithm, 413-414
    Edge-connected graph, 113, 117, 438-439
    Edge-separable graph, 112
    Edmonds, J., 393
    Eligible edge, 412, 455-457, 462-468
    Enumeration, graph, 150-151
    Equal weights, 228-229
    Equivalence class, 183
    Equivalence relation, 183
    Equivalent problems, 328
    Erdos, P., 144
    Euclidean graph, 10
       flow networks, 402-404
       MSTs, 274-276
       neighbor graphs, 49
       networks, 322-326
    Euclidean heuristic, 324-326
    Euler path, 62-68
       directed, 224
       mail carrier, 477-478
       two-way Euler tour, 109
    Even cycle, 74, 224
    Excess, vertex, 411
    Existence problem, 75-76

    Fat interface, 39
    Feasible flow, 410, 430-432, 444
    Feasible spanning tree, 453-455
    Feedback vertex set, 224
    Fibonacci computation, 188, 268
    FIFO queue, 123-125, 132-138
       PFS, 302
       preflow-push, 416-420
       topological sort, 197-199
    Find edge operation, 40-41
    Flow cost, 443
    Flow network, 15, 367-486
       augmenting-flow method, 382-407
       backward/forward edges, 383-384
       capacities, 372, 375, 385, 426
       circulation, 377-378, 429
       cut problems, 369-370, 385-386
       defined, 375
       distribution problems, 368, 430, 444-445, 475
       equilibrium, 376-377
       flows, 372, 375
       inflow/outflow, 375-377
       matching problems, 369, 433-436, 476, 482
       maxflow-mincut theorem, 385-387
       model, 373-374
       network simplex algorithm, 372, 453-470, 479
       preflow-push method, 410-423
       random, 402-404
       reductions, 367, 406, 425-440
       representations, 379
       residual, 388-391, 412, 417, 446, 453
       st-network, 375-377, 429-430
       value, 375-377
       see also Maxflow problem; Mincost flow problem; Network
    Floyd's algorithm, 176, 290, 304, 307-311
       negative weights, 349-351, 354
    Ford, L. R., 382
    Ford-Fulkerson method. See Augmenting-path method
    Forest, 12
       BFS, 125
       Boruvka's algorithm, 264
       DFS, 98-103, 109, 124-125, 161-162, 164, 194
       Kruskal's algorithm, 258
       spanning, 109
       see also DFS tree; Tree
    Four-color theorem, 76
    Fringe, 131-138, 296
       Prim's algorithm, 251-256
       priority queue, 393
    Fulkerson, D. R., 382
    Function call graph, 50-52

    Gabow's algorithm, 206, 211-214
    General connectivity, 74, 119
    Generalized queue, 416, 418
    Geometric algorithm, 275-276
    Goldberg, A., 410
    Graph, 3-73
       applications, 4-5
       bipartite, 13, 110-111
       complete, 12
       connected, 11-12
       de Bruijn, 53
       defined, 7
       degrees-of-separation, 53
       dense/sparse, 13, 29-30
       directed/undirected, 14-15
       edge-connected/edge-separable, 112-113, 117
       Euclidean, 10
       function call, 50-52
       interval, 53
       isomorphic, 10, 29
       multigraph, 8
       neighbor, 49
       planar, 9, 73
       random, 47-48
       simple, 8
       static, 21-22
       subgraph, 9
       transaction, 49-50
       see also Digraph; Directed acyclic graph (DAG); Undirected graph; Weighted graph
    Graph ADT, 16-24, 39
       adjacency-lists representation, 31-35
       adjacency-matrix representation, 25-30
       all-pairs shortest paths, 304-305
       connectivity interface, 21-22
       constructor, 18
       equivalence relations, 184
       graph-search functions, 91-97
       iterator, 18-20
       show function, 20
       symbol table, 50
       vertex degrees, 38
       weighted graphs, 230-239
       see also Class
    Graph search, 81-147
       ADT functions, 91-97
       algorithm analysis, 140-146
       bioconnectivity, 117-119
       generalized, 131-138
       Hamilton tour, 60
       maze exploration, 82-86
       priority-first search, 251-256, 296-302, 323, 392-393
       randomized, 136-138
       separability, 112-117
       simple path, 57-59, 61, 106
       see also Breadth-first search (BFS); Depth-first search (DFS)
    Graph-processing problem, 70-79
       client, 19, 23
       degree of difficulty, 71, 77-79
       existence, 75-76
       intractable, 75
       NP-hard, 75, 77, 339-340
       tractable, 72
    Grid digraph, 152

    Hamilton path, 59-62, 224, 339-340
    Height function, 412-415
    Highest-vertex preflow-push, 420
    Hypertext, 4

    Immediate dominator, 223
    Incident edge, 9
    Indegree, 14, 153-154, 197
    Independent set problem, 75
    Indexing function, 51
    Induced subgraph, 9
    Infeasible problem, 336
    Inflow, 375-377
    Inheritance, 39
    Initial height function, 413
    Integer weights, 379-380
    Interface, graph ADT, 16-24, 39
    Intersection, 82
    Interval graph, 53
    Intractable problem, 75, 342
    Irreflexive relation, 183
    Isomorphic graphs, 10, 29, 77, 150
    Item, 3

    Jarnik's algorithm, 256
    Job placement, 369, 476
    Job scheduling, 4, 150, 186-187
       negative cycles, 348-350
       shortest paths, 332-338, 344
       see also Topological sorting
    Johnson, D., 268
    Johnson's algorithm, 360
    Karp, R., 206, 393
    k-connected graph, 119
    Kernel DAG, 157, 216-220
    k-neighbor graph, 49
    Konigsberg, bridges of, 62-64
    Kosaraju's algorithm, 206-208
    Kruskal's algorithm, 243-244, 258-263, 268
    Kuratowski's theorem, 73

    Least common ancestor (LCA), 459-460
    Length, path, 11
    Library programming, 336, 485
    LIFO stack, 132-134, 138
    Linear programming (LP), 333, 342-343, 365
       maxflow, 439-440
       mincost flow, 425, 479
       multicommodity flow, 483
       network flow algorithms, 371-372
    Linear quantity, 59
    Link, 4, 8
       back, 99
       DFS tree, 99-100
       down, 99-100, 161-162, 202-204
       parent, 99-100, 165
    Locality property, 48
    Longest paths, 75, 199, 315-320
       augmenting paths, 396
       difference constraints, 334-335
       and shortest path, 329-330

    Mail carrier problem, 74, 224, 477-478
    Map, 4, 154, 326
    Matching, 5, 73
       bipartite, 74, 433-436, 476
       maximum, 482
       maximum-cardinality, 433, 482
       minimum-distance point matching, 369
    Mathematical programming, 343
    Maxflow problem, 372, 375-378, 382-440
       acyclic networks, 427-429
       augmenting-path method, 382-407
       bipartite matching, 433-436
       capacity constraints, 426
       connectivity, 437-438
       feasible flow, 430-432
       general networks, 425-426
       linear programming, 439-440
       and mincost flow problem, 425, 472-473
       mincost maxflow, 443-447
       preflow-push method, 410-423
       reductions, 370, 406, 425-440
       running time, 434-436
       spanning tree, 454-455
       standard, 425-426
       undirected networks, 429-430
    Maxflow-mincut theorem, 385-387, 437
    Maximal connected subgraph, 11-12
    Maximum-capacity augmenting path, 394, 399-401, 405-406
    Maximum-cardinality matching, 433, 482
    Maze, 82-86
    Menger's theorem, 119, 437
    Merchandise distribution, 368, 430, 444-445, 475
    Mincost flow problem, 372, 443-479
       assignment problem, 476-477
       cycle-canceling algorithm, 372, 447-452
       edge costs, 474
       eligible edges, 455-457
       feasible flow, 444-445, 472-473
       flow cost, 443
       LP formulation, 425, 479
       mail carrier, 477-478
       and maxflow problem, 425, 472-473
       mincost maxflow, 443-447
       reductions, 472-479
       running time, 451
       single-source shortest paths, 472-473
       transportation, 475-476
       see also Network simplex algorithm
    Mincut, 386-387
    Minimum spanning tree (MST), 72, 227-276
       Boruvka's algorithm, 244, 263-267
       cut and cycle properties, 240-244
       defined, 228
       equal weights, 228-229
       Euclidean, 274-276
       Kruskal's algorithm, 243-244, 258-263, 268
       performance, 268-273, 269
       Prim's algorithm, 243, 247-256, 263, 269
       representations, 237-239
       weighted-graph ADTs, 230-239
    Minimum-distance point matching, 369
    Modular arithmetic, 183-184
    Multicommodity flow, 482-483
    Multigraph, 8
    Multisource paths, 314-318

    Negative cost, 446-447
    Negative cycle, 279-280, 348-350, 446-454
    Negative weight, 345-365
       arbitrage, 348-349
       Bellman-Ford algorithm, 350-356, 358
       Dijkstra's algorithm, 349, 354-360
       Floyd's algorithm, 349-351, 354
    Neighbor graph, 49, 144
    Network, 5, 15, 277-284
       acyclic, 313-321, 334-335, 427-429
       adjacency representations, 37
       communications, 368-369
       distribution, 444-445
       reliability, 370
       residual, 388-391, 412, 417, 446, 453
       reweighting, 324, 357-360
       st-network, 375-378, 429-430
       telephone, 370
       undirected, 429-430
       weighted diameter, 304
       see also Flow network; Shortest path
    Network simplex algorithm, 372, 453-470
       assignment problem, 476-477
       eligible edges, 455-457, 462-468
       feasible spanning tree, 453-455
       implementations, 466-469
       initialization, 464
       parent-link representation, 458-464
       performance, 466-470
       shortest paths, 472-473
       simplex method, 479
       vertex potentials, 454-456, 468
       see also Mincost flow problem
    Node, 8
    Nonlinear cost, 483
    NP-hard problem, 75, 77, 339-340

    Online algorithm, 22
    Operations research (OR), 343, 365
    Optimization, 76
    Ordered pair, 14, 182-183
    Outdegree, 14, 153-154
    Outflow, 375-378

    Parallel edges, 8, 18, 27
       adjacency-lists representation, 34
       networks, 278
       random graphs, 47
       weighted graphs, 237
    Parent-link representation
       BFS tree, 127
       cycle detection, 165
       DFS tree, 99-100
       network simplex algorithm, 458-464
    Partial order, 184-185
    Passage, 82
    Path, 10-11, 56-58
       cyclic, 10, 156, 477-478
       directed, 72, 152, 155, 224
       disjoint, 11, 117
       Euler, 62-64, 109
       Hamilton, 59-62, 224, 339-340
       mail carrier, 477-478
       relaxation, 286, 288-290, 292
       simple, 57-59, 61, 106, 279
       weight, 277
       see also Longest path; Shortest path
    Paths matrix, 289-290, 306, 360
    Performance, 6, 77-79
       abstraction, 42-43
       adjacency-lists representation, 33-35, 37-40, 145-146
       adjacency-matrix representation, 29-30, 37-40, 144-146
       augmenting-path method, 393, 395-406, 434-436
       cycle canceling, 452
       dense/sparse graphs, 13
       DFS forests, 103
       Dijkstra's algorithm, 297-300, 324-326
       equivalent problems, 330-331
       Kruskal's algorithm, 260-262
       MST algorithms, 268-273
       network simplex algorithm, 466-470
       path search, 61-62, 64-65
       PFS, 255-256, 297-300
       preflow-push, 419-423
       preprocessing time, 106-108, 127, 216-217, 221-222
       random graphs, 54
       shortest-paths algorithms, 363-365
       static graphs, 42
       transitive closure, 179-180, 221-222
       union-find algorithm, 145
       vector-of-edges, 37-38
       worst-case, 43-44
       see also Running time
    PERT chart, 150, 345
    Planar graph, 9, 73
    Planarity problem, 73
    Pointer, edge, 232, 235-237, 277-278, 432
    Polynomial-time reduction, 439
    Postorder numbering, 101, 162, 193
    Potential function, 416-419, 454-456, 468
    Precedence constraint, 186, 332
    Preflow, 410-411
    Preflow-push method, 410-423
       edge-based, 413-414
       highest-vertex, 420
       performance, 419-423
       vertex-based, 416
    Preorder numbering, 98-99, 101, 162
    Preprocessing
       DFS, 106-108
       shortest paths, 127, 304-305
       transitive closure, 216-217, 221-222
    Prim's algorithm, 243, 247-256, 263
       and Dijkstra's algorithm, 294-296
       running time, 269
    Priority queue, 136, 268-269
       augmenting-path method, 392-393
       Dijkstra's algorithm, 296-302
       Kruskal's algorithm, 261-263
       multiway heap implementation, 272
    Priority-first search (PFS), 323
       augmenting-path method, 392-393
       Prim's algorithm, 251-256
    Program structure, 5
    Pushdown stack, 123

    Quicksort, 260, 262, 268

    Radar tracking system, 369
    Radix sort, 260, 268
    Random flow network, 402-404
    Random graph, 47-48, 141-144
    Randomized queue, 137, 402
    Reachability, 152, 158, 166-167
       DAGs, 201-204
       digraphs, 205
       dynamic, 223
       see also Transitive closure
    Reduced cost, 454-457
    Reduction, 177, 283, 484
       difference constraints, 333-336, 338
       equivalent problems, 328
       flow networks, 367
       implications, 341
       job scheduling, 332-338
       linear programming, 333, 342-343
       maxflow, 370, 406, 425-440
       mincost flow, 472-479
       polynomial-time, 439
       shortest paths, 328-343
       transitive, 223
       upper/lower bounds, 342
    Reflexive relation, 183
    Relation, 182-183
    Relaxation, 285-292, 323
    Remove edge operation, 34, 40-41
    Remove the minimum operation, 251, 268-271
    Renyi, A., 144
    Residual network, 388-391, 453
       mincost flow, 446
       preflow-push, 412, 417
    Reverse topological sorting, 193-195
    Reweighting, 324, 357-360
    Road map, 282-283
    Running time, 141
       augmenting-path method, 393, 405
       Bellman-Ford algorithm, 354-356
       Boruvka's algorithm, 265
       DFS, 95-96
       digraphs, 221-222
       Dijkstra's algorithm, 296, 299, 311
       Floyd's algorithm, 309-311
       Kruskal's algorithm, 260-262
       maxflow, 434-436
       mincost flow, 451
       MST algorithms, 269-270
       NP-hard problems, 339
       path search, 61
       preflow-push, 416-419
       Prim's algorithm, 269
       random graph connectivity, 144
       shortest path algorithms, 301
       strong components in digraphs, 205-206
       transitive closure, 172-174, 177, 180, 221-222
       weighted graphs, 235
       see also Performance

    Scheduling problem, 4, 150, 483
       DAGs, 186-187
       precedence-constrained, 332-338
       see also Topological sorting
    Search. See Graph search
    Selection, 331
    Self-loop, 8, 18, 28
       digraphs, 152
       networks, 278
       relations, 183
    Sentinel weight, 235, 278, 287
    Separability, 112-117
    Separation vertex, 117-118
    Set-inclusion DAG, 184
    Shortest path, 176, 277-365
       acyclic networks, 313-321
       augmenting paths, 393-394, 398-399, 405-407
       Bellman-Ford algorithm, 350-356, 358-360
       BFS, 121-123
       defined, 279
       Dijkstra's algorithm, 293-302, 305-307, 349, 354-360
       Euclidean networks, 322-326
       Floyd's algorithm, 304, 307-311, 349-351, 354-356
       and longest path, 329-330
       multisource, 314-318
       negative weights, 345-361
       network simplex algorithm, 472-473
       NP-hard problems, 339-340
       performance, 301, 363-365
       reduction, 328-343
       relaxation, 285-292
       shortest paths tree (SPT), 279, 287-288, 294
       source-sink, 281, 294, 322-326
       terminology, 286, 313
       see also All-pairs shortest path; Network; Single-source shortest path
    Simple connectivity, 72, 106-109
    Simple graph, 8
    Simple path, 10, 57-59, 61
       DFS, 106
       networks, 279
    Simplex method, 479
    Single-source longest paths, 334-335
    Single-source shortest paths, 72, 127, 281
       acyclic networks, 314-315
       Dijkstra's algorithm, 293-294
       and mincost flow problem, 472-473
       negative weights, 350-354
       reachability, 166-167
    Sink, 154, 195-197, 281, 375-378
    Software library, 485
    Sollin, G., 267
    Sorting, 331
    Source vertex, 14, 154, 195-197, 281, 375-378
    Source-sink shortest path, 281, 294, 322-326
    Spanning forest, 12, 93, 110
    Spanning tree, 12, 72
       feasible, 453-455
       maxflow, 454-455
       network simplex algorithm, 457-464
       see also Minimum spanning tree
    Sparse graph, 13, 29
    st-connectivity, 119
    st-cut, 385-387, 427-428
    st-network, 375-378, 429-430
    Stack, LIFO, 132-134, 138
    Stack-based augmenting-path method, 400, 402
    Static graph, 18-19, 42, 50
    STL list, 31-33
    Strong components, 157-158, 205-214
       transitive closure, 217-219
    Strong connectivity, 72, 156-158, 205
    Subgraph, 9
       forbidden, 73
       maximal connected, 11-12
    Subset inclusion, 184
    Supply lines problem, 370, 386-387
    Symbol table
       find edge, 41
       graph-building function, 50-52
       indexing function, 51
    Symmetric relation, 183

    Tarjan, R. E., 410
    Tarjan's algorithm, 73, 206, 210-213
    Telephone network, 370
    Topological sorting, 150, 187, 191-199
       DFS, 193-195, 201-204
       multisource shortest-paths, 314-318
       relabeling/rearrangement, 191-192
       reverse, 193-195
    Total order, 185
    Tour, 10
       Euler, 62-64, 109
       Hamilton, 59-62
       mail carrier problem, 74
       traveling salesperson problem, 76
    Tractable problem, 72
    Traffic flow, 369
    Transaction, 5
    Transaction graph, 49-50
    Transitive closure, 72, 169-180
       abstract, 174-175, 216-220
       and all-pairs shortest paths, 175, 328-329
       Boolean matrix multiplication, 169-172, 176-177
       DAGs, 201-204
       DFS-based, 177-179
       performance, 172-174, 177, 179-180, 221-222
       of a relation, 183
       Warshall's algorithm, 172-175
    Transitive reduction, 223
    Transitive relation, 183
    Transportation problem, 368, 475-476
    Traveling salesperson problem, 76
    Tree, 12, 72
       BFS, 124-129
       binary, 188-190
       and DAGs, 188-190
       DFS, 90, 98-103, 113-117, 161-162
       edge, 99, 113-115, 161-162, 202
       preorder tree traversal, 101
       shortest-path tree (SPT), 279, 287-288, 294
       spanning, 453-455, 457-464
       see also Minimum spanning tree (MST)
    Tree link, 99-100
    Tremaux exploration, 83-86, 87-90, 109
    Two-coloring, 110-111
    Two-way Euler tour, 66, 109

    Uncapacitated edge, 381
    Undirected graph, 14-15, 36
       and digraphs, 153, 155-162, 165-167, 179-180
       networks, 429-430
       reachability, 205
       underlying, 15
    Uniconnected digraph, 224
    Union, 12
    Union-find algorithm, 22, 43
       Boruvka's algorithm, 264-265
       and DFS, 108-109
       Kruskal's algorithm, 263
       performance, 145

    Vector, vertex-indexed, 37, 96
    Vector-of-edges representation, 24, 37
    Vertex, 7-10
       active, 411
       adjacent, 9
       connectivity, 119, 438
       cut, 117-118
       degree of, 9
       destination, 14
       disjoint, 11
       dummy, 376-377
       excess, 411
       fringe, 253
       height, 412-415
       indegree/outdegree, 14
       inflow/outflow, 375-378
       marking, 92-93
       ordered pair, 14
       potentials, 416-419, 454-456, 468
       printing, 19-20
       reachable, 152, 158
       removing, 41
       search, 109-110
       separation, 117-118
       sink/source, 14, 154, 195-197, 281, 375-378
    Vertex-based preflow-push algorithm, 416
    Vertex-indexed vector, 37, 96
    V -vertex graph, 7

    Warshall's algorithm, 172-175, 289-290, 307-309
    Weighted diameter, 304
    Weighted graph, 15, 227-229
       adjacency-matrix representation, 37
       ADTs, 230-239
       arbitrary weights, 228
       bipartite matching, 74
       digraphs, 277-278
       edge weights, 234-235
       equal weights, 228-229
       integer weights, 379-380
       negative weights, 345-365
       path weight, 277
       reweighting, 324, 357-360
       sentinel weight, 235, 278
       see also Minimum spanning tree (MST); Shortest path
    Whitney's theorem, 119
    World Wide Web, 4

    Updates

    Errata

    Click for the Errata related to this title.

    Submit Errata

    More Information

    Unlimited one-month access with your purchase
    Free Safari Membership