2014 | OriginalPaper | Chapter

# 7. Finite Graph Algorithms

Published in:
Practical Analysis of Algorithms

## Abstract

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.