Lab program 7a: Print all the nodes reachable from a given starting node in a digraph using BFS method.

Description:

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root(or some arbitrary node of a graph, sometimes referred to as a 'search key’) and explores the neighbor nodes first, before moving to the next level neighbors..

Algorithm

1. Start from node s.
2. Visit all neighbors of node s.
3. Then visit all of their neighbors, if not already visited
4. Continue until all nodes visited

 Solution:

#include<stdio.h>

#define size 20

#define true 1

#define false 0

int queue[size],visit[20],rear=-1,front=0;

int n,s,adj[20][20],flag=0;

void insertq(int v)

{

    queue[++rear]=v;

}

int deleteq()

{

    return(queue[front++]);

}

int qempty()

{

  if(rear<front)

    return 1;

  else

    return 0;

}

void bfs(int v)

{

  int w;

  visit[v]=1;

  insertq(v);

  while(!qempty())

  {

    v=deleteq();

    for(w=1;w<=n;w++)

       if((adj[v][w]==1) && (visit[w]==0))

       {

              visit[w]=1;

              flag=1;

              printf("v%d\t",w);

              insertq(w);

       }

   }

}

void main()

{

    int v,w;

    printf("Enter the no.of vertices:\n");

    scanf("%d",&n);

    printf("Enter adjacency matrix:");

    for(v=1;v<=n;v++)

    {

      for(w=1;w<=n;w++)

       scanf("%d",&adj[v][w]);

    }

    printf("Enter the start vertex:");

    scanf("%d",&s);

    printf("Reachability of vertex %d\n",s);

    for(v=1;v<=n;v++)

            visit[v]=0;

    bfs(s);

    if(flag==0)

    {

      printf("No path found!!\n");

    }

}

OUTPUT 1:

Enter the no.of vertices:

4

Enter adjacency matrix:

0 1 0 0

0 0 1 1

0 0 0 0

1 0 1 0

Enter the start vertex:3

Reachability of vertex 3

No path found!!

OUTPUT2 :

Enter the no.of vertices:

4

Enter adjacency matrix:

0 1 0 0

0 0 1 1

0 0 0 0

1 0 1 0

Enter the start vertex:4

Reachability of vertex 4

v1        v3        v2