Program 11

Program 11

#include<stdio.h>

#include<stdlib.h>

void bfs(int v);

void dfs(int v);

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

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

int s[20], top = -1, count=0;

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

}

}

}

}

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 )

{

dfs(i);

count++;

}

}

}

int main()

{

int ch, start, i, j;

creategraph();

printf("\n\n~~~Menu~~~~");

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

}

break;

case 2: for(i=1;i<=n;i++)

visited[i] = 0;

printf("\n Enter the starting vertex:\t");

scanf("%d", &start);

dfs(start);

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

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

printf("%d\t", s[i]);

break;

case 3: exit(0);

default: printf("\nPlease enter valid choice:");

}

}