Swipe to navigate through the chapters of this book
This chapter introduces a variety of classical finite graph algorithms, such as are taught in upper level computer science classes, together with an analysis of their complexity. It starts with the formal definition and classification of graphs. Then it discussed implementation details and a C++ graph class example. Breadth-first and depth-first traversals are discussed and an application to counting the connected components of a graph is provided. Then Dijkstra’s algorithm is introduced, followed by Kruskal’s and Prim’s. The problems of topological sorting and maximum flow are discussed. Finally, special tours such as Hamiltonian are discussed, as well as their feasibility.
Please log in to get access to this content
- Finite Graph Algorithms
- Springer International Publishing
- Sequence number
- Chapter number
- Chapter 7