Represent graph using adjacency list and perform DFS and BFS

                         Link List
/*Represent graph using adjacency list and perform DFS and BFS*/
#include<conio.h>
#include<stdio.h>
#include<iostream.h>
#include<alloc.h>

struct sll
{
int data;
struct sll * next;
};
typedef struct sll node;

class graph
{
private:
node * head[20],* last,* temp;
int visit[20],no,n,i,j;
public:
void create();
void dfs(int );
void bfs(int );
};
class stack
{
private:
int item[20];
int top;
public:
stack()
{
top=-1;
}
void push(int data)
{
top++;
item[top]=data;
}
int pop()
{
int data;
data=item[top];
top--;
return data;
}
int empty()
{
if(top==-1)
return 1;
else
return 0;
}
};
void graph::create()
{
int v1,v2;
cout<<"\nEnter no of vertices of graph : ";
cin>>no;
for(i=0;i<no;i++)
{
head[i]=NULL;
head[i]->next=NULL;
}
for(i=0;i<no;i++)
{
temp=new node;
cout<<"\nEnter vertex : ";
cin>>temp->data;
temp->next=NULL;
head[i]=temp;
}
cout<<"\nEnter no of edges : ";
cin>>n;
for(j=0;j<n;j++)
{
cout<<"\nEnter edge no:"<<j+1<<": ";
cin>>v1>>v2;
temp=new node;
temp->data=v2;
temp->next=NULL;
for(i=0;i<no;i++)
{
last=head[i];
if(head[i]->data==v1)
break;

}
last=head[i];
if(head[i]->next==NULL)
{
head[i]->next=temp;
}
else
{
last=head[i];
while(last->next!=NULL)
{
last=last->next;
}
last->next=temp;
}
}
}

void graph::dfs(int sv)
{
int j,visit[20]={0};
stack s;
node * start,*end;
s.push(sv);
for(int i=0;i<no;i++)
{
start=head[i];
if(start->data==sv)
{
visit[i]=1;
break;
}
}
cout<<"\t";
while(!s.empty())
{
sv=s.pop();
cout<<sv<<"\t";
for(i=0;i<no;i++)
{
start=head[i];
if(start->data==sv)
break;

}
end=head[i]->next;
while(end!=NULL)
{
sv=end->data;
for(i=0;i<no;i++)
{
start=head[i];
if(start->data==sv)
break;

}
if(visit[i]==0)
{
s.push(sv);
visit[i]=1;
}
end=end->next;
}

}

}
void graph::bfs(int sv)
{
int j,visit[20]={0};
stack s;
node * start,*end;
s.push(sv);
cout<<"\t"<<sv;
for(int i=0;i<no;i++)
{
start=head[i];
if(start->data==sv)
{
visit[i]=1;
break;
}
}
while(!s.empty())
{
sv=s.pop();
for(i=0;i<no;i++)
{
start=head[i];
if(start->data==sv)
break;

}
end=head[i]->next;
while(end!=NULL)
{
sv=end->data;
for(i=0;i<no;i++)
{
start=head[i];
if(start->data==sv)
break;

}
if(visit[i]==0)
{
s.push(sv);
cout<<"\t"<<sv;
visit[i]=1;
}
end=end->next;
}

}

}
void main()
{
graph g1;
int no;
clrscr();
g1.create();
cout<<"\n********DFS*********";
cout<<"\nEnter starting vertex ";
cin>>no;
g1.dfs(no);
cout<<"\n********BFS*********";
cout<<"\nEnter starting vertex ";
cin>>no;
g1.bfs(no);

getch();
}

/* OUTPUT

Enter no of vertices of graph : 4

Enter vertex : 1

Enter vertex : 2

Enter vertex : 3

Enter vertex : 4

Enter no of edges : 5

Enter edge no:1: 1 2

Enter edge no:2: 2 3

Enter edge no:3: 3 4

Enter edge no:4: 4 1

Enter edge no:5: 1 3

********DFS*********
Enter starting vertex 1
        1       3       4       2
********BFS*********
Enter starting vertex 1
        1       2       3       4
*/

                                 Using Matrix

/*4. Represent graph using adjacency list and perform DFS and BFS*/

#include<iostream.h>
#include<conio.h>


int ad[10][10],n,m,v1,v2,i;

class gr
{
public:
void ins(int,int);
void cre();
void disp(int [10][10],int);
void dfsm();
void bfsm();

};

void gr::cre()
{
cout<<"\nEnter How many vertex in graph:";
cin>>n;
cout<<"\nEnter how many edges in graph(for undirected count as 2):";
cin>>m;

for(i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ad[i][j]=0;

for(i=0;i<m;i++)
{
cout<<i+1<<"th edge(v1,v2):";
cin>>v1>>v2;
ins(v1,v2);
ins(v2,v1);
}
}

void gr::ins(int v1,int v2)
{
ad[v1][v2]=1;
}

void gr::disp(int ad[10][10],int v1)
{
cout<<"\n"<<v1;
for(i=1;i<=n;i++)
{
if(ad[v1][i]==1)
cout<<" "<<i;
}
getch();
}

void gr::dfsm()
{
int stack[10],top=-1,st,i,visit[10];
cout<<"\nEnter strarting point:";
cin>>st;
cout<<"\n\nDFS:- ";
for(i=1;i<=n;i++)
visit[i]=0;

top++;
stack[top]=st;

while(top!=-1)
{
v1=stack[top];
top--;
if(visit[v1]==0)
{
cout<<" "<<v1;
visit[v1]=1;
}

for(i=1;i<=n;i++)
{
if(visit[i]==0)
{
top++;
stack[top]=i;
}
}

}
}

void gr::bfsm()
{
int q[10],f=-1,r=-1,st,i,visit[10];
for(i=1;i<=n;i++)
visit[i]=0;

cout<<"\nEnter strarting point:";
cin>>st;
cout<<"\n\nBFS:- ";
r++;
q[r]=st;
visit[st]=1;
while(r!=f)
{
f++;
v1=q[f];
cout<<" "<<v1;

for(i=1;i<=n;i++)
{
if(ad[v1][i]==1)
{
if(visit[i]==0)
{
r++;
q[r]=i;
visit[i]=1;
}
}
}
}
}

void main()
{
gr obj;
clrscr();
cout<<"\n********CREATION OF GRAPH********\n\n";
obj.cre();

int ch;
do
{
cout<<"\n**********MAIN MENU*******";
cout<<"\n1.DFS";
cout<<"\n2.BFS";
cout<<"\n3.EXIT";
cout<<"\nEnter Choice:";
cin>>ch;
switch(ch)
{
 case 1:
cout<<"\n*********DEPTH FIRST SEARCH********\n";
obj.dfsm();
break;
 case 2:
cout<<"\n*********BREATH FIRST SEARCH*********\n";
obj.bfsm();
break;
 case 3:
break;
 default:
cout<<"\nWRONG CHOICE";
}
}while(ch!=3);
}
/*
OUTPUT

********CREATION OF GRAPH********                                              
                                                                               
                                                                               
Enter How many vertex in graph:5                                              
                                                                               
Enter how many edges in graph(for undirected count as 2):6                    
1th edge(v1,v2):1 2                                                            
2th edge(v1,v2):2 3                                                            
3th edge(v1,v2):3 4                                                            
4th edge(v1,v2):4 5                                                            
5th edge(v1,v2):5 2                                                            
6th edge(v1,v2):4 2
                                                                               
**********MAIN MENU*******                                                    
1.DFS                                                                          
2.BFS                                                                          
3.EXIT                                                                        
Enter Choice:1                                                                
                                                                               
*********DEPTH FIRST SEARCH********                                            
                                                                               
Enter strarting point:1                                                        
                                                                               
                                                                               
DFS:-  1 5 4 3 2                                                              
**********MAIN MENU*******                                                    
1.DFS                                                                          
2.BFS                                                                          
3.EXIT                                                                        
Enter Choice:2                                                                
                                                                               
*********BREATH FIRST SEARCH*********                                          
                                                                               
Enter strarting point:3                                                        
                                                                               
                                                                               
BFS:-  3 2 4 1 5                                                              
**********MAIN MENU*******                                                    
1.DFS                                                                          
2.BFS                                                                          
3.EXIT                                                                        
Enter Choice:3                                                                
  */