Breadth First Traversal-Algorithm

#include <stdio.h>
#define size 100

char visited_array[100];
int VS=-1, f = 0, r = 0, graph[50][50]={0}, no_of_vertex;
char q[size+1], vertex[26];

void visit(char ch)
{
VS++;
visited_array[VS]=ch;
}
int is_visit(char ch)
{
int i;
for(i=0; i<=VS; i++)
{
if(ch==visited_array[i])
{
return 1;
}
}
return 0;
}

void show_visited_array()
{
int i;
for(i=0; i<=VS; i++)
printf(“%c “, visited_array[i]);
}
void enqueue(char ch)
{
int s = (r+1) % (size+1);
if(f == s)
return;
else
{
r = s;
q[r] = ch;
}

}
char dequeue()
{
f = (f+1) % (size+1);
char ch = q[f];
q[f] = ‘\0’;
return ch;
}
void find_adjacency(char ch)
{
int i,j;
for(i=0; i<no_of_vertex; ++i)
{
if(ch==vertex[i])
{
for(j=0; j<no_of_vertex; ++j)
{
if(graph[i][j]==1)
{
if(is_visit(vertex[j]) == 0)
{
enqueue(vertex[j]);
}
}
}
}
}
}
void BFS()
{
char ch;
enqueue(vertex[3]);
while(f != r){
ch = dequeue();
find_adjacency(ch);
if(is_visit(ch) == 0)
visit(ch);
}
}
void createGraph()
{
int i, j;
for(i = 0 ; i < 26 ; i++)
vertex[i] = i+65;

printf(“How many vertex: “);
scanf(“%d”, &no_of_vertex);
for(i = 0 ; i < no_of_vertex ; i++)
{
for(j = i+1 ; j < no_of_vertex ; j++)
{
printf(“%c-%c: “, vertex[i], vertex[j]);
scanf(“%d”, &graph[i][j]);
if(graph[i][j] == 1)
graph[j][i] = 1;

}
}
}

int main()
{
createGraph();
BFS();
show_visited_array();

return 0;
}

If you like this post please must share with other people
Share on Facebook
Facebook
0Tweet about this on Twitter
Twitter
Pin on Pinterest
Pinterest
0Share on LinkedIn
Linkedin

Leave a Reply

Your email address will not be published. Required fields are marked *