Trend Posts
Author
View LUQMAN's profile
Showing posts with label breadth first search method. Show all posts
Showing posts with label breadth first search method. Show all posts
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:
Posts (Atom)