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 –

1. 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.
2. 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..! 😀