Robert Sedgewick
Algorithms in C: Graph Algorithms
Addison - Wesley, Boston, 2002
Softcover, pp. 482, plus XIII, USA $ 38.50
ISBN 0-201-31663-3
http://www.pearsoneduc.com

In general about the book

Graph theory is a relatively new field in mathematics. Nevertheless, by now graph theory is developed and well-understood field. In essence graphs are used to model relationships among pairs of objects. Many books on graph theory and graph algorithms have been published. This book is another addition to the broad selection of texts available that are aimed at the advanced undergraduate and first- year graduate level treatment of computer systems. The author states in the preface that: "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". He had indeed succeeded in including much material on graph algorithms that has not previously been available in textbook form at this level. 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, Chapters 1- 16) deals with fundamental concepts, data structures, sorting and searching, the second volume (Part 5, Chapters 17-22) focuses on graph algorithms, while the future third volume (Parts 6-8) will cover strings, geometry, and variety of other advanced topics. This book is divided into six chapters, References for Part V, and Index.

Chapter content

Chapter 17 (first chapter in this volume) entitled as "Graph Properties and Types" concentrates on basics for developing an understanding of graph algorithms ranging from the simple ones, already described in the first volume Part I, to the sophisticated ones presented in Chapters 18 through 22 of this book. Chapter 18, "Graph Search", considers the fundamental graph-search algorithms. The main topics discussed here are depth-first search, breadth-first search, their related algorithms, and their application to graph theory. In Chapter 19, "Digraphs and DAGs", algorithms for solving the topological-sorting, transitive- closure, and shortest-path problem for directed graphs (digraphs) and for directed acyclic graphs (DAGs) are considered. Chapter 20, "Minimum spanning Trees" deals with algorithms for determining the lowest-cost way to connect all the points for a graph. In Chapter 21, entitled as "Shortest Paths", properties of various shortest-paths algorithms are considered. Chapter 22, "Network Flow", cover details concerning classical solutions to network-flow problems.

Useful for advanced undergraduate and first-year
graduate students of computer-science

The book is easy to read and the explanations are clear and well written. Throughout the book there are numerous exercises (that test your understanding, that add new and thought-provoking information, that are intended to challenge you, and that are extremely difficult). In other words it emphasizes the creative side of graph-algorithm design. As an overall summary, I found the book extremely interesting, and I encourages everyone who uses or teaches algorithm design to get a copy of the book.