Breadth-first search implementation

I learned bfs from my friend and from this blog shafaetsplanet . In shafaetsplanet the algorithm is explained very easily. There the bfs code was implemented using adjacent metrix. Here we will implement it using adj list.

from safaet's blog I will take few lines to show everyone how bfs works

     01. A node can't be visited more than once.
     02. The source node is always level 0.
     03. All nodes directly connected to level 0 or source node are level 1.
     04. All nodes directly connected to level 1 are level 2.And this is how level will keep on rising one by one.
     05. Level of each node is the shortest path distance from its source node

	bfs(source)
	visited[source] = true //let us visit the starting node
	level[source]=0 // level of starting node is 0
	queue <- source // push the starting node in the queue
	while(queue != empty) // while queue not empty run bfs
	u <- queue // u if the front of queue
	for all edges from u to v in G.adjacentEdges(v) do // lets get all the directly connected node of u
	if(visited[v]==false) // if we haven't visited them
	visited[v]= true //visit them
	level[v]=level[u]+1 // 1 + level of its parent
	queue <- v // push the currnt node in the queue

view raw bfs.cpp hosted with ❤ by GitHub

Basic Graph:

                          Bfs using source node A :
     

Bfs using source node F:

	#include<bits/stdc++.h>
	using namespace std;
	vector<int>v[100];
	int cost[100];
	bool visited[100];
	int p[100];
	void bfs(int s){
	queue<int>Q;
	Q.push(s);
	cost[s]=0;
	visited[s]=true;
	while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=0;i<v[u].size();i++){
	int V=v[u][i];
	if(visited[V]==false){
	visited[V]=true;
	cost[V]=cost[u]+1;
	p[V]=u;
	Q.push(V);
	}
	}
	}
	}
	int main(){
	int n,e;
	cin>>n>>e;
	memset(visited,false,sizeof(visited));
	memset(cost,INT_MAX,sizeof(cost));
	for(int i=0;i<e;i++){
	int a,b;
	cin>>a>>b;
	v[a].push_back(b);
	v[b].push_back(a);
	}
	int s;
	cin>>s;
	bfs(s);
	for(int i=1;i<=n;i++)
	cout<<"Level of "<<i<<" is "<<cost[i]<<"\n";
	cout<<"\npath: ";
	int i=5;
	while(i!=0){
	cout<<i<<" ";
	i=p[i];
	}
	return 0;
	}

view raw Bfs implementation.cpp hosted with ❤ by GitHub