Breadth-First Search in Graphs - Inevitable Vertexes
(Page 4 of 4 )
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!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
