Hello people..! This is a special extension for my discussion on Breadth First Search (BFS) Algorithm. Here, I give you the code for Breadth First Search Algorithm using Queue. The algorithm uses C++ STL. Well, it makes no sense if the algorithm is using STL if the input graph isn’t built by STL..! So, essentially this is the Breadth First Search algorithm designed for my code in Adjacency List using C++ STL.
The way the Queue works is that, we enqueue all the to-be-processed vertices inside the queue and dequeue them one-by-one. The first vertex to be processed is obviously the starting vertex. Then, we “process” the starting vertex, which means that we look at all the vertices adjacent to this vertex, if they are unvisited, we store data about level and parent and then enqueue this adjacent vertices to the queue, because we haven’t seen what’s adjacent to these adjacent vertices of the start vertex.
For example, in the sketch, I used to depict the working of BFS, the graph was drawn 6 times. If you think of those 6 graphs as steps, in those steps –
- Step 1 – The queue would have vertex 1, that is, the starting vertex. Then, we process the vertex, that is, we look at all the adjacent vertices.
- Step 2 – The queue would have the vertices {2, 6, 8}. Note that the vertex 1 is gone. Then we gradually process these vertices.
In the processing, we check if the vertex has already been visited, if not, we do the necessary computation. This technique is a lot easier if you revise the actual working of the BFS and then think in terms of data structures for implementing the tier-to-tier exploration that the BFS displays. Then you’ll understand that a Queue is what you need..! This is the code –
/* * Breadth First Search * Algorithm for Graph * implemented using C++ STL * which using a Queue * * Authored by, * Vamsi Sangam. */ #include <cstdio> #include <vector> #include <list> #include <utility> using namespace std; void breadthFirstSearch(vector<list<int> > adjacencyList, int parent[], int level[], int start) { list<int>::iterator itr; level[start] = 0; /* We start from node 'start' * So, Node 'start' is at level 0 * All immediate neighbours are at * level 1 and so on. */ list<int> VertexQueue; // Queue of vertices to be processed VertexQueue.push_back(start); // Start processing with the // starting vertex while (!VertexQueue.empty()) // While there are vertices to be processed { int newVertex = VertexQueue.front(); // The first vertex in queue itr = adjacencyList[newVertex].begin(); // To explore all the vertices adjacent to it while (itr != adjacencyList[newVertex].end()) { if (level[*itr] == -1) { // This is an unvisited vertex level[*itr] = level[newVertex] + 1; // Set level parent[*itr] = newVertex; // Set parent VertexQueue.push_back(*itr); // Add it to the queue } ++itr; } VertexQueue.pop_front(); // Pop out the processed vertex } } int main() { int vertices, edges, v1, v2, weight; printf("Enter the Number of Vertices -\n"); scanf("%d", &vertices); printf("Enter the Number of Edges -\n"); scanf("%d", &edges); // Adjacency List is a vector of lists. vector< list<int> > adjacencyList(vertices + 1); printf("Enter the Edges V1 -> V2\n"); for (int i = 1; i <= edges; ++i) { scanf("%d%d", &v1, &v2); // Adding Edges adjacencyList[v1].push_back(v2); adjacencyList[v2].push_back(v1); } printf("\nThe Adjacency List-\n"); // Printing Adjacency List for (int i = 1; i < adjacencyList.size(); ++i) { printf("adjacencyList[%d] ", i); list<int>::iterator itr = adjacencyList[i].begin(); while (itr != adjacencyList[i].end()) { printf(" -> %d", *itr); ++itr; } printf("\n"); } int parent[vertices + 1]; // Each element of Parent Array holds the Node value of its parent int level[vertices + 1]; // Each element of Level Array holds the Level value of that node for (int i = 0; i <= vertices; ++i) { //Initialising our arrays parent[i] = 0; level[i] = -1; } printf("\nEnter the Starting Vertex -\n"); scanf("%d", &v1); breadthFirstSearch(adjacencyList, parent, level, v1); //Level Array printf("\nLevel and Parent Arrays -\n"); for (int i = 1; i <= vertices; ++i) { printf("Level of Node %d is %d, Parent is %d\n", i, level[i], parent[i]); } return 0; }
This implementation is faster than the previous implementation where we used a loop. The queue used internally is named VertexQueue, not ‘queue’ or ‘Queue’, so that the code doesn’t get messed up if you use the STL queue, or create a Queue class somewhere. It is a good practice to name your variables with care and in such a way that they can be used in future without breaking code..! 🙂
Feel free to comment if you have any doubts..! Keep practising..! Happy Coding..! 😀
7 thoughts on “Breadth First Search Algorithm using Queue”
I think there is a slight bug in your code…
Instead of :-
while (itr != adjacencyList[newVertex].end()) {
if (level[*itr] == -1) { // This is an unvisited vertex
level[*itr] = lev + 1; // Set level
parent[*itr] = newVertex; // Set parent
VertexQueue.push_back(*itr); // Add it to the queue
}
++itr;
}
VertexQueue.pop_front();
++lev;
We should use :-
while (itr != adjacencyList[newVertex].end()) {
if (level[*itr] == -1) { // This is an unvisited vertex
level[*itr] = level[newVertex] + 1; // Set level
parent[*itr] = newVertex; // Set parent
VertexQueue.push_back(*itr); // Add it to the queue
}
++itr;
}
VertexQueue.pop_front();
Thanks a lot for pointing out the bug..! 🙂 … I’m glad my post could help you…!! 😀
Please correct this bug here:http://theoryofprogramming.azurewebsites.net/2014/12/25/breadth-first-search-algorithm/
in the C++ STL (using a Queue) portion.
It is actually correct there… In the BreadthFirstSearch() method, the loop runs from index 1 → ‘vertices’… Now, as the size of adjacencyList is (vertices + 1), the index of value ‘vertices’ is a valid index… We run the loops in main() method from zero just to initialize the arrays… 🙂
Your post helped me a lot in understanding the topic of BFS.. Thank you very much for such a nice explaination..
Although instead of using a std::list ,you can use std::queue to get lower time.. I experience this in some spoj problems like BITMAP,ELEVTRBL etc..