Graphs play an important part in solving many networking problems. One problem, for example, is determining the best way to get from one node to another in an internet, a network of gateways into other networks. One way to model an internet is using an undirected graph in which vertices represent nodes, and edges represent connections between the nodes. With this model, we can use breadth-first search to help determine the smallest number of traversals, or hops, between various nodes.
For example, consider the graph in Figure 11.8, which represents an internet of six nodes. Starting at node1 , there is more than one way we can reach node4 . The paths 〈 node1 , node2 , node4 〉, 〈 node1 , node3 , node2 , node4 〉, and 〈 node1 , node3 , node5, node4 〉 are all acceptable. Breadth-first search determines the shortest path, 〈 node1 , node2 , node4 〉, which requires two hops.
Figure 11.8. Hop counts after performing a breadth-first search on an internet of six nodes
This example presents a function, bfs
(see Examples Example
11.3 and Example 11.4), that
implements breadth-first search. It is used here to determine the
smallest number of hops between nodes in an internet. The function has
graph is a graph, which in
this problem represents the internet;
is the vertex representing the starting point; and
hops is the list of hop ...