Trend Posts
Author
View LUQMAN's profile
Monday, July 21, 2014
/*Print all the nodes reachable from a given starting node in a digraph using BFS method.*/
#include<stdio.h>
int i,j,s,a[100][100],q[100],visited[100],u,rear,front,n;
void bfs();
void main()
{
printf("\nEnter the number of nodes:\n");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\nThe entered adjacency matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",a[i][j]);
printf("\n");
}
printf("\nEnter the source vertex:\n");
scanf("%d",&s);
bfs();
for(i=1;i<=n;i++)
{
if(visited[i])
printf("\nNode %d is reachable from source node %d",i,s);
else
printf("\nNode %d is not reachable from source node %d",i,s);
}
}
void bfs()
{
q[rear]=s;
visited[s]=1;
while(front<=rear)
{
u=q[front];
front=front+1;
for(i=1;i<=n;i++)
if(a[u][i] && !visited[i])
{
rear=rear+1;
q[rear]=i;
visited[i]=1;
}
}
}
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment
You are very Important to Us...
STAY TUNE...