/*DFS and BFS on graph represented using adjacency list */
#include<stdio.h>
#include<stdlib.h>
#define MAX 20
typedef struct Q
{
int data[MAX];
int R,F;
}Q;
typedef struct node
{
struct node *next;
int vertex;
}node;
void enqueue(Q *,int);
int dequque(Q *);
int empty(Q *);
int full(Q *);
void BFS(int);
void readgraph(); //create an adjecency list
void insert(int vi,int vj); //insert an edge (vi,vj)in adj.list
void DFS(int i);
int visited[MAX];
node *G[20]; //heads of the linked list
int n; // no of nodes
int main()
{
int i,op;
do
{ printf("\n\n1)Create\n2)BFS\n3)DFS\n4)Quit");
printf("\nEnter Your Choice: ");
scanf("%d",&op);
switch(op)
{ case 1: readgraph();break;
case 2: printf("\nStarting Node No. : ");
scanf("%d",&i);
BFS(i);break;
case 3: for(i=0;i<n;i++)
visited[i]=0;
printf("\nStarting Node No. : ");
scanf("%d",&i);
DFS(i);break;
}
}while(op!=4);
}
void BFS(int v)
{
int w,i,visited[MAX];
Q q;
node *p;
q.R=q.F=-1; //initialise
for(i=0;i<n;i++)
visited[i]=0;
enqueue(&q,v);
printf("\nVisit\t%d",v);
visited[v]=1;
while(!empty(&q))
{
v=dequeue(&q);
//insert all unvisited,adjacent vertices of v into queue
for(p=G[v];p!=NULL;p=p->next)
{
w=p->vertex;
if(visited[w]==0)
{
enqueue(&q,w);
visited[w]=1;
printf("\nvisit\t%d",w);
}
}
}
}
void DFS(int i)
{
node *p;
int stack[10],top=-1;
stack[++top]=i;
while(top != -1)
{
i=stack[top--];
if(!visited[i])
{
visited[i]=1;
printf("%d ",i);
for(p=G[i];p!=NULL;p=p->next)
if(!visited[p->vertex])
stack[++top]=p->vertex;
}
}
}
int empty(Q *P)
{
if(P->R==-1)
return(1);
return(0);
}
int full(Q *P)
{
if(P->R==MAX-1)
return(1);
return(0);
}
void enqueue(Q *P,int x)
{
if(P->R==-1)
{
P->R=P->F=0;
P->data[P->R]=x;
}
else
{
P->R=P->R+1;
P->data[P->R]=x;
}
}
int dequeue(Q *P)
{
int x;
x=P->data[P->F];
if(P->R==P->F)
{
P->R=-1;
P->F=-1;
}
else
P->F=P->F+1;
return(x);
}
void readgraph()
{ int i,j;
int adj[10][10];
printf("\nEnter no. of vertices :");
scanf("%d",&n);
printf("\nEnter Adjacency matrix :\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&adj[i][j]);
//initialise G[] with NULL
for(i=0;i<n;i++)
G[i]=NULL;
for(i=0;i<n;i++) //create adjacency list
for(j=0;j<n;j++)
if(adj[i][j]!=0)
insert(i,j);
}
void insert(int vi,int vj)
{
node *p,*q;
//acquire memory for the new node
q=(node *)malloc(sizeof(node));
q->vertex=vj;
q->next=NULL;
//insert the node in the linked list for the vertex no. vi
if(G[vi]==NULL)
G[vi]=q;
else
{
// go to the end of linked list
p=G[vi];
while(p->next!=NULL)
p=p->next;
p->next=q;
}
}
