## Graph Example: Counting Network Hops

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

*node*. The paths 〈

_{4}*node*,

_{1}*node*,

_{2}*node*〉, 〈

_{4}*node*,

_{1}*node*,

_{3}*node*,

_{2}*node*〉, and 〈

_{4}*node*,

_{1}*node*,

_{3}*node5*,

*node*〉 are all acceptable. Breadth-first search determines the shortest path, 〈

_{4}*node*,

_{1}*node*,

_{2}*node*〉, which requires two hops.

_{4}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;

*is the vertex representing the starting point; and*

`start`

*is the list of hop ...*

`hops`

Get *Mastering Algorithms with C* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.