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 algorithm using the 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 Edge to the Directed Graph
		adjacencyList[v1].push_back(v2);
	}

	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..! Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 … Keep practising..! Happy Coding..! 😀

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

      • 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… 😉

        Like

  1. 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

    Like

    • 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..! 😛

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s