Summary

In this chapter, we used our understanding of graph structures, including trees and networks, from Chapter 8, Storage and Feature Extraction of Graphs, Trees, and Networks, and learned about some practical graph-oriented problems and popular algorithms for solving them.

We began by learning about graph searches where we traverse a graph to discover its structure and perhaps do some calculations at each vertex. Then, we moved on to perhaps the most common graph search algorithm, DFS. We did an example on a small graph by hand before writing a Python implementation of the algorithm, which we confirmed led to the same results as the example we did by hand.

Then, we moved on to a very practical problem: finding the shortest paths between vertices in networks. This problem has applications in finding optimal travel routes, sending messages over a computer network through good paths, efficiently delivering electricity over electrical grids, and many other areas. With some networks...