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

Description

• Copyright 2002
• Dimensions: 7-3/4" x 9-1/4"
• Pages: 512
• Edition: 3rd

• Book
• ISBN-10: 0-201-31663-3
• ISBN-13: 978-0-201-31663-6

Once again, Robert Sedgewick provides a current and comprehensive introduction to important algorithms. The focus this time is on graph algorithms, which are increasingly critical for a wide range of applications, such as network connectivity, circuit design, scheduling, transaction processing, and resource allocation. In this book, Sedgewick offers the same successful blend of theory and practice with concise implementations that can be tested on real applications, which has made his work popular with programmers for many years.

Algorithms in C, Third Edition, Part 5: Graph Algorithms is the second book in Sedgewick's thoroughly revised and rewritten series. The first book, Parts 1-4, addresses fundamental algorithms, data structures, sorting, and searching. A forthcoming third book will focus on strings, geometry, and a range of advanced algorithms. Each book's expanded coverage features new algorithms and implementations, enhanced descriptions and diagrams, and a wealth of new exercises for polishing skills. A focus on abstract data types makes the programs more broadly useful and relevant for the modern object-oriented programming environment.

Coverage includes:

• A complete overview of graph properties and types
• Diagraphs and DAGs
• Minimum spanning trees
• Shortest paths
• Network flows
• Diagrams, sample C code, and detailed algorithm descriptions

The Web site for this book (http://www.cs.princeton.edu/~rs/) provides additional source code for programmers along with numerous support materials for educators.

A landmark revision, Algorithms in C, Third Edition, Part 5 provides a complete tool set for programmers to implement, debug, and use graph algorithms across a wide range of computer applications.



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.



For Instructors

Course Support

Click for the Course Support related to this title.



Sample Content

Downloadable Sample Chapter

Click below for Sample Chapter related to this title:
sedgewickch21.pdf

Table of Contents

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.

18. Graph Search.

Exploring a Maze.

Depth-First Search.

Graph-Search ADT Functions.

Properties of DFS Forests.

DFS Algorithms.

Separability and Biconnectivity.

Breadth-First Search.

Generalized Graph Search.

Analysis of Graph Algorithms.

19. Digraphs and DAGs.

Glossary and Rules of the Game.

Anatomy of DFS in Digraphs.

Reachability and Transitive Closure.

Equivalence Relations and Partial Orders.

DAGs.

Topological Sorting.

Reachability in DAGs.

Strong Components in Digraphs.

Transitive Closure Revisited.

Perspective.

20. Minimum Spanning Trees.

Representations.

Underlying Principles of MST Algorithms.

Prim's Algorithm and Priority-First Search.

Kruskal's Algorithm.

Boruvka's Algorithm.

Comparisons and Improvements.

Euclidean MST.

21. Shortest Paths.

Underlying Principles.

Dijkstra's algorithm.

All-Pairs Shortest Paths.

Shortest Paths in Acyclic Networks.

Euclidean Networks.

Reduction.

Negative Weights.

Perspective.

22. Network Flows.

Flow Networks.

Augmenting-Path Maxflow Algorithms.

Preflow-Push Maxflow Algorithms.

Maxflow Reductions.

Mincost Flows.

Network Simplex Algorithm.

Mincost-Flow Reductions.

Perspective.

References for Part Five.


Index. 0201316633T09172001

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. 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.

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 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.

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 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.

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. 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.

Programming Language

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.

0201316633P09182001

Index

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



Updates

Errata

Click for the Errata related to this title.

Submit Errata

