Computer Science: 5th sem ADA Lab Program 9

Analysis and Design of Algorithms Lab.

Question 9.

//print all the nodes reachable from a given starting node in a diagraph using BFS(Breadth first search)

///Check whether a given graph is connected or not using DFS(Depth first search)

#include<iostream>

#include<conio.h>

#define MAX 10

using namespace std;

void BFS(int a[MAX][MAX],int n,int v,int *vis,int &count)

{

if(vis[v]==-1)

{

vis[v]=++count;

int *q=new int[n];

int q_ponter=-1;

for(int i=0;i<n;i++)

q[i]=-1;

for(int i=0;i<n;i++)

{

if(a[v][i]!=0 && vis[i]==-1)

{

vis[i]=++count;

q[++q_ponter]=i;

}

}

for(int i=0;i<=q_ponter;i++)

BFS(a,n,q[i],vis,count);

}

}

void bfs(int a[MAX][MAX],int n)

{

int *vis=new int[n];

for(int i=0;i<n;i++)

vis[i]=-1;

int count=0;

for(int i=0;i<n;i++)

{

BFS(a,n,i,vis,count);

}

for(int i=0;i<n;i++)

cout<<vis[i]<<" ";

}

void DFS(int a[MAX][MAX],int n,int v,int *vis)

{

if(vis[v]==0)

{

vis[v]=1;

for(int i=0;i<n;i++)

if(a[v][i]!=99)

DFS(a,n,i,vis);

}

}

bool dfs(int a[MAX][MAX],int n)

{

int *vis=new int[n];

for(int i=0;i<n;i++)

vis[i]=-1;



DFS(a,n,0,vis);

for(int i=0;i<n;i++)

if(vis[i]==-1)

return false;

return true;

}

void main()

{

int n;

cout<<"Enter the size of the array:";cin>>n;

cout<<"Enter the matrix:\n\n";

int arr[MAX][MAX];

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

cin>>arr[i][j];



cout<<"\nThe order of BFS traversal according to the vertici numbers:\n";

bfs(arr,n);

if(dfs(arr,n))

cout<<"\nThe graph is connected";

else

cout<<"\nThe graph is not connected";

getch();

}