To Implement Graph using Adjacency List in C

Program to implement Graph using Adjacency List  and traversing using DFS and BFS in C

 #include<stdio.h>
 #include<conio.h>
 #include<alloc.h>

 #define max 10

 struct node
 {
 int vertex;
 struct node *next;
 };
 typedef struct node* nodeptr;
 typedef struct queue
 {
int front,rear;
int arr[max];
 };
 typedef struct stack
 {
int top;
int arr[max];
 };
 nodeptr getnode()
 {
nodeptr p;
p=(nodeptr)malloc(sizeof(struct node));
p->next=NULL;
return p;
 }

  int empty(struct stack *s)
  {
 if(s->top==-1)
 {
return 1;
 }
 else
return 0;
  }
  void push(struct stack *s,int x)
  {
if(s->top==max-1)
printf("\n Queue Overflow");
else
{
s->top++;
s->arr[s->top]=x;
}
  }
  int pop(struct stack *s)
  {
int x;
if(empty(s))
printf("\n Queue Overflow..!");
else
{
x=s->arr[s->top];
s->top--;
}
return x;
  }

  int qempty(struct queue *q)
  {
if(q->front > q->rear)
return 1;
else
return 0;
  }
  void insertq(struct queue *q,int x)
  {
if(q->rear==max-1)
printf("\n Queue Overflow..1");
else
{
q->rear++;
q->arr[q->rear]=x;
}
  }
  int removeq(struct queue *q)
  {
 int x;
 if(qempty(q))
printf("\n Queue Overflow..!");
 else
 {
x=q->arr[q->front];
q->front++;
 }
 return x;
  }

  void init(nodeptr head[],int n)
  {
int v;
for(v=1;v<=n;v++)
head[v]=NULL;
  }
  void initialise_visit(int visited[],int n)
  {
int i;
for(i=1;i<=n;i++)
visited[i]=0;
  }

    void create(nodeptr head[])
  {
nodeptr adj;
char ch='y';
int i,v1,v2,v,c;
nodeptr new1,p;
printf("\n <0>Directed");
printf("\n <1>UnDirected");
printf("\n Enter Your Choice:\t");
scanf("%d",&c);

do
{
printf("\n Enter The Edge Between Two Vertices:\t");
scanf("%d%d",&v1,&v2);
new1=getnode();
new1->vertex=v2;
p=head[v1];
if(p==NULL)
head[v1]=new1;
else
{
while(p->next!=NULL)
p=p->next;
p->next=new1;
}
if(c==1)
{
new1=getnode();
new1->vertex=v1;
p=head[v2];
if(p==NULL)
head[v2]=new1;
else
{
 while(p->next!=NULL)
 p=p->next;
 p->next=new1;
}
}
printf("\n Do You Want To Add More Edges In Graph(y/n):\t");
ch=getche();
}while(ch=='y'||ch=='Y');
  }

  void display(nodeptr head[],int n)
  {
int v;
nodeptr adj;
printf("\n Adjancency List Is:\n");
for(v=1;v<=n;v++)
{
printf("\n Head[%d]->",v);
adj=head[v];
while(adj!=NULL)
{
printf("%d  ",adj->vertex);
adj=adj->next;
}
printf("\n");
}
  }

  void DFSR(nodeptr head[],int start,int visited[])
  {
nodeptr adj;
visited[start]=1;
printf("\t %d",start);
adj=head[start];
while(adj!=NULL)
{
if(visited[adj->vertex]==0)
{
DFSR(head,adj->vertex,visited);
}
adj=adj->next;
}
  }

  void DFSN(nodeptr head[],int start,int visited[])
  {
nodeptr adj;
struct stack s;
int v;
s.top=-1;
push(&s,99);
visited[start]=1;
printf("\n %d",start);
push(&s,start);
do
{
 adj=head[start];
 while(adj!=NULL)
 {
if(visited[adj->vertex]==0)
{
visited[adj->vertex]=1;
printf("\t%d",adj->vertex);
push(&s,adj->vertex);
start=adj->vertex;
break;
}
else
adj=adj->next;
 }
 if(adj==NULL)
 {
start=pop(&s);
 }

}while(!empty(&s));

  }
  void BFS(nodeptr head[],int start,int visited[])
  {
nodeptr adj;
struct queue q;
int v;
q.front=0;
q.rear=-1;
visited[start]=1;
printf("\n %d",start);
insertq(&q,start);
while(!qempty(&q))
{
v=removeq(&q);
adj=head[v];
while(adj!=NULL)
{
if(visited[adj->vertex]==0)
{
 visited[adj->vertex]=1;
 printf("\t %d",adj->vertex);
}
adj=adj->next;
}
}
  }
  void main()
  {
char c='y';
int ch,start,n,visited[10];
nodeptr head[10];
clrscr();
do
{
clrscr();
printf("\n========Graph========");
printf("\n 1. Create");
printf("\n 2. Display Adjancency List");
printf("\n 3. Depth First Search(Rec)");
printf("\n 4. Depth First Search(Non-Rec)");
printf("\n 5. Breadth First Search");
printf("\n 6. Exit");
printf("\n=====================");
printf("\n Enter Your Choice:\t");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n Enter The No. of Vertices In Graph:\t");
scanf("%d",&n);
init(head,n);
create(head);
break;

case 2:
display(head,n);
break;

case 3:
printf("\n Enter The Vertex From Which You Want To Start Traversal");
scanf("%d",&start);
initialise_visit(visited,n);
printf("\n Recursive Depth First Search Is\n");
DFSR(head,start,visited);
break;

case 4:
printf("\n Enter The Vertex From Which You Want To Start Traversal");
scanf("%d",&start);
initialise_visit(visited,n);
printf("\n Non-Recursive Depth First Search Is\n");
DFSN(head,start,visited);
break;

case 5:
printf("\n Enter The Vertex From Which You Want To Start Traversal");
scanf("%d",&start);
initialise_visit(visited,n);
BFS(head,start,visited);
break;

case 6:
break;
}
printf("\n Do You Want To Continue(y/n):\t");
c=getche();
 }while(c=='Y'||c=='y');
getch();
  }