Graph Traversals
There are a number of approaches used for solving problems on graphs. One of the most important approaches is based on the notion of systematically visiting all the vertices and edge of a graph. The reason for this is that these traversals impose a type of tree structure (or generally a forest) on the graph, and trees are usually much easier to reason about than general graphs.
Breadth-first search
This is one of the simplest methods of graph searching. Choose some vertex arbitrarily as a root. Add all the vertices and edges that are incident in the root. The new vertices added will become the vertices at the level 1 of the BFS tree. Form the set of the added vertices of level 1, find other vertices, such that they are connected by edges at level 1 vertices. Follow the above step until all the vertices are added.
Algorithm:
BFS(G,s) //s is start vertex
{
T = {s}; L =Φ; //an empty queue
Enqueue(L,s);
while (L != Φ )
{
v = dequeue(L);
for each neighbor w to v
if ( w Ï L and w Ï T )
{
enqueue( L,w);
T = T U {w}; //put edge {v,w} also
}
}
}
Example: Use breadth first search to find a BFS tree of the following graph.
Analysis
From the algorithm above all the vertices are put once in the queue and they are accessed. For each accessed vertex from the queue their adjacent vertices are looked for and this can be done in O(n) time(for the worst case the graph is complete). This computation for all the possible vertices that may be in the queue i.e. n, produce complexity of an algorithm as O(n2 ). Also from aggregate analysis we can write the complexity as O(E+V) because inner loop executes E times in total
Post A Comment:
0 comments so far,add yours