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

About

Features

Description

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.

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.

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.

Representations.

Underlying Principles of MST Algorithms.

Prim's Algorithm and Priority-First Search.

Kruskal's Algorithm.

Boruvka's Algorithm.

Comparisons and Improvements.

Euclidean MST.

Underlying Principles.

Dijkstra's algorithm.

All-Pairs Shortest Paths.

Shortest Paths in Acyclic Networks.

Euclidean Networks.

Reduction.

Negative Weights.

Perspective.

Flow Networks.

Augmenting-Path Maxflow Algorithms.

Preflow-Push Maxflow Algorithms.

Maxflow Reductions.

Mincost Flows.

Network Simplex Algorithm.

Mincost-Flow Reductions.

Perspective.

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

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