BFS and DFS on a graph represented using adjacency list C program

Saturday, 1 March 2014


#include<conio.h>
#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

void main()
{
 int i,op;
 clrscr();
 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;
 printf("\n%d",i);
 p=G[i];
 visited[i]=1;
 while(p!=NULL)
 {
  i=p->vertex;
  if(!visited[i])
   DFS(i);
  p=p->next;
 }
}


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,vi,vj,no_of_edges;
 printf("\nEnter no. of vertices :");
 scanf("%d",&n);
 //initialise G[] with NULL
 for(i=0;i<n;i++)
  G[i]=NULL;
 //read edges and insert them in G[]
 printf("\nEnter no of edges :");
 scanf("%d",&no_of_edges);
 for(i=0;i<no_of_edges;i++)
 {
  printf("\nEnter an edge (u,v)  :");
  scanf("%d%d",&vi,&vj);
  insert(vi,vj);
  insert(vj,vi);
 }
}

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;
 }
}



OUTPUT:-


1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 1

Enter no. of vertices :4

Enter no of edges :5

Enter an edge (u,v)  :1 2

Enter an edge (u,v)  :2 3

Enter an edge (u,v)  :3 4

Enter an edge (u,v)  :4 1

Enter an edge (u,v)  :1 3


1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 2

Starting Node No. : 1

Visit   1
visit   2
visit   3
visit   4


1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 3

Starting Node No. :2


2
1
4
3
1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 2

Starting Node No. : 4

Visit   4
visit   3
visit   1
visit   2

1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 4

2 comments

  1. There is an error on BFS initialization, it should be:

    for(i=0;i <=n; i++)
    visited[i]=0;

    ReplyDelete

Related Posts Plugin for WordPress, Blogger...
Related Posts Plugin for WordPress, Blogger...
 

Most Reading

Labels