O'Reilly logo

Mastering Algorithms with C by Kyle Loudon

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 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.

Hop counts after performing a breadth-first search on an internet of six nodes

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 is the vertex representing the starting point; and hops is the list of hop ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required