EVERYDAY DISCOUNT OFFER
Buy 2 or more eligible titles and save 35%*—use code BUY2. 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 with concise implementations that can be tested on real applications, which has made his work popular with programmers for many years.
Algorithms in C, Third Edition, Part 5: Graph Algorithms is the second book in Sedgewick's thoroughly revised and rewritten series. The first book, Parts 1-4, addresses fundamental algorithms, data structures, sorting, and searching. A forthcoming third book will focus on strings, geometry, and a range of advanced algorithms. Each book's expanded coverage features new algorithms and implementations, enhanced descriptions and diagrams, and a wealth of new exercises for polishing skills. A focus on abstract data types makes the programs more broadly useful and relevant for the modern object-oriented programming environment.
Coverage includes:
The Web site for this book (http://www.cs.princeton.edu/~rs/) provides additional source code for programmers along with numerous support materials for educators.
A landmark revision, Algorithms in C, Third Edition, Part 5 provides a complete tool set for programmers to implement, debug, and use graph algorithms across a wide range of computer applications.
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.
Click below for Sample Chapter related to this title:
sedgewickch21.pdf
Preface.
Notes on Exercises.
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. Nearly 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 has become indispensable in 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 uses of priority-queue, symbol-table, and union-find ADTs--all of which are described in de-tail 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 of the properties of the algorithms 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 complete 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. Although not emphasized, 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 (versions of the book in C++ and Java are under development). Any particular language has advantages and disadvantages; we use C in this book because it is widely available and provides the features needed for the implementations here. The programs can be translated easily to other modern programming languages because relatively few constructs are unique to C. We use standard C idioms when appropriate, but this book is not intended to be a reference work on C programming.
We strive for elegant, compact, and portable implementations, but we take the point of view that efficiency matters, so we try to be aware of the code's performance characteristics at all stages of development. There are many new programs in this edition, and many of the old ones have been reworked, primarily to make them more readily useful as abstract-data-type implementations. Extensive comparative empirical tests on the programs are discussed throughout the book.
A goal of this book is to present the algorithms in as simple and direct a form as possible. The style is consistent whenever possible so that similar programs look similar. 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.
Abstract transitive closure, 166-167, 208-212
Active vertex, 397
Acyclic graph: see Digraph, Directedacyclic graph (DAG)
Acyclic network, 300-307, 320-321
maxflow, 413-415
Adjacency-lists representation, 27-30
augmenting-paths method, 379
DFS, 84-85, 88, 95-96
digraphs, 31-32, 145, 147, 171
Dijkstra's algorithm, 284
Euler path, 59
find/remove edge, 34
flow networks, 365-368
performance, 29-30, 32-33,136-139
PFS, 242
removing vertices, 35
standard adjacency-lists DFS, 90, 153
transitive closure, 166
weighted graphs/networks, 32, 222-226, 266
Adjacency-matrix representation, 21-26
DFS, 81-82, 88
digraphs, 31-32, 145, 147, 161-164, 168, 171
flow networks, 365
linear-time algorithm, 53
performance, 25-26, 32-33, 136, 138
Prim's algorithm, 237-238
removing vertices, 34-35
standard adjacency-matrix DFS, 90-91, 153
weighted graphs/networks, 32, 222-226, 266
Adjacent vertices, 9
ADT, graph: see Graph ADT
Airline route, 270-271
All-pairs shortest paths, 269, 290-298
acyclic networks, 304-306
BFS, 120-121
negative weights, 342-346
path relaxation, 276-279
and transitive closure, 167, 315
and operation, 161-162
Arbitrage, 334-335
Arbitrary weight, 220
Arc, 8, 14
Array
of bits, 24
of edges, 18-19, 32-33, 226-227
isomorphic graphs, 25
of lists, 27-28
vertex-indexed, 32, 90
Articulation point, 110-112
Assignment problem, 68, 461-462
A* algorithm, 312
Augmenting-path method, 370-394
cycle canceling, 437
longest augmenting path, 382-383
maximum-capacity, 381, 386-388, 391-392
network simplex algorithm, 446-447
performance, 379, 381-394, 421-422
and preflow-push, 398
random flow networks, 387-390
shortest augmenting path, 380, 384-386, 391-393
stack-based, 386, 388
Back edge, 93, 107, 109, 154-157, 194-195
Back link, 93-94
Bellman-Ford algorithm, 338-342, 346, 433
BFS tree, 118-122
Binary DAG, 180-182
Binary decision diagram (BDD), 181
Binary tree, 180-182
Biconnectivity, 110-113
Bipartite graph, 13, 103-105
Bipartite matching, 67-68, 419-422, 461, 467
Boolean matrix multiplication, 161-164, 168-169
Boruvka's algorithm, 232-233, 251-255
Breadth-first search (BFS), 76, 114-123
and DFS, 122-123, 125-127
forest, 118
fringe size, 130
PFS, 241, 288
Bridge, 106-110
Bridges of Königsberg problem, 56-58
Call, program structure, 5
Capacity, flow, 358, 361
st-cut, 373
vertex-capacity constraints, 412-413
Change priority operation, 241
Circuit, 4
Circulation, flow network, 363-364, 415
Clique, 12, 69
Colorability problem, 69
two-coloring, 103-104
Communications network, 354-355
Complement, 12
Complete graph, 12
Connection, 3
Connectivity, 11-12
biconnectivity, 110-113
digraphs, 150
edge, 424-425
equivalence relations, 176
general connectivity, 68, 113
k-connected graph, 112-113
maxflow, 423-425
random, 134-137
simple connectivity, 65-66, 100-102
st-connectivity, 113
strong connectivity, 66, 148-150, 197
vertex connectivity, 112, 424
Construct operation, 249
Constraint, 178-179
Cost, 219, 358, 429
convex/nonlinear, 468
edge, 459-460
flow, 429
negative, 432-433
reduced, 440-443
see also Performance, Weighted graph
Critical edge, 385
Cross edge, 154, 194, 196
Crossing edge, 229, 373
Cut, 229
mincut, 373-375
property, 228-229, 233
set, 373
st-cut, 373-375, 414
vertex, 110-112
Cut problem, 355-356, 373-374
Cycle, 10-11, 462
DFS, 99
directed, 14, 147, 155-157
even, 67-68, 215
flow networks, 363-364, 413
MSTs, 228-232
negative, 267-268, 333-336, 432-440
odd, 103-104
property, 230-231
Cycle-canceling algorithm, 358, 433-438, 455
see also Network simplex algorithm
Cyclic path, 10, 148, 462-463
DAG: see Directed acyclic graph (DAG)
de Bruijn graph, 47
Decrease key operation, 243, 256-259, 287
Degrees-of-separation graph, 47
Delauney triangulation, 262
Delete the minimum operation, 239, 256-259
Dense graph, 13, 25-26
Depth-first search (DFS), 75-76, 81-86
and BFS, 122-123, 125-127
cycle detection, 99
digraphs, 152-160
fringe size, 130
functions, 90
PFS, 241
running time, 88-89
simple connectivity, 100-102
simple path, 51-53, 100
spanning tree, 103
standard adjacency representations, 90-91, 153
strong components algorithms, 199-206
topological sorting, 185-186, 193-196
transitive closure, 169-171
tree links, 93-94
and Tremaux exploration, 82-84
two-coloring, 103-104
two-way Euler tour, 61, 102-103
and union-find, 101-102
vertex search, 103
see also DFS forest, DFS tree
Destination vertex, 14
DFS forest, 91-97, 118
DAGs, 186
digraphs, 153-154, 156
DFS tree, 84, 91-97
bridges, 107-110
digraphs, 153-154
spanning tree, 103
d-heap, 256, 259-260
Diameter, network, 291
Difference constraints, 319-322, 324, 334
Digraph, 14-15, 141-216
adjacency-lists representation, 31-32, 145, 147, 171
adjacency-matrix representation, 31-32, 145, 147, 161-164, 168, 171
connectivity, 150, 424-425
decomposing, 158
defined, 144
DFS in, 152-160
directed cycle detection, 155-158
directed path, 144, 147
edge direction, 141-142
even cycles, 67-68
grid, 144
isomorphism, 142
map, 146
random, 211-212
and relations, 175
reverse, 146-147
running time of algorithms, 213-214
single-source reachability, 158-159
strong components, 149-150, 197-206
strongly connected, 66, 148-150, 197
transitive closure, 161-172, 208-212
and undirected graphs, 145, 148-154, 157-159, 171-172
uniconnected, 215
weighted, 265-266
see also Directed acyclic graph (DAG)
Dijkstra's algorithm, 244, 280-288
acyclic networks, 302, 306
all-pairs shortest paths, 292-294
Euclidean networks, 309-312
negative weights, 335, 342, 344, 346
and Prim's algorithm, 281
Directed acyclic graph (DAG), 14, 142, 178-196
binary, 180-182
defined, 148
detection, 155-157
dominators, 214-215
kernel, 149-150, 208-212
longest paths, 191
partial orders, 176-177
scheduling problem, 178-179
sink/source, 187-190
strong components, 149
topological sorting, 179, 183-193
transitive closure, 193-196
weighted, 300-307
Directed cycle, 14, 147, 155-157
Directed graph: see Digraph, Directed acyclic graph (DAG)
Directed path, 66, 144, 147, 215
Disjoint paths, 11, 111
Distances matrix, 276-277, 346
Distribution network, 430-431
Distribution problem, 354, 416-417, 430-431, 460
Dominator, 214-215
Down link, 93-94, 154, 194-196
Dummy edge, 433-437, 440-441, 457
Dummy vertex, 362-363
Dynamic algorithm, 19, 44
Dynamic reachability, 213
Edge, 7-10
array of edges, 18-19
back, 93, 107, 109, 154-157, 194-195
backward/forward, 371
connectivity, 424-425
costs, 459-460
critical, 385
cross, 154, 194, 196
crossing, 229, 373
directed, 14
disjoint, 11, 111, 423
down, 93-94, 154, 194-196
dummy, 433-437, 441, 457
eligible, 398, 442-443, 450-453
flows, 361
incident, 9
parallel, 8, 18, 24, 29, 41, 224, 266
random, 41
relaxation, 273-275, 309
separation, 107
tree, 93, 107, 109, 154, 194
uncapacitated, 368
Edge data type, 17, 32
Edge-based preflow-push algorithm, 400
Edge-connected graph, 106-107, 111-113, 424-425
Edge-separable graph, 106-107
Edmonds, J., 380-381
Eligible edge, 398, 442-443, 450-453
Empirical analysis
augmenting path, 389
bipartite matching, 420
connectivity, 138
minimum spanning tree, 258
preflow-push, 406
transitive closure, 172
Enumeration, graph, 142-143
Equal weights, 220-221
Equivalence class, 176
Equivalence relation, 175-176
Equivalent problems, 314
Erdös, P., 136
Euclidean graph, 10
MSTs, 261-263
neighbor graphs, 43
networks, 308-312, 389-390
Euclidean heuristic, 310-312
Euler path, 56-61
directed, 215
mail carrier, 463
two-way Euler tour, 102-103
Even cycle, 67-68, 215
Excess, vertex, 397
Existence problem, 69-70
Feasible flow, 397, 416-419, 430
Feasible spanning tree, 439-441
Feedback vertex set, 215
Fibonacci computation, 180, 256
FIFO queue, 115-119, 125-130
PFS, 288
preflow-push, 403, 405-407
topological sort, 188-190
Find edge operation, 34
Flow cost, 429
Flow network, 15, 353-471
augmenting-flow method, 370-394
backward/forward edges, 371
capacities, 358, 361, 373, 412-413
circulation, 363-364, 415
cut problems, 355-356, 373-374
defined, 361
distribution problems, 354, 416-417, 430-431, 460
equilibrium, 362-363
flows, 358, 361
inflow/outflow, 361-363
matching problems, 355, 419-422, 461, 467-468
maxflow-mincut theorem, 372-375
model, 359-360
network simplex algorithm, 358, 439-459, 464
preflow-push method, 396-409
random, 289-290
reductions, 353, 394, 411-426
representations, 365-368
residual, 376-377, 398, 403, 431-432, 439
st-network, 361, 415-416
value, 361
see also Maxflow problem, Mincost flow problem, Network
Floyd's algorithm, 168, 277, 291, 295-298
negative weights, 336-337, 341-342
Ford, L. R., 370
Ford-Fulkerson method: see Augmenting-path method
Forest, 12
BFS, 118
Boruvka's algorithm, 252
DFS, 91-97, 118, 153-154, 156, 186
Kruskal's algorithm, 246
see also DFS tree, Tree
Four-color theorem, 70
Fringe, 124-130, 283
Prim's algorithm, 239-243
priority queue, 379
Fulkerson, D. R., 370
Function call graph, 44-47
Gabow's algorithm, 198, 204-206
General connectivity, 68, 113
Generalized queue, 402, 404
Geometric algorithm, 263
Goldberg, A., 396
Graph ADT, 16-21
adjacency-lists representation, 27-30
adjacency-matrix representation, 21-26
all-pairs shortest paths, 291
augmenting-paths, 378
DFS, 82
equivalence relations, 176
flow networks, 366-368, 417-419, 431-432, 435
graph-search functions, 86-91
network simplex algorithm, 452, 454
PFS, 242
preflow-push, 404
symbol table, 45
weighted graphs, 222-227
Graph search, 75-139
ADT functions, 86-91
algorithm analysis, 133-139
biconnectivity, 110-113
generalized, 124-132
Hamilton tour, 54
maze exploration, 76-80
priority-first search, 239-244, 283-288, 309, 376-379
randomized, 130-131
separability, 106-111
simple path, 51-53, 55, 100
see also Breadth-first search (BFS), Depth-first search (DFS)
Graph type, 3-73
applications, 4-5
bipartite, 13, 103-104
complete, 12
connected, 11-12
de Bruijn, 47
defined, 7
degrees-of-separation, 47
dense/sparse, 13, 25-26
directed/undirected, 14-15
edge-connected/edge-separable, 106-107, 111
Euclidean, 10
function call, 44-47
interval, 47
isomorphic, 10, 25
multigraph, 8
neighbor, 43
planar, 9, 67
random, 41-42
simple, 8
static, 18-19
subgraph, 9
transaction, 43-44
see also Digraph, Directed acyclic graph (DAG), Undirected graph, Weighted graph
Graph-processing problem, 64-73
client, 20
degree of difficulty, 65, 71-73
existence, 69-70
intractable, 69
NP-hard, 69, 71, 325-326
tractable, 66
Grid digraph, 144
Hamilton path, 53-55, 215, 325-326
Height function, 398-402
Highest-vertex preflow-push, 408
Hypertext, 4
Immediate dominator, 214-215
Incident edge, 9
Indegree, 14, 146-147, 190
Independent set problem, 69
Indexing function, 46
Induced subgraph, 9
Infeasible problem, 321
Inflow, 361
Initial height function, 398-399
Integer weights, 367
Interface, graph ADT, 16-21
Intersection, 76
Interval graph, 47
Intractable problem, 69, 328
Irreflexive relation, 175
Isomorphic graphs, 10, 25, 71, 142
Item, 3
Jarnik's algorithm, 244
Job placement, 355, 461
Job scheduling, 4, 142, 178-179
negative cycles, 333-334
shortest paths, 318-324
see also Topological sorting
Johnson, D., 256
Johnson's algorithm, 346
Karp, R., 198, 380-381
k-connected graph, 112-113
Kernel DAG, 149-150, 208-212
k-neighbor graph, 43
Konigsberg, bridges of, 56-58
Kosaraju's algorithm, 198-201
Kruskal's algorithm, 231-232, 246-251, 256
Kuratowski's theorem, 67
Least common ancestor (LCA), 445
Length, path, 11
< operator, 279
Library programming, 323
LIFO stack, 125-127, 130
Linear programming (LP), 319, 329, 351
maxflow, 425-426
mincost flow, 411, 464
multicommodity flow, 468
network flow algorithms, 357-358
Linear-time algorithms, 53
Link, 4, 8
back, 93-94
DFS tree, 93-94
down, 93-94, 154, 194-196
parent, 91-94, 157
Locality property, 42
Longest paths, 69, 191, 302-306
augmenting paths, 382-383
difference constraints, 320-321
and shortest paths, 316
Mail carrier problem, 68, 215, 462-464
Map, 4, 146, 312
Matching, 5, 67
bipartite, 68, 419-422, 461
maximum, 467-468
maximum-cardinality, 419, 467
minimum-distance point matching, 355
Mathematical programming, 329
Matrix, adjacency, 21-26
Maxflow problem, 358, 361-364, 370-426
acyclic networks, 413-415
augmenting-path method, 370-394
bipartite matching, 419-422
capacity constraints, 412-413
connectivity, 423-425
feasible flow, 416-418
general networks, 412
linear programming, 425-426
and mincost flow problem, 411, 457-458
mincost maxflow, 430-431
preflow-push method, 396-409
reductions, 356, 394, 411-426
running time, 420-422
spanning tree, 440-441
standard, 411-412
undirected networks, 415-416
Maxflow-mincut theorem, 372-375, 423-424
Maximal connected subgraph, 11-12
Maximum-capacity augmenting path, 381, 386-388, 391-392
Maximum-cardinality matching, 419, 467
Maze, 76-80
Menger's theorem, 112-113, 423
Merchandise distribution, 354, 416-417, 430-431, 460
Mincost flow problem, 358, 429-464
assignment problem, 461-462
cycle-canceling algorithm, 358, 433-438, 455
edge costs, 459-460
eligible edges, 442-443
feasible flow, 430-431, 458
flow cost, 429
LP formulation, 411, 464
mail carrier, 462-464
and maxflow problem, 411, 457-458
mincost maxflow, 430-431
reductions, 457-464
running time, 437
single-source shortest paths, 458
transportation, 460-462
see also Network simplex algorithm
Mincut, 373-375
Minimum spanning tree (MST), 66, 219-263
Boruvka's algorithm, 232-233, 251-255
cut and cycle properties, 228-233
defined, 220
equal weights, 220-221
Euclidean, 261-263
Kruskal's algorithm, 231-232, 246-251, 256
performance, 255-260, 257
Prim's algorithm, 231, 235-244, 251, 256-257
representations, 226-227
weighted-graph ADTs, 222-225
Minimum-distance point matching, 355
Modular arithmetic, 176
Multicommodity flow, 468
Multigraph, 8
Multisource paths, 301-304
Negative cost, 432-433
Negative cycle, 267-268, 333-336, 432-440
Negative weight, 331-351
arbitrage, 334-335
Bellman-Ford algorithm, 338-342, 346
Dijkstra's algorithm, 335, 342, 344, 346
Floyd's algorithm, 336-337, 341-342
Neighbor graph, 43, 136
Network, 5, 15, 265-271
acyclic, 300-307, 320-321, 413-415
adjacency representations, 32
communications, 354-355
distribution, 430-431
reliability, 356
residual, 376-377, 398, 403, 431-432, 439
reweighting, 310, 343-346
st-network, 361, 415-416
telephone, 356
undirected, 415-416
weighted diameter, 291
see also Flow network, Shortest paths
Network simplex algorithm, 358, 439-455
assignment problem, 462
eligible edges, 442-443, 450-453
feasible spanning tree, 439-441
implementations, 452, 454
initialization, 450
parent-link representation, 444-449
performance, 453-455
shortest paths, 458-459
simplex method, 464
vertex potentials, 440-441, 454
see also Mincost flow problem
Node, 8
Nonlinear cost, 468
NP-hard problem, 69, 71, 325-326
Online algorithm, 19
Operations research (OR), 329, 352
Optimization, 70
or operation, 161-162
Ordered pair, 14, 175
Outdegree, 14, 146-147
Outflow, 361
Parallel edges, 8, 18, 24
adjacency-lists representation, 29
networks, 266
random graphs, 41
weighted graphs, 224
Parent-link representation cycle detection, 157
DFS tree, 91-94
network simplex algorithm, 444-449
Partial order, 176-177
Passage, 76
Path, 10-11, 50-62
cyclic, 10, 148, 462-463
directed, 66, 144, 147, 215
disjoint, 11, 111
Euler, 56-61, 102-103
Hamilton, 53-55, 215, 325-326
mail carrier, 463
relaxation, 274, 276-277
simple, 51-53, 55, 100, 267-268
weight, 265
see also Longest paths, Shortest paths
Paths matrix, 276-277, 346
Performance, 6, 71-73
abstraction, 36
adjacency-lists representation, 29-30, 32-33, 136-139
adjacency-matrix representation, 25-26, 32-33, 136, 138
array-of-edges, 32-33
augmenting-path method, 379, 381-394, 421-422
cycle canceling, 438
dense/sparse graphs, 13
DFS forests, 96-97
Dijkstra's algorithm, 287-288, 311-312
equivalent problems, 317
Kruskal's algorithm, 248-249
MST algorithms, 255-260
network simplex algorithm, 453-455
path search, 55-56, 58-59
PFS, 243-244, 285-287
preflow-push, 406-408
preprocessing time, 101, 120, 208-209
shortest-paths algorithms, 350-351
static graphs, 35
transitive closure, 171-172, 213
union-find algorithm, 139
worst-case, 37-38
see also Running time
PERT chart, 142
Planar graph, 9, 67
Planarity problem, 66-67
+ operator, 279
Polynomial-time reduction, 425
Postorder numbering, 95, 154, 185-186
Potential function, 405, 440-441, 454
Precedence constraint, 179, 318
Preflow, 397
Preflow-push method, 396-409
edge-based, 400
highest-vertex, 408
performance, 406-408
vertex-based, 402
Preorder numbering, 91-92, 95, 154
Preprocessing, 101, 120, 208-209
shortest paths, 269-270, 291-292
Prim's algorithm, 231, 235-244, 251
and Dijkstra's algorithm, 281
running time, 256-257
Priority queue, 130, 256
augmenting-path method, 376-379
Kruskal's algorithm, 249-251
multiway heap, 259
Priority-first search (PFS), 128, 309
augmenting-path method, 376-379
BFS, 241, 288
Dijkstra's algorithm, 283-288
DFS, 241
Prim's algorithm, 239-244
Shortest paths in Euclidean networks, 309-310
Program structure, 5
Pushdown stack, 115
Quicksort, 248, 250, 256
Radar tracking system, 355
Radix sort, 248, 256
Random flow network, 389-390
Random graph, 41-43, 134-137
Randomized queue, 130, 388
Reachability, 144, 150, 158-159
DAGs, 193-196
digraphs, 197
dynamic, 213
see also Transitive closure
Reduced cost, 440-443
Reduction, 169, 271, 469-470
difference constraints, 319-322, 324
equivalent problems, 314
flow networks, 353
implications, 327
job scheduling, 318-324
linear programming, 319, 329
maxflow, 356, 394, 411-426
mincost flow, 457-464
polynomial-time, 425
shortest paths, 314-329
transitive, 215
upper/lower bounds, 328-329
Reflexive relation, 175
Relation, 175
Relaxation, 273-279, 309
Remove edge operation, 29, 34
Renyi, A., 136
Residual network, 376-377, 439
mincost flow, 431-432
preflow-push, 398, 403
Reverse topological sorting, 185-186
Reweighting, 310, 343-346
Road map, 270
Running time, 134
augmenting-path method, 379, 390
Bellman-Ford algorithm, 341-342
Boruvka's algorithm, 253
DFS, 88-89
digraphs, 213-214
Dijkstra's algorithm, 283, 286, 298
Floyd's algorithm, 296-298
Kruskal's algorithm, 248-249
maxflow, 420-422
mincost flow, 437
MST algorithms, 257-258
NP-hard problems, 325
path search, 55
preflow-push, 405
Prim's algorithm, 256-257
random graph connectivity, 136
shortest paths algorithms, 287
strong components in digraphs, 197-198
transitive closure, 164-166, 169, 172, 213-214
see also Performance
Scheduling problem, 4, 142, 468
DAGs, 178-179
precedence-constrained, 318-324
see also Topological sorting
Search: see Graph search
Selection, 317-318
Self-loop, 8, 18, 24
digraphs, 144
networks, 266
relations, 175
Sentinel weight, 223, 266, 275
Separability, 106-111
Separation vertex, 110-112
Set-inclusion DAG, 176
Shortest paths, 168, 265-352
acyclic networks, 300-307
augmenting paths, 380, 384-386, 391-393
Bellman-Ford algorithm, 338-342, 346
BFS, 114-115
defined, 266-268
Dijkstra's algorithm, 280-288, 292-294, 335, 342-346
Euclidean networks, 308-312
Floyd's algorithm, 291, 295-298, 336-337, 341-342
and longest paths, 316
multisource, 301-304
negative weights, 331-347
network simplex algorithm, 458-459
NP-hard problems, 325-326
performance, 287, 350-351
reduction, 314-329
relaxation, 273-279
shortest paths tree (SPT), 267, 274-275, 281
source-sink, 269, 281, 308-312
terminology, 271, 300
see also All-pairs shortest paths, Network, Single-source shortest paths
Simple connectivity, 65-66, 100-102
Simple graph, 8
Simple path, 10, 51-53, 55
DFS, 100
networks, 267-268
Simplex method, 464
Single-source longest paths, 320-321
Single-source shortest paths, 66, 120, 269
acyclic networks, 301-302
Dijkstra's algorithm, 280-281
and mincost flow problem, 458
negative weights, 336-338
reachability, 158-159
Sink, 146, 187-188, 269, 361
Sollin, G., 255
Sorting, 317-318
Source vertex, 14, 146, 187-188, 269, 361
Source-sink shortest path, 269, 281, 308-312
Spanning forest, 12
Spanning tree, 12, 66, 103
feasible, 439-441
maxflow, 440-441
network simplex algorithm, 443-449
see also Minimum spanning tree
Sparse graph, 13, 25-26
Stack, LIFO, 125-127, 130
Stack-based augmenting-path method, 386, 388
Static graph, 18-19, 35, 44
st-connectivity, 113
st-cut, 373-375, 414
st-network, 361, 415-416
Strong components, 149-150, 197-206
transitive closure, 209-210
Strong connectivity, 66, 148-150, 197
Subgraph, 9
forbidden, 67
maximal connected, 11-12
Subset inclusion, 176
Supply lines problem, 356, 373-374
Symbol table
find edge, 34
graph-building function, 44-45
indexing function, 46
Symmetric relation, 175
Tarjan, R. E., 396
Tarjan's algorithm
planarity, 67
strong connectivity, 198, 202-204
Telephone network, 356
Topological sorting, 142, 179, 183-191
DFS, 185-186, 193-196
multisource shortest-paths, 301-304
relabeling/rearrangement, 183-184
reverse, 185-187
Total order, 177
Tour, 10
Euler, 56-61, 102-103
Hamilton, 53-55
mail carrier problem, 68
traveling salesperson problem, 70
Tractable problem, 66
Traffic flow, 355
Transaction, 5
Transaction graph, 43-44
Transitive closure, 66, 161-172
abstract, 166-167, 208-212
and all-pairs shortest paths, 167, 315
Boolean matrix multiplication, 161-164, 168-169
DAGs, 193-196
DFS-based, 169-171
performance, 164-166, 169, 171-172, 213-214
of a relation, 175
Warshall's algorithm, 164-167
Transitive reduction, 215
Transitive relation, 175
Transportation problem, 354, 460-462
Traveling salesperson problem, 70
Traversal function, 19
Tree, 12, 66
BFS, 118-122
binary, 180-182
and DAGs, 180
DFS, 84, 91-97, 103, 107-110, 153-154
edge, 93, 107, 109, 154, 194
preorder tree traversal, 95
shortest-paths tree (SPT), 267, 274-275, 281
spanning, 103, 439-441, 443-449
see also Minimum spanning tree (MST)
Tree link, 93-94
Tremaux exploration, 77-80, 82-84, 102-103
Two-coloring, 103-105
Two-way Euler tour, 61, 102-103
Uncapacitated edge, 368
Undirected graph, 14-15, 31
and digraphs, 145, 148-154, 157-159, 171-172
networks, 415-416
reachability, 197
underlying, 15
Uniconnected digraph, 215
Union, 12
Union-find algorithm, 19, 37
in Boruvka's algorithm, 252-253
and DFS, 101-102
in Kruskal's algorithm, 251
performance, 139
Vertex, 7-10
active, 397
adjacent, 9
connectivity, 112, 424
cut, 110-112
degree of, 9
destination, 14
disjoint, 11
dummy, 362-363
excess, 397
fringe, 241
height, 398-402
indegree/outdegree, 14
inflow/outflow, 361
marking, 86
ordered pair, 14
potentials, 405, 440-441, 454
reachable, 144, 150
removing, 34-35
search, 103
separation, 110-112
sink/source, 14, 146, 187-188, 269, 361
Vertex-based preflow-push algorithm, 402
Vertex-indexed array, 32, 90
Warshall's algorithm, 164-167, 277, 295-296
Weighted diameter, 291
Weighted graph, 15, 219-221
adjacency-matrix representation, 32
ADTs, 222-225
arbitrary weights, 220
bipartite matching, 68
digraphs, 265-266
equal weights, 220-221
integer weights, 367
negative weights, 331-351
path weight, 265
reweighting, 310, 343-346
sentinel weight, 223, 266
see also Minimum spanning tree (MST), Shortest paths
Whitney's theorem, 112
World Wide Web, 4
Worst-case performance, 37-38