Welcome Message

Hi, welcome to my website. This is a place where you can get all the questions, puzzles, algorithms asked in interviews and their solutions. Feel free to contact me if you have any queries / suggestions and please leave your valuable comments.. Thanks for visiting -Pragya.

Showing posts with label BFS. Show all posts
Showing posts with label BFS. Show all posts

January 3, 2010

BFS prog for the Graph in the last blog

public void bfs() // breadth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
displayVertex(0); // display it
theQueue.insert(0); // insert at tail
int v2;
while( !theQueue.isEmpty() ) // until queue empty,
{
int v1 = theQueue.remove(); // remove vertex at head
// until it has no unvisited neighbors
while( (v2=getAdjUnvisitedVertex(v1)) != -1 )
{ // get one,
vertexList[v2].wasVisited = true; // mark it
displayVertex(v2); // display it
theQueue.insert(v2); // insert it
} // end while
} // end while(queue not empty)
// queue is empty, so we're done
for(int j=0; j< totalVertices; j++) // reset flags
vertexList[j].wasVisited = false;
} // end bfs()