EVERYDAY DISCOUNT OFFER
Buy 3 or more eligible titles and save 40%*—use code BUY3. Shop now.
Register your product to gain access to bonus material or receive a coupon.
This eBook includes the following formats, accessible from your Account page after purchase:
EPUB The open industry format known for its reflowable content and usability on supported mobile devices.
MOBI The eBook format compatible with the Amazon Kindle and Amazon Kindle applications.
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.
This eBook includes the following formats, accessible from your Account page after purchase:
EPUB The open industry format known for its reflowable content and usability on supported mobile devices.
MOBI The eBook format compatible with the Amazon Kindle and Amazon Kindle applications.
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.
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 that has made his work popular with programmers for many years. Christopher van Wyk and Sedgewick have developed concise new C++ implementations that both express the methods in a natural and direct manner and also can be used in real applications.
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:
The Web site for this book (http://www.cs.princeton.edu/~rs/) provides additional source code for programmers along with a wide range of academic 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.
Code for Algorithms in C++, Third Edition, Part 5
Click below for Supplements related to this title:
Supplements
Click below for Web Resources related to this title:
Author's Web Site
Click for the Author's Web Site related to this title.
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.
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.
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.
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.
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.
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.
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
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 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
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