BASIC CODE FORM OF BFS(BREADTH FIRST SEARCH)

CODE:

//JUST FOLLOW THE COMMENTS BESIDE THE CODE, YOU CAN EASILY RELATE CODE AND THE ALGORITHM.

#include <bits/stdc++.h>
using namespace std;
vector <int> edge[10000];//2d array that will contain the vertex and edges in coordinate                                        //form
int level[10000]; //the distance from the source, the position value i.e level[i],’i’ in here is                             //vertex level[i] will contain the distance from the source
int visited[10000];
int parent[10000];
int bfs(int source)
{
cout<<“Source: “<<source<<endl;//just printing out the source
queue <int> q;//taking a queue that will temporarily contain all the vertices
q.push(source);//push source into the queue
visited = 1;//source is the first move so it is made visited,it is similar to the //coloring it to grey
level = 0;//Distance from source to source is zero
while(!q.empty())//taking while loop that will run till the queue is empty
{
int u = q.front();//taking the first element of the queue in the integer u
for(int i = 0;i<edge[u].size();i++)//for loop will run till the size of row i
{
int v = edge[u][i];//v = adjacent vertex of the u
if(!visited[v])
{
visited[v] = 1;//making v as visited
level[v] = level[u] + 1;//level is greater than that of the parents
parent[v] = u;//parent of v is u
q.push(v);//the adjacent vertex of u is pushed into the queue
}
}
q.pop();//source is poped in the first move of while loop gradually others are done
}
}
int main()
{
int n,m;//n = vertex and m = number of edges
int a,b;
cin>>n>>m;
//now we will take input of vertex using a for loop
//vertex will basically be converted into edges by
//taking the input in the vector just reversing the
//positions
for(int i = 0;i<m;i++)
{
cin>>a>>b;
edge[a].push_back(b);
edge[b].push_back(a);
}
int source;
cin>>source;
memset(visited,0,sizeof(visited));//making the vertex as unvisited(white)
bfs(source);//bfs is called     using a source. U can choose anyone as source
cout<<“DISTANCES:”<<endl;
for(int i = 1;i<=n;i++)
{
cout<<“DISTANCE FROM SOURCE TO         “<<i<<“:         “<<level[i]<<endl;
}
cout<<“PARENTS:”<<endl;
for(int i = 2;i<=n;i++)
{
cout<<“PARENT OF         “<<i<<“: “<<parent[i]<<endl;
}

}

LIGHT OJ – 1012 SOLUTION

PROBLEM LINK:

LIGHT OJ-1012 (GUILTY PRINCE)

SOLUTION:

//To learn about pair<int,int> , please go to pair c++
//To learn about memset(), please go to memset()

#include <bits/stdc++.h>
#define _clear(a) memset(a,0,sizeof(a))
#define pii pair<int,int>
using namespace std;
int main()
{
int t;
cin>>t;
for(int n = 0; n<t; n++)
{
int col,row,source_x,source_y;
cin>>col>>row;
char arr[row][col];
char a;
for(int i = 0; i<row; i++) {
for(int j = 0; j<col; j++) {
cin>>a;
if(a==’@’) {
source_x = i;
source_y = j;
}
arr[i][j] = a;
}
}
bool visited[row][col];
int DX[] = {-1,1,0,0};
int DY[] = {0,0,-1,1};
int counter = 1;
queue <pii>q;
_clear(visited);
visited[source_x][source_y] = true;
q.push(pii(source_x,source_y));
while(!q.empty()) {
pii top = q.front();
q.pop();

    for(int k = 0; k<4; k++) {
int f = top.first + DX[k];
int s = top.second + DY[k];
if(arr[f][s] == ‘#’)continue;
else if((f>=0&&f<row)&&  (s>=0&&s<col)&&(!visited[f][s])&&arr[f][s] == ‘.’) {
visited[f][s] = true;
counter++;
q.push(pii(f,s));
}
}

}
cout<<“Case “<<n+1<<“: “<< counter<<endl;
}
}

LIGHT OJ 1009 SOLUTION

PROBLEM LINK:

LIGHTOJ 1009 BACK TO UNDERWORLD

SOLUTION:

#include <bits/stdc++.h>
#define _clear(a) memset(a,0,sizeof(a))
using namespace std;
vector <int> edge[20004];
int level[20004];
bool visited[20004],used[20004];
int parent[20004];
int T,m,a,b,cnt,source;
int vam[20004];
int lyn[20004];
int bfs() {
queue <int> q;
visited = true;
int cnt1=0,cnt2=0,u,v;
_clear(vam);
_clear(lyn);
cnt = 0;
q.push(source);
vam = 1;
visited=1;
while(!q.empty()) {
u = q.front();
q.pop();
for(int i = 0; i<edge[u].size(); i++) {
v = edge[u][i];
if(!visited[v]) {
if(!vam[u])
vam[v] = 1;
if(!lyn[u])
lyn[v] = 1;
visited[v]=1;
q.push(v);
}
}
}
for(int j = 0; j<20004; j++) {
if(vam[j]==1)
cnt1++;

}
for(int j = 0; j<20004; j++) {
if(lyn[j]==1)
cnt2++;
}
if(cnt1>cnt2) {
cnt = cnt1;
return cnt;
} else {
cnt = cnt2;
return cnt;
}

}
int main() {

cin>>T;
for(int i = 1; i<=T; i++) {
cin>>m;
memset(used,0,sizeof(used));
for(int i=0;i<20004;i++)edge[i].clear();
_clear(visited);
for(int j = 0; j<m; j++) {
cin>>a>>b;
edge[a].push_back(b);
edge[b].push_back(a);
used[a]=used[b]=1;
}
int ans=0;
for(int j=0; j<20004; j++) {
if(used[j] && !visited[j]){
source=j;
bfs();
ans+=cnt;
}
}
cout<<“Case “<<i<<“: “<<ans<<“\n”;
}

}

UVA – 439 SOLUTION

PROBLEM LINK:

UVA-439 KNIGHT MOVES

BFS RELATED PROBLEM

SOLUTION:

//PROGRAMMERS ARE REQUESTED NOT TO COPY AND PASTE THE CODE SOMEWHERE, //THERE BY YOUR EFFICIENCY WILL DECREASE. PLEASE TRY TO UNDERSTAND THE CODE //AND IF YOU FEEL ANY DIFFICULTY PLEASE COMMENT BELOW, WE WILL TRY TO HELP //FURTHER

#include <bits/stdc++.h>
#define FOO pair<int,int>
#define clear(a) memset(a,0,sizeof(a))

using namespace std;
int DX[]={1, -1, 1, -1, 2, 2, -2, -2};
int DY[]={2, 2, -2, -2, 1, -1, 1, -1};
bool visited[10][10];
int level[10][10];
string str1,str2;
void bfs(int a,int b,int c,int d)
{
queue<FOO> q;
clear(visited);
q.push(FOO(a,b));
level[a][b] = 0;
visited[a][b] = true;
while(!q.empty())
{
FOO top = q.front();
q.pop();
if(top.first == c && top.second == d)
{
cout<<“To get from “<<str1<<” to “<<str2<<” takes “<<level[top.first]                                      [top.second]<<” knight moves.”<<endl;
return;
}
for(int i = 0;i<8;i++)
{
int m = top.first + DX[i];
int n = top.second + DY[i];
if((m>=1&&m<=8)&&(n>=1&&n<=8)&&!visited[m][n])
{
visited[m][n] = true;
level[m][n] = level[top.first][top.second] + 1;
q.push(FOO(m,n));
}}
}}
int main()
{

while(cin>>str1>>str2)
{
int x1,y1,x2,y2;
x1 = str1[0] – 96;
y1 = str1[1] – 48;
x2 = str2[0] – 96;
y2 = str2[1] – 48;
bfs(x1,y1,x2,y2);
}
}

BFS(Breadth First Search)

This topic contains the elaboration and working procedure of BFS. The topic contains the graph related terminologies. If you want to refresh you knowledge regarding graph please visit introduction to graph

In graph theory, BFS is a well-known algorithm. Using BFS the problems of unweighted edge graph is solved. Distance from source vertex to every other vertex can be calculated with BFS. The time complexity is O(V+E) where V represents number of vertices and E represents the number of edges.

ALGORITHM:

EXPLANATION:
1. From line 1 to 4
    In line 2 inside the loop, each vertex of the graph V except source s, firstly color it as white to mark it as  unvisited. In line 3, the distance of every vertex is made infinity from source. In line 4, the parent of all vertex except source is made null.
2. From line 5 to 9
In line 5, color of source is made grey i.e source is visited. In line 6, the distance of source from source is made 0; and in 7, the parent of source is made null. Because, source can never have a parent. If we transform graph into tree, source will be the root. In line 8, a queue is defined and in 9, source is entered into the queue.
3.  From line 10 to 18
In line 10, the loop will continue till it is empty. In line 11, variable u accepts the first element of the queue. Now for the for loop in line 12, it will continue for all vertices v which are adjacent to u. In line 13, if the vertex color is white, i.e if the vertex is not visited then in line 14, the color is changed to grey to mark it visited. In line 15,
                distance of vertex v from source = (distance from source of u) +1
In line 16, parent of v = u. In line 17, v is inserted into the queue. For-loop finishes here.
Finally, the color of u is made black to mark it that, vertex is fully discovered.