#include<stdio.h>
#include<conio.h>
#define MAX 30


typedef struct node
{
  int vertex;
  struct node *next;
}node;

typedef struct q
{
  int r,f;
  int data[MAX];
}q;


node *g[20];                                     //heads of linked list
int n;                                           //no. of nodes
int visited[MAX];

void readgraph();                //create adjacency list
void insert(int vi,int vj);                    //insert edge(vi,vj) in graph
void bfs(int i);
void dfs(int i);
void enquee(q *,int);
int dequee(q *);
int empty(q *);
int full(q *);

void main()
{
  int i,k;
  clrscr();
  do
  {
    printf("\n\n1.CREATE A GRAPH\n2.DFS\n3.BFS\n4.QUIT.");
    printf("\nEnter your choice::");
    scanf("%d",&k);
    switch(k)
    {
      case 1:
            readgraph();
            break;
      case 2:
            for(i=0;i<n;i++)
                visited[i]=0;
            printf("\nEnter the start node::");
            scanf("%d",&i);
            dfs(i);
            break;
      case 3:
            printf("\nEnter the start node::");
            scanf("%d",&i);
            bfs(i);
            break;

    }
   }while(k!=4);
}

void readgraph()
{
  int i,j,vi,vj,no;


  printf("\nEnter the no. of vertices::");
  scanf("%d",&n);
  for(i=0;i<n;i++)                //initialise g to NULL
    g[i]=NULL;

  printf("\nEnter the no. of edges::");         //insert edges to graph g
  scanf("%d",&no);
  for(i=0;i<no;i++)
  {
    printf("\nEnter the edge(u,v)::");
    scanf("%d%d",&vi,&vj);
    insert(vi,vj);
    insert(vj,vi);

  }

}

void insert(int vi,int vj)
{
  node *p,*q;
  q=(node*)malloc(sizeof(node));         //acquire memory for new node
  q->vertex=vj;
  q->next=NULL;


  if(g[vi]==NULL)
    g[vi]=q;                               //insert node in linked list
  else
  {
    p=g[vi];
    while(p->next!=NULL)                       //go to end of linked list
    p=p->next;
    p->next=q;
  }
}

void dfs(int i)
{
 node *p;
 p=g[i];
 visited[i]=1;
 printf("\nVisit->%d",i);
 while(p!=NULL)
 {
   i=p->vertex;
   if(!visited[i])
    dfs(i);
   p=p->next;
  }
}

void bfs(int v)
{
  int i,w;
  q x;
  node *p;
  x.r=x.f=-1;                        //initialise quee
  for(i=0;i<n;i++)
    visited[i]=0;

  enquee(&x,v);
  printf("\nVisit->%d",v);
  visited[v]=1;
  while(!empty(&x))
  {
    v=dequee(&x);
    //insert all unvisited vertices of v into quee
    for(p=g[v];p!=NULL;p=p->next)
    {
    w=p->vertex;
    if(visited[w]==0)
    {
        enquee(&x,w);
        visited[w]=1;
        printf("\nVisit->%d",w);
    }
     }
  }
}


int empty(q *p)
{
  if(p->r==-1 &&p->f==-1)
    return(1);
  return(0);
}

int full(q *p)
{
  if(p->r==MAX-1)
    return(1);
  return(0);

}

void enquee(q *p,int x)
{

  if(p->r==-1)
  {
    p->r=p->f=1;
  }
  else
    p->r=p->r+1;
  p->data[p->r]=x;
}

int dequee(q *p)
{
  int x;
  x=p->data[p->f];
  if(p->f==p->r)
    p->r=p->f=-1;
  else
    p->f=p->f+1;
  return(x);
}

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
   { int data;
     struct node *next;
   }node;

node *create();
node *insert_b(node *head,int x);
node *insert_e(node *head,int x);
node *insert_in(node *head,int x);
node *delete_b(node *head);
node *delete_e(node *head);
node *delete_in(node *head);
node *reverse(node *head);
void printreverse(node *head);
void print(node *head);

void main()
{ int op,op1,x;
  node *head=NULL;
  clrscr();
  do
    {
      printf("\n\n1)create\n2)Insert\n3)Delete\n4)Display Reverse ");
      printf("\n5)Revert the SLL\n6)Display\n7)Quit");
      printf("\nEnter your Choice:");
      scanf("%d",&op);
      switch(op)
       { case 1:head=create();break;
     case 2:printf("\n\t1)Beginning\n\t2)End\n\t3)In between");
        printf("\nEnter your choice : ");
        scanf("%d",&op1);
        printf("\nEnter the data to be inserted : ");
        scanf("%d",&x);
        switch(op1)
         {  case 1: head=insert_b(head,x);
                break;
            case 2: head=insert_e(head,x);
                break;
            case 3: head=insert_in(head, x);
                break;
          }
        break;
     case 3:printf("\n\t1)Beginning\n\t2)End\n\t3)In between");
        printf("\nEnter your choice : ");
        scanf("%d",&op1);
        switch(op1)
         {  case 1:head=delete_b(head);
               break;
            case 2:head=delete_e(head);
               break;
            case 3:head=delete_in(head);
               break;
          }
         break;
     case 4:printreverse(head);break;
     case 5:head=reverse(head);
        print(head);
        break;
     case 6:print(head);break;
       }
    }while(op!=7);
}

void printreverse(node *head)
  {
    if(head !=NULL)
       {
      printreverse(head->next);
      printf("%d   ",head->data);
       }
  }
node *create()
{ node *head,*p;
  int i,n;
  head=NULL;
  printf("\n Enter no of data:");
  scanf("%d",&n);
  printf("\nEnter the data:");
  for(i=0;i<n;i++)
   {
     if(head==NULL)
     p=head=(node*)malloc(sizeof(node));
     else
       {
     p->next=(node*)malloc(sizeof(node));
     p=p->next;
       }
       p->next=NULL;
       scanf("%d",&(p->data));
   }
 return(head);
}

node *insert_b(node *head,int x)
{   node *p;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    p->next=head;
    head=p;
    return(head);
}

node *insert_e(node *head,int x)
{   node *p,*q;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    p->next=NULL;
    if(head==NULL)
       return(p);
    //locate the last node
    for(q=head;q->next!=NULL;q=q->next)
    ;
    q->next=p;
    return(head);
}

node *insert_in(node *head,int x)
{   node *p,*q;
    int y;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    p->next=NULL;
    printf("\Insert after which number ? : ");
    scanf("%d",&y);
    //locate the lthe data 'y'
    for(q=head ; q != NULL && q->data != y ; q=q->next)
    ;
    if(q!=NULL)
      {
    p->next=q->next;
    q->next=p;
      }
    else
       printf("\nData not found ");
    return(head);
}
node *delete_b(node *head)
{
  node *p,*q;
  if(head==NULL)
     {
    printf("\nUnderflow....Empty Linked List");
    return(head);
     }
  p=head;
  head=head->next;
  free(p);
  return(head);

}
node *delete_e(node *head)
{
  node *p,*q;
  if(head==NULL)
     {
    printf("\nUnderflow....Empty Linked List");
    return(head);
     }
  p=head;
  if(head->next==NULL)
     { // Delete the only element
       head=NULL;
       free(p);
       return(head);
     }
//Locate the last but one node
   for(q=head;q->next->next !=NULL;q=q->next)
   ;
   p=q->next;
   q->next=NULL;
   free(p);
   return(head);
}
node *delete_in(node *head)
{
  node *p,*q;
  int x,i;
  if(head==NULL)
     {
    printf("\nUnderflow....Empty Linked List");
    return(head);
     }
  printf("\nEnter the data to be deleted : ");
  scanf("%d",&x);
  if(head->data==x)
     { // Delete the first element
       p=head;
       head=head->next;
       free(p);
       return(head);
     }
//Locate the node previous to one to be deleted
   for(q=head;q->next->data!=x && q->next !=NULL;q=q->next )
   ;
   if(q->next==NULL)
     {
       printf("\nUnderflow.....data not found");
       return(head);
     }
   p=q->next;
   q->next=q->next->next;
   free(p);
   return(head);
}

void print(node *head)
{ node *p;
 printf("\n\n");
 for(p=head;p!=NULL;p=p->next)
  printf("%d  ",p->data);
}

node *reverse(node *head)
  { node *p,*q,*r;
    p=NULL;
    q=head;
    r=q->next;
    while(q!=NULL)
      {
    q->next=p;
    p=q;
    q=r;
    if(q!=NULL)
       r=q->next;
      }
   return(p);
  }

 Click Here to Download Source Code with Executable Program