Share on Google+Share on Google+

Representing Graph using adjacency list & perform DFS & BFS

Advertisement
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:

Download this code

Advertisements

Advertisement

Posted on: June 21, 2010 If you enjoyed this post then why not add us on Google+? Add us to your Circles

Share this Tutorial Follow us on Twitter, or add us on Facebook or Google Plus to keep you updated with the recent trends of Java and other open source platforms.