BREADTH FIRST SEARCH (BFS)

If you have any queries please leave a message here
Your Message
×


Breadth First Search (BFS) is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.

In BFS the vertices have three adjacent different statuses during the process of traversal or searching, the status being : unknown, discovered and visited.


EXAMPLE

In the figure given below, we can see the graph given initially, in which only source S is discovered.


Figure 1 : Initial Input Graph


Figure 2 : After we visit S


Figure 3 : After we visit A


Figure 4 : After we visit B


Figure 5 : After we visit C


Figure 6 : After we visit D


Figure 7 : After we visit E


Figure 8 : After we visit F


Figure 9 : After we visit G




Breadth First Search Programming in C

#include<stdio.h>
#include<stdlib.h>

//Global Function Declaration
void BFS();

// Global Variable Declaration
int number_of_vertices, number_of_edges, discover_top=-1, visited_top=-1, v, i, j, k;
int edges[25][2], discovered[25], visited[25];

// main( ) function begins
void main()
{
// Input number of vertices present in the graph
printf("\n Enter number of vertices : ");
scanf("%d",&number_of_vertices);
// Input number of edges present in the graph
printf("\n Enter number of edges : ");
scanf("%d",&number_of_edges);
for(i=0; i<number_of_edges; i++)
{
printf("Enter an edge (u,v)...");
scanf("%d%d",&edges[i][0],&edges[i][1]);
}
// Input the vertex from where searching process is start
printf("\n Enter the start vertex...");
scanf("%d",&v);
BFS();
printf("\n\n\n Final Visited List : ");
for(i=0; i<=visited_top; i++)
printf("\t%d",visited[i]);
}

// BFS( ) function begins
void BFS()
{
int temp[25];
int pos,z;
discover_top++;
discovered[discover_top]=v;
printf("\n\n\n Discovered List : \n");
printf("\t%d",v);
for(z=1; z<=number_of_vertices; z++)
{
// Print Discover List
printf("\n\n Discover List : ");
for(i=0;i<=discover_top;i++)
{
printf("\t%d",discovered[i]);
}

// Print Visited List
printf("\n Visited List : ");
for(i=0;i<=visited_top;i++)
{
printf("\t%d",visited[i]);
}

// Find the vertices which connected with the discover vertex
pos=0;
for(i=0; i<number_of_edges; i++)
{
if(edges[i][0] == discovered[0])
{
temp[pos]=edges[i][1];
pos++;
}
}

visited_top++;
visited[visited_top]=discovered[0];
for(i=1;i<=discover_top;i++)
{
discovered[i-1]=discovered[i];
}
discover_top--;

// Check whether the vertices which connected with the new discover vertex are already discover or not
for(i=0; i<=discover_top; i++)
{
for(j=0;j<pos;j++)
{
if(discovered[i] == temp[j])
{
for(k=j; k<pos-1; k++)
temp[k]=temp[k+1];
pos--;
}
}
}

// Check whether the vertices which connected with the new discover vertex are already visited or not
for(i=0; i<=visited_top; i++)
{
for(j=0;j<pos;j++)
{
if(visited[i] == temp[j])
{
for(k=j; k<pos-1; k++)
temp[k]=temp[k+1];
pos--;
}
}
}

// pos > 0 means that the vertices present in the temp[ ] array are not discovered or visited
if(pos > 0)
{
// Sort the temp[ ] array using Bubble Sort
for(i=1;i<pos;i++)
{
for(j=1;j<=pos-i;j++)
{
if(temp[j-1] > temp[j])
{
v=temp[j-1];
temp[j-1]=temp[j];
temp[j]=v;
}
}
}
// Put all the vertices present in the temp[ ] array into discovered[ ] array
for(i=0;i<pos;i++)
{
discover_top++;
discovered[discover_top]=temp[i];
}
}
}
}


ABOUT US

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.


MORE TOPIC


Windows Command

UNIX Command

IGNOU Assignment Solution

IGNOU Question Paper Solution

Solutions of Different Questions


WHAT WE DO


Website Devlopment

Training

Home Learning

Provide BCA, MCA Projects

Provide Assignment & Question Paper Solution


CONTACT US


Follow Us