The first edition of this book [1] was an undergraduate level text widely used in courses like “Data structures” and “Analysis of algorithms.” In this third edition, Sedgewick divides his first edition into three separate texts (the second of which is the subject of this review):

• Algorithms in C++, Parts 1 to 4, covering fundamental concepts, data structures, sorting algorithms, and searching algorithms. This volume contains the first 16 chapters of the three-volume set.
• Algorithms in C++, Part 5, covering graphs and graph algorithms. This volume contains chapters 17 through 22.
• Algorithms in C++, Parts 6 to 8, the yet-to-be published third volume, which will cover strings, computational geometry, and advanced algorithms.

The first edition, which had companion versions in C and Pascal, was widely praised for explaining complex algorithms at an intuitive level through the use of hundreds of figures, scattered throughout the book. In this edition, Sedgewick expands the use of sequential figures to demonstrate clearly the principal graph structures, their properties, and the behavior of the associated algorithms. A C version of the book is available, and a Java version should be out shortly.

The first edition was criticized for simply translating Pascal into C++ for the associated code. In the third edition, Sedgewick has wisely employed the services of Christopher Van Wyk to provide C++ consulting. Consequently, the C++ code is object oriented, and should be quite useful to serious students.

There are six chapters, “Graph Properties and Types,” “Graph Search, Digraphs and DAGs,” “Minimum Spanning Trees,” “Shortest Paths,” and “Network Flows.” The first step to wisdom, as the Chinese say, is getting things by their right names. In “Graph Properties and Types,” Sedgewick offers a lucid taxonomy of graph types, explanations of the fundamental paths (Simple, Hamilton, and Euler), and clear definitions of the principal properties (connectivity, colorability, transitive closure, isomorphism, and so on). The “Graph Search” chapter provides clear, detailed explanations of breadth-first and depth-first search. In the succeeding chapters, there are excellent treatments of the classic algorithms for minimum spanning trees and shortest paths. The dramatically expanded size of the third edition also allows room for topics seldom covered in similar texts such as the Tremaux maze exploration and the failure of Dijkstra’s shortest path when confronted with negative weights.

The paragraphs above describe what this book is; it is probably just as important to describe what it is not. It is not a rigorous mathematical treatment of graph theory, nor does it offer any groundbreaking advancement of the topic. It is, as the author promised, “useful as [a text] early in the computer science curriculum” and “as a reference for people engaged in the de velopment of computer systems or applications programs.”

I don’t know if a Java-based review of the third edition would be as favorable as this C++-based review is; but I suspect that a C-based one would be. In either case, the insightful explanations should hold across languages. A three-language version of a given text is ample evidence that the problem of selecting a language on which to base a computer science education continues to bedevil both students and faculty, just as it continues to torment industry. And those who claim that the choice of language/operating system/database is irrelevant to good design should be condemned to the purgatory of the many projects that are imploding around such choices. But at least from the C/C++ perspective, Sedgwick’s effort may join the set of computer science undergraduate classics, particularly if Parts 1 to 4 and Parts 6 to 8 are of the same quality.