Breadth First Search Algorithm using C++ STL

Hello people..! This is a special extension for my discussion on Breadth First Search (BFS) Algorithm. Here, I give you the code for the Breadth First Search Algorithm using 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. A couple of features of this code are –

  • The basic input differs from the code in our initial discussion.
  • The flag variables is of the type bool.
/*
 * Breadth First Search
 * Algorithm for Graph
 * implemented using C++ STL
 *
 * 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[])
{
	list<int>::iterator itr;
	int i, par, lev;
	bool flag = true;
	//'lev' represents the level to be assigned
	//'par' represents the parent to be assigned
	//'flag' indicates if graph is unexplored or not

	lev = 0;
	level[1] = lev;
	/* We start from node 1
	 * So, Node 1 is at level 0
	 * All immediate neighbours are at
	 * level 1 and so on.
	 */

	while (flag) {
		flag = false;
		for (i = 1; i < adjacencyList.size(); ++i) {
			if (level[i] == lev) {
				flag = true;
				itr = adjacencyList[i].begin();
				par = i;

				while (itr != adjacencyList[i].end()) {
					if (level[*itr] != -1) {
						++itr;
						continue;
					}

					level[*itr] = lev + 1;
					parent[*itr] = par;
					++itr;
				}
			}
		}

		++lev;
	}
}

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;
	}

	breadthFirstSearch(adjacencyList, parent, level);

	//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;
}

I could have just simply put the algorithm procedure.. But the reason I put the whole code, is that the graph I am using is an unweighted graph… Obviously, BFS needs an unweighted graph..! So, this graph is a little different from my C++ STL implementation of Adjacency List. The difference, is that, each edge is simply an integer corresponding to the vertex ‘V’ in an edge U → V… It is not a pair… You should’ve guessed that by now.. But, it doesn’t harm to mention… 😛

Feel free to comment if you have any doubts..! Keep practising..! Happy Coding..! 😀

17 thoughts on “Breadth First Search Algorithm using C++ STL

  1. First of all thanks for such detailed explaination. I now have understood BFS more clearly . I just did not get one thing in this code…
    Why does the for loop in the main function runs till less than adjacentList.size() while in the breathFirstSearch function it runs till less than ‘equal to’ adjacentList.size()?

    1. The loop in the breadthFirstSearch function must run till less than adjacencyList.size()… It was a mistake which doesn’t cause much trouble in C.. But it would be an exception in Java… I have corrected the code… Thanks for pointing it out… 🙂

    1. I just wanted to keep it simple so that everyone can understand it easily… Yes, it would make a lot of sense to use const reference if the graph is big, so that we can avoid copying… Though modern compilers generally detect this opportunity of optimization, I prefer to do that explicitly… So, you are right, but here, I wanted to keep things simple… 🙂

        1. Nice question..! 🙂 … I took a little time to think which one would be better… A queue or a list… By default the underlying container of a queue is a dequeue… Personally, I don’t fancy the way a dequeue grows (the internal memory allocation)… It is chunks of contiguous data… But we are not interested in the contiguous memory allocation, or benefits of random access… So, the dequeue doesn’t offer us anything we are interested in… On the other hand a list grows decently, its a doubly linked list… In C too, traditionally we implement queues using doubly linked lists… So, the memory allocation thing made me choose a list.
          On the other hand, we can specify the underlying container of queue to be a list while instantiation… But I didn’t do that either… Call me lazy, but I didn’t do that because I didn’t want to include another header file when the job can be done decently with the resources I already have… 🙂
          You can always use the STL Queue… We can’t know which is the best, unless we are given really massive amounts of data… 😉

  2. I stare you blog almost the whole day 🙂 .Btw along with segment tree request(I hope you remember that).If you could make a post on cycle detection using DFS 🙂 That is another hot topic for every programmer 🙂 Just a suggestion and request you can say.And one more thing i would like to know is that have you prepared any list of topics according to which you make your posts ? If yes please let us know

    1. I’m really glad you find my blog useful..! I do remember your request.. 😉 … Yes, cycle detection is an interesting topic.. I just wrote a short note in my post regarding DFS… It would be nice to have the code too..! Thanks for the suggestion.. 🙂
      As for the list of topics… Nothing specific like that.. 😛 … I do have a bunch of topics in mind… But the real challenge is to balance my day-to-day curriculum with the blog activities… So it all comes down to priorities… What’s easy and effective for me in the given situation.. 🙂
      Adjacency List Data Structure, BFS and DFS have been the heart of the traffic to my blog… So, I am boosting it by putting more implementations. Then I’m thinking of starting the Object Oriented Section of my Java Tutorials… The post is half ready… Then I guess your request for Segment Tree problems is on the queue.. 🙂 … After that, I’ll stop posting for a while and go through all my codes once again… Because every now-and-then when people ask doubts and I go through my codes, I find a few statements which can be removed to cut-short the code… So I’ll be working on optimizing the codes for a while…
      Currently that’s what I have in mind… 😀 …. Let’s see what I actually end up doing..! 😛

Leave a Reply