Representing Graph using adjacency list & perform DFS & BFS - DS TUTORIAL

A graph is a collection of nodes and edges.

Description:

This tutorial demonstrate how to create a graph using adjacency list and perform DFS and BFS.
Different kind of graph are listed below:

Directed Graph: A directed graph is one in which edges connect nodes in only one direction(unidirectional).

Undirected Graph: An undirected graph is one in which edges connect nodes bidirectionally (in both directions). Node: A node, usually drawn as a circle, represents an item that can be related to other items or nodes. Nodes are sometimes referred to as vertices.

Edge: An edge represents a connection between nodes. Edges can be either directed or undirected, depending on the type of graph. Edges can also have weights, which may corresponds distance between edges.

Connected: A graph is said to be connected if from any node you can reach any other node.

Disconnected: A graph is said to be disconnected if certain groups of nodes from an island that has no connection to the rest of the graph.

Code:

 #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();
  }

Output: