[go: up one dir, main page]
Scribd
Upload
22 views3 pages

Graph

The document contains C++ code to implement breadth-first search (BFS) and depth-first search (DFS) algorithms on graphs. It defines functions for enqueueing and dequeuing nodes to a queue for BFS and pushing and popping nodes to a stack for DFS. The main function takes input for the number of vertices and adjacency matrix of a graph and allows the user to select BFS or DFS, starting node, and prints the traversal order.

Uploaded by

nithishvv3010
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
22 views3 pages

Graph

The document contains C++ code to implement breadth-first search (BFS) and depth-first search (DFS) algorithms on graphs. It defines functions for enqueueing and dequeuing nodes to a queue for BFS and pushing and popping nodes to a stack for DFS. The main function takes input for the number of vertices and adjacency matrix of a graph and allows the user to select BFS or DFS, starting node, and prints the traversal order.

Uploaded by

nithishvv3010
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 3

#include<iostream>

using namespace std;


int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20];
int dequeue();
void enqueue(int item);
void bfs(int s,int n);
void dfs(int s,int n);
void push(int item);
int pop();

main()
{
int n,i,s,ch,j;
char c,dummy;
cout<<"ENTER THE NUMBER VERTICES:"<<endl;
cin>>n;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<"ENTER 1 IF "<<i<<" HAS A EDGE WITH "<<j<<" ELSE 0 "<<endl;
cin>>a[i][j];
}
}
cout<<"THE ADJACENCY MATRIX IS:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
do
{
for(i=1;i<=n;i++)
vis[i]=0;
cout<<"MENU"<<endl;
cout<<"1.B.F.S"<<endl;
cout<<"2.D.F.S"<<endl;
cout<<"ENTER YOUR CHOICE:"<<endl;
cin>>ch;
cout<<"ENTER THE SOURCE VERTEX :"<<endl;
cin>>s;
switch(ch)
{
case 1:bfs(s,n);break;
case 2:dfs(s,n);break;
}
cout<<"DO U WANT TO CONTINUE(Y/N) ? "<<endl;
cin>>c;
}while((c=='y')||(c=='Y'));
}

//**************BFS(breadth-first search) code**************//


void bfs(int s,int n)
{
int p,i;
enqueue(s);
vis[s]=1;
p=dequeue();
if(p!=0)
cout<<" "<<p<<" ";
while(p!=0)
{
for(i=1;i<=n;i++)
if((a[p][i]!=0)&&(vis[i]==0))
{
enqueue(i);
vis[i]=1;
}
p=dequeue();
if(p!=0)
cout<<" "<<p<<" ";
}
for(i=1;i<=n;i++)
if(vis[i]==0)
bfs(i,n);
}

void enqueue(int item)


{
if(rear==19)
cout<<"QUEUE FULL"<<endl;
else
{
if(rear==-1)
{
q[++rear]=item;
front++;
}
else
q[++rear]=item;
}
}
int dequeue()
{
int k;
if((front>rear)||(front==-1))
return(0);
else
{
k=q[front++];
return(k);
}
}

//***************DFS(depth-first search) code******************//


void dfs(int s,int n)
{
int i,k;
push(s);
vis[s]=1;
k=pop();
if(k!=0)
cout<<" "<<k<<" ";
while(k!=0)
{
for(i=1;i<=n;i++)
if((a[k][i]!=0)&&(vis[i]==0))
{
push(i);
vis[i]=1;
}
k=pop();
if(k!=0)
cout<<" "<<k<<" ";
}
for(i=1;i<=n;i++)
if(vis[i]==0)
dfs(i,n);
}
void push(int item)
{
if(top==19)
cout<<"Stack overflow "<<endl;
else
stack[++top]=item;
}
int pop()
{
int k;
if(top==-1)
return(0);
else
{
k=stack[top--];
return(k);
}
}

You might also like