Searching Graph and Tree data structures

In the previous chapter, we learned about graphs and trees. As we progress through the chapter, keep in mind that whenever we refer to graphs, this includes trees because trees are simply graphs that have no cycles. The topic of this section is the idea of searching graphs. This simply means to travel along the edges of a graph to locate paths to destination vertices. This sounds like a simple thing to do, but we hope to do it as efficiently as we can because many real-world graphs are huge.

There are many reasons why we might want an algorithm to traverse the graph to find vertices. For example, suppose you want to send a message over the internet to five of your friends living in five different cities. There certainly will be no direct connection between your device and your friends' devices, so the message must follow multiple paths from vertex to vertex through networked devices until it reaches your friends. Networked devices connect...