• Choose a category
• All
• Classic-Fiction

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 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 counts that is returned. The function modifies graph, so a copy should be made before calling the function, if necessary. Also, vertices returned in hops are pointers to the actual vertices from graph, so the caller must ensure that the storage in graph remains valid as long as hops is being accessed. Each vertex in graph is a BfsVertex structure (see Example 11.3), which has three members: data is a pointer to the data associated with the vertex, color maintains the color of the vertex during the search, and hops maintains the number of hops to the vertex from the start node. The match function for graph, which is set by the caller when initializing the graph with graph_init, should compare only the data members of BfsVertex structures.

The bfs function performs breadth-first search as described earlier in this chapter. To keep track of the minimum number of hops to each vertex, we set the hop count of each vertex to the hop count of the vertex to which it is adjacent plus 1. We do this for each vertex as we discover it, and color it gray. Colors and hop counts for each vertex are maintained by the BfsVertex structures in the list of adjacency-list structures. At the end, we load hops with all vertices whose hop counts are not -1. These are the vertices that were reachable from the start node.

The runtime complexity of bfs is O (V + E ), where V is the number of vertices in the graph and E is the number of edges. This is because initializing the colors of the vertices and ensuring that the start node exists both run in O (V ) time, the loop in which the breadth-first search is performed in O (V + E ) time, and loading the list of hop counts is O (V ).

Example 11.3. Header for Breadth-First Search

/*****************************************************************************

* *

* --------------------------------- bfs.h -------------------------------- *

* *

*****************************************************************************/

#ifndef BFS_H

#define BFS_H

#include "graph.h"

#include "list.h"

/*****************************************************************************

* *

* Define a structure for vertices in a breadth-first search. *

* *

*****************************************************************************/

typedef struct BfsVertex_ {

void *data;

VertexColor color;

int hops;

} BfsVertex;

/*****************************************************************************

* *

* --------------------------- Public Interface --------------------------- *

* *

*****************************************************************************/

int bfs(Graph *graph, BfsVertex *start, List *hops);

#endif

Example 11.4. Implementation of a Function for Breadth-First Search

/*****************************************************************************

* *

* -------------------------------- bfs.c --------------------------------- *

* *

*****************************************************************************/

#include

#include "bfs.h"

#include "graph.h"

#include "list.h"

#include "queue.h"

/*****************************************************************************