Scope

This book, Algorithms in Java, 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 Java, C++, or C. Algorithms in Java, Third Edition, Parts 1 “4 , is certainly adequate preparation. This volume assumes basic knowledge about arrays, linked lists, and abstract data types (ADTs) 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.