Me, you and everyone is constantly searching for something: a new relationship, knowledge, music, food or just for a new experience. If we start to think about it, searching slowly becomes our second nature and takes up a good portion of our life, becoming a central motive for us. In the world of graphs, searching is just as important. Today we are going to examine the breadth-first search algorithm (BFS).
Contributed by Gabor Bernat Rating: / 4 May 11, 2009
This article is part of a series I am dedicating to graphs, so if you missed any of the previous ones you may want to read them. You can find them by clicking on my name or just start up a search on the site.
If you have just heard the word "graph" and know little about the field of graphs, please make the effort to read the introductory article entitled An Insight into the Graphs.
For now, let us focus on the search algorithms. Mainly there exist two kinds of search algorithms: the breadth-first search and the depth-first search. All the rest are variations on these. With small modifications to these two, you can solve a wide range of problems, as I will show you later on.
Searching a graph means starting from a point and visiting all of the vertexes within a graph through the edges that exist between them. The depth-first search will be the subject of a future article, so for now let us focus on the breadth-first search.
The theory behind it is simple. It can be summed up in the following sentence: step in at the root item (from the vertex we start to visit/search the graph), drop by all of its neighbors that have not been visited yet, and then continue the algorithm on the neighbors until all of the vertexes have been touched.
Now a few of you could already implement the algorithm/search by turning it into code just from the earlier description -- however, most of you will need a more detailed explanation. The idea is to start from a root vertex and visit all of its neighbors (its children), the neighbors of those (the children’s children) and so on. From this point of view, the breadth-first search is like a tree of generations.
It will visit first the ancients, then the offspring of those, and follow on with the descendants of those, and so forth. Therefore, we can already see that this could be an appropriate way to tell the distance of a vertex from the root in number of edges. All we need to do is store the current level and increase it as we go deeper and deeper into the tree.
However, before we venture on, let us be clear as to how we are going to make this search happen. The vertexes that we will need to visit are added at the end of this virtual list, and we will follow on with the first item within this list. This looks like a FIFO (First In First Out) data management system, which is synonym to using a queue.
In the end, the algorithm is translated to the following pseudo code: insert root item into the queue. While we have items inside the queue, do: visit the neighbors of the first item in the queue. If the neighbor is not yet visited, add it to the end of the queue. When all of the neighbors are visited, remove the item from the queue.
The order in which we added items to the queue will build up the breadth-first search. To simulate in a more practice way the state of vertexes, we are going to assign each one a color. White means that we have not visited the vertex, gray that we are currently visiting the node (currently in the queue), and black will be the color of the vertexes for which we have visited all of their neighbors, and they are out of the queue.
Under these circumstances, we can restate the search as stepping ahead from the vertex that turned gray earliest and trying to drop by each still-white node. As we are going forward only on the edges that are still white, it is logical that our search will determine a tree. Moreover, we can store it all inside an array. This array will let us determine the shortest path from the root item, if we are willing to iterate back on the array until we reach the root whose origin is the zero vertex.
According to the breadth-first search, we can categorize the edges. They are four kinds of edges: edges that will became part of the tree, edges pointing ahead, edges pointing back and cross-pointing edges. Their names already tell you what they try to describe; however, let us see how we can learn what they are during our search.
Each edge will be categorized in one of these sections, and this will happen the first time the search observes the existence of the edge. So that we can use the information later on, I decided to add another property during this algorithm to our adjacent list: the type of the edge. I also made a few definitions, as you will see below:
#define TREE_EDGE 1
#define BACK_EDGE 2
#define CROSS_EDGE 3
#define AHEAD_EDGE 4
struct ListIt
{
int value;
int type;
ListIt* p_next;
};
A tree edge means that the edge will become a part of the search tree (we traveled ahead on it inside the graph or found another vertex through it). Back-pointing edges are the ones that will point to a node already black (it points to an earlier generation vertex). Cross-pointing edges are gray, and their distance from the root is less than the distance from the root of the currently-visited node.
Ahead-pointing edges should be gray, and the distance from the root is greater than the currently-visited node; however, inside a breadth-first search, this kind of edge does not exist, otherwise we would use them to visit that node.
As mentioned on the previous page, we can find the shortest route by the number of edges from the root to specific vertex by re-iterating, and eventually by counting the number of iterations, we can also tell the distance. Now for didactic reasons we will store this information in a distance array that will point the level where we are in the graph.
Everything I've tried to explain up to this point, translated to a C code snippet, will look as follows:
void BFS(int rootVertex)
{
int u;
for (int i = 1 ; i <= n ; ++i)
{
ancient[i] = 0;
color[i] = WHITE;
distance[i] = INT_MAX;
}
// insert root item
ancient[rootVertex] = 0;
color[rootVertex] = GRAY;
distance[rootVertex] = 0;
vertex_queue = new ListIt;
vertex_queue->p_next = NULL;
vertex_queue->value = rootVertex;
pListIt p, qE;
p = NULL;
qE = vertex_queue;
while(vertex_queue)
{
// get first item
u = vertex_queue->value;
printf(" %d ", u);
for (p = v[u]; p != NULL; p = p -> p_next)
if( !p->type)
if (color[p -> value] == WHITE)
{
// add item to the queue
color[p->value] = GRAY; // gray nod
distance[p->value] = distance[u] +1;
ancient[p->value] = u;
p->type = TREE_EDGE; // this is a tree edge
qE->p_next = new ListIt;
qE = qE->p_next;
qE->p_next = NULL;
qE->value = p->value;
}
else // so no tree edge something else
if (color[p->value] == GRAY) {
p->type = BACK_EDGE;
}
else
if (color[p->value] == BLACK && distance[p->value] <= distance[u]) {
This is one way to use the breadth-first search. This tries to show that with just a little adjustment to our search, we can solve problems that at first may seem quite difficult. The issue is as follows: let there be a graph that has a source vertex (these have only out-going edges) and a drain vertex (only in-coming edges). Determine the vertexes that are inevitable; in other words, all the roads from the source to the drain pass through them.
We need to observe that with a breadth-first search, as we step further from a gray vertex that has all of its incoming edges black, the nodes that at a point remain alone in the queue will be the inevitable points. This is a key point -- for example, in the road system of a country -- and we need to take special care of these vertexes to illustrate a practical usage of the algorithm.
To further simplify the count of the incoming edges, we are going to execute the search at the inverse of the graph (so we invert the direction of all edges). This way we can check the outgoing edges, which is an easy task with the adjacent list. In addition, here is the modified search code snippet:
void BFS_inevitable(int root)
{
int u;
for (int i =1 ; i <= n ; ++i)
if (i != root)
{
color[i] = WHITE;
}
color[root] = GRAY;
vertex_queue = new ListIt;
vertex_queue->p_next = NULL;
vertex_queue->value = root;
pListIt p, qE, q;
q = NULL;
p = NULL;
qE = vertex_queue;
while(vertex_queue)
{
if (!vertex_queue->p_next) // only one item
{
printf(" %d ", vertex_queue->value);
}
// we get the point for which all neighbors are
//already visited
u = 0; // invalid point
for (p = vertex_queue; p != NULL && !u;
p = p -> p_next) // until we find a valid point
{
// check if all the edges towards it point is touched
for (q = inverseList[p->value]; q != NULL;
q = q -> p_next) // until we find a valid point
if( !color[q->value])
break;
if(!q)
u = p->value;
}
for (p = v[u]; p != NULL; p = p -> p_next)
if (!color[p -> value])
{
//add it to the queue
color[p->value] = GRAY;
qE->p_next = new ListIt;
qE = qE->p_next;
qE->p_next = NULL;
qE->value = p->value;
}
// remove the item from the queue
// mark as black
p = vertex_queue;
color[p->value] = BLACK;
vertex_queue = vertex_queue->p_next;
delete p;
}
}
You may download the C file for everything I presented here today and observe the full program, where you may enter new graphs to perform tests and see the code in action.
This will be all for today, so I would like to thank you for reading all the way to the end, and ask you to rate my article and comment it here on the blog if you feel like you want to say something about it. As an alternative, you may also join our friendly forum over at DevShed or DevHardware and act similarly there. I will be back next time with the depth-first search, consequently until then Live With Passion!
Code Examples 
/ 4 
Depth-First Search in Graphs
