# Representing Graph using adjacency list & perform DFS & BFS

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

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

{
char ch='y';
int i,v1,v2,v,c;
nodeptr new1,p;
printf("\n <0>Directed");
printf("\n <1>UnDirected");
scanf("%d",&c);

do
{
printf("\n Enter The Edge Between Two Vertices:\t");
scanf("%d%d",&v1,&v2);
new1=getnode();
new1->vertex=v2;
if(p==NULL)
else
{
while(p->next!=NULL)
p=p->next;
p->next=new1;
}
if(c==1)
{
new1=getnode();
new1->vertex=v1;
if(p==NULL)
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');
}

{
int v;
for(v=1;v<=n;v++)
{
{
}
printf("\n");
}
}

{
visited[start]=1;
printf("\t %d",start);
{
{
}
}
}

{
struct stack s;
int v;
s.top=-1;
push(&s,99);
visited[start]=1;
printf("\n %d",start);
push(&s,start);
do
{
{
{
break;
}
else
}
{
start=pop(&s);
}

}while(!empty(&s));

}
{
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);
{
{
}
}
}
}
void main()
{
char c='y';
int ch,start,n,visited[10];
clrscr();
do
{
clrscr();
printf("\n========Graph========");
printf("\n 1. Create");
printf("\n 3. Depth First Search(Rec)");
printf("\n 4. Depth First Search(Non-Rec)");
printf("\n 6. Exit");
printf("\n=====================");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n Enter The No. of Vertices In Graph:\t");
scanf("%d",&n);
break;

case 2:
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");
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");
break;

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

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

## Output:

Related Tutorials