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 *node _{1}
*, there is more than one way we can reach

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
three arguments: * graph* is a graph, which in
this problem represents the internet;

`start`

`hops`

Start Free Trial

No credit card required