Thread: Breadth-First Search

I know this is probably one of the most fundamental algorithms you will have to learn when you are a CS major but I cannot seem to understand this part. I need to understand the BFS algorithm and this is what I have so far:

Code:

#include <string>
#include <queue>

// aren't typedef's cool?
typedef string Vertex;
typedef queue<Vertex> queue;

void BFS(V1, V2) {
queue Q;
// find the first vertex and push it in
Q.push(V1);

 while(!Q.empty()){
   Vertex t = Q.front();
   // for(every unvisited neighbor of n) --- HOW DO YOU KNOW?
         Q.push(n);
         if(n == V2) Success(Q);
   // }
   Q.pop();
   Failure(Q);
 }
}

My question is how can you process the for loop... a.k.a how do you know which ones are unvisited and which ones are not. Assume that we are given a queue data strucutre and the start vertex and goal vertex.

Typically the program also keeps an array of bools where each index corresponds to a particular vertex. When a vertex is added to the queue then the bool is set to true. So just check to see if it is set to true before adding to the queue and if it is then skip it.

Another idea is to include a bool in the vertex struct.