Lab Program 11 DFS BFS 15CSL38 Data Structures in C Lab

Lab Program 11

Design, Develop and Implement a Program in C for the

following operations on Graph(G) of Cities

a. Create a Graph of N cities using Adjacency Matrix.

b. Print all the nodes reachable from a given starting node in a digraph using DFS/BFS method

#include<stdio.h>
#include<stdlib.h>

int a[50][50], n, visited[50];
int q[20], front = -1,rear = -1;
int s[20], top = -1, count=0;

void bfs(int v)
{
int i, cur;
visited[v] = 1;
q[++rear] = 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);
}
}
}
}

void dfs(int v)
{
         int i;
visited[v]=1;
s[++top] = v;
for(i=1;i<=n;i++)
{
if(a[v][i] == 1&& visited[i] == 0 )
{
                           printf("%d ", i);
                          dfs(i);
}
}
}

int main()
{

         int ch, start, 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]);
          }

    for(i=1;i<=n;i++)
           visited[i]=0;
    printf("\nEnter the starting vertex: ");
    scanf("%d",&start);

        printf("\n==>1. BFS: Print all nodes reachable from a given starting node");
        printf("\n==>2. DFS: Print all nodes reachable from a given starting node");
        printf("\n==>3:Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &ch);
        switch(ch)
        {
            case 1: printf("\nNodes reachable from starting vertex %d are: ", start);
                    bfs(start);
                    for(i=1;i<=n;i++)
                    {
                        if(visited[i]==0)
                            printf("\nThe vertex that is not reachable is %d" ,i);
                    }
                    break;


            case 2: printf("\nNodes reachable from starting vertex %d are:\n",start);
                    dfs(start);
                    break;
           case 3: exit(0);
           default: printf("\nPlease enter valid choice:");
        }
}

Output:

Case 1:

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

~~~Menu~~~~

==>1. BFS: Print all nodes reachable from a given starting node

==>2. DFS: Print all nodes reachable from a given starting node

==>3:Exit

Enter your choice: 1

Enter the starting vertex: 1

Nodes reachable from starting vertex 1 are: 2       4          3

Case 2:

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

~~~Menu~~~~

==>1. BFS: Print all nodes reachable from a given starting node

==>2. DFS: Print all nodes reachable from a given starting node

==>3:Exit

Enter your choice: 1

Enter the starting vertex: 2

Nodes reachable from starting vertex 2 are:  3      4

The vertex that is not reachable is 1

Case 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

~~~Menu~~~~

==>1. BFS: Print all nodes reachable from a given starting node

==>2. DFS: Print all nodes reachable from a given starting node

==>3:Exit

Enter your choice: 2

Enter the starting vertex:     1

Nodes reachable from starting vertex 1 are:  2       3       4

Case 4:

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

~~~Menu~~~~

==>1. BFS: Print all nodes reachable from a given starting node

==>2. DFS: Print all nodes reachable from a given starting node

==>3:Exit

Enter your choice: 2

Enter the starting vertex:     2

Nodes reachable from starting vertex 2 are:   3       4