Breadth-First Search in Graphs - Classification and the Code Snippet
(Page 3 of 4 )
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]) {
p->type = CROSS_EDGE;
}
// remove item from queue
p = vertex_queue;
color[p->value] = BLACK;
vertex_queue = vertex_queue->p_next;
delete p;
}
}
Next: Inevitable Vertexes >>
More Code Examples Articles
More By Gabor Bernat
