Swipe to navigate through the chapters of this book
This chapter introduces graphs as diagrams for solving puzzles. Careful definitions specify the language of graph theory: vertices, edges, degrees, paths, circuits, Euler paths, Hamilton paths, and so on. Then our interest returns to trees, with algorithms for depth-first traversal and for breadth-first traversal.
Algorithms for constructing a minimum connector and finding shortest paths joining two specified vertices are given for edge-weighted graphs. Finally, for directed graphs, we give Dijkstra’s Algorithm for shortest dipaths and the Floyd-Warshall Algorithm for the distance matrix.
Please log in to get access to this content
To get access to this content you need the following product:
- Graphs and Trees
- Springer International Publishing
- Sequence number
- Chapter number
- Chapter 5