Data Structure Program to Implement BFS

Implement BFS for an undirected or digraph.

/* Breadth First Search Traversal - BFS - Undirected Graph - Non-Recursive */

#include
#include

#define MAXVERTS 10 /* maximum vertices in the graph <= 10 */

void main(void)
{
void bfs(int [][MAXVERTS], int [], int); /* prototype declaration for */
/* breadth first search traversal function */
int adj_mat[MAXVERTS][MAXVERTS]; /* array to hold the adjecancy matrix */
int visited[MAXVERTS]; /* array to hold if node is already visited */
int n; /* stores actual number of vertices present in graph */
int m; /* stores total no of edges in the undirected graph */
int start; /* stores the vertex at which the BFS begins */
int i,j,k; /* loop variables */
input : /* label name for transfer of control through goto */
clrscr();
printf("BFS Traversal - Undirected Graphs - Non-Recursive\n");
printf("--- --------- - ---------- ------ - -------------\n\n");
printf("Enter number of vertices in the undirected graph [0 to exit] - ");
flushall();
scanf("%d", &n);
if (n < 0 || n > MAXVERTS) /* check for valid input */
{
printf("Maximum vertices in the undirected graph = %d\n",MAXVERTS);
printf("Error - input value is out of range...[0 to 10]");
getch();
goto input;
}
if (n == 0)
{
goto end;
}
for (i=0; i {
visited[i] = 0; /* initialize visited array to zeroes or false */
for (j=0; j {
adj_mat[i][j] = 0; /* initialize adjecancy matrix */
}
}
printf("Enter total number of edges in the undirected graph - ");
flushall();
scanf("%d", &m);
for (k=1; k<=m; k++)
{ /* This loop asks details of the edges in the graph */
printf("\nEdge no = %2d is between -\n vertex number = ", k);
flushall();
scanf("%d",&i);
printf("and vertex number = ");
flushall();
scanf("%d",&j);
if (i<1 || i>n || j<1 || j>n)
{
printf("Error - check details of this edge\n");
printf("wrong vertex numbers...");
getch();
goto input;
}
adj_mat[i-1][j-1]=1; /* sets the proper pair of elements in the */
adj_mat[j-1][i-1]=1; /* adjecancy boolean matrix to a value 1 */
}
printf("\n\nEnter vertex no at which to start BFS [%d to %d] - ", 1, n);
flushall();
scanf("%d",&start);
if (start < 1 || start>n)
{
printf("Error - input value is out of range...[0 to 10]");
getch();
goto input;
}
clrscr();
printf("Adjecancy Matrix - \n", n);
printf("--------- ------ - \n\n\n");
for (i=0; i {
for (j=0; j {
printf(" %d ",adj_mat[i][j]); /* displays the contents of the */
} /* adjencancy boolean matrix */
printf("\n\n");
}
printf("\n\n\nBFS Traversal starting at vertex no %d -\n",start);
printf("--- --------- -------- -- ------ -- - -\n\n\n");
bfs(adj_mat,visited,(start-1)); /* invoke the function for performing */
/* BFS traversal starting at a particular vertex */
printf("\n\n");
getch();
goto input;
end :
printf("\n\n\bEnd of Program");
getch();
}

/* Non-Recursive Function definition for BFS traversal of graph */
/* starting at a particular vertex */
void bfs(int adj_mat[][MAXVERTS], int visited[], int start)
{
int i; /* local loop variable */
int queue[MAXVERTS] = {0};
/* decalre an array to store the simple linear queue elements */
int first = -1; /* control variable to store the position of */
/* first element of the simple linear queue */
int last = -1; /* control variable to store the position of */
/* last element of the simple linear queue */
queue[++last] = start; /* add the start node to the queue */
visited[start] = 1; /* set the visited flag of the start node to 1 */
printf("%d ",(start+1)); /* display this vertex as visited */
while (first != last) /* check for queue empty condition */
{
start = queue[++first]; /* read the first element of the simple */
/* linear queue for further processing */
for (i=0; i {
if (adj_mat[start][i] && visited[i] == 0) /* check for adjecancy and */
{ /* not visited status of the ith vertex */
queue[++last] = i; /* Add the vertex just visited onto the stack */
visited[i] = 1; /* set the visited flag to 1 */
printf("%d ",(i+1)); /* display this vertex as visited */
} /* End of if statement with adj_mat */
} /* End of for loop with i as control vairaible */
} /* End of while loop with first */
} /* End of non-recursive function for BFS */