Breadth First Search (BFS)

Breadth First Search (BFS)

#include<stdio.h>

#include<stdlib.h>

void bfs(int v);

int a[50][50], n, visited[50];

int q[20], front = -1,rear = -1;

void creategraph()

{

            int i, j;

            printf("\nEnter the number of vertices in graph:  ");

            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]);

}

void bfs(int v)

{

            int i, cur;

            visited[v] = 1;

            q[++rear] = v;

            printf("\nNodes reachable from starting vertex %d are: ", v);

            while(front!=rear)

            {

                        cur = q[++front];

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

                        {

                                    if((a[cur][i]==1)&&(visited[i]==0))

                                    {

                                        q[++rear]=i;

                                                visited[i]=1;

                                                printf("%d ", i);

                                    }

                        }

            }

}

int main()

{

            int ch, start, i, j;

            creategraph();

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

                        visited[i]=0;

            printf("\nEnter the starting vertex: ");

            scanf("%d", &start);

             bfs(start);

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

             {

                                    if(visited[i]==0)

                                                printf("\nThe vertex that is not reachable is %d" ,i);

             }

}

Output:

Enter the number of vertices in graph:  4

Enter the adjacency matrix:

0          1          0          1

0          0          1          0

0          0          0          1

0          0          0          0

Enter the starting vertex: 1

Nodes reachable from starting vertex 1 are: 2 4 3

Enter the number of vertices in graph:  4

Enter the adjacency matrix:

0          1          0          1

0          0          1          0

0          0          0          1

0          0          0          0

Enter the starting vertex: 2

Nodes reachable from starting vertex 2 are: 3 4

The vertex that is not reachable is 1