# GRAPH OF DATA STRUCTURE AND ALGORITHMS

Depth First Search (DFS) Program in C

In this tutorial you will learn about Depth First Search (DFS) program in C with algorithm. Most of graph problems involve traversal of a graph. Traversal of a graph means visiting each node and visiting exactly once. There are two types of traversal in graphs i.e. Depth First Search (DFS) and Breadth First Search(BFS).

### Spardhavani.com Android App Download Now Click Here It is like tree. Traversal can start from any vertex, say Vi . Vi is visited and then all vertices adjacent to Vi are traversed recursively using DFS.Since, a graph can have cycles. We must avoid revisiting a node. To do this, when we visit a vertex V, we mark it visited. A node that has already been marked as visited should not be selected for traversal. Marking of visited vertices can be done with the help of a global array visited[ ]. Array visited[ ] is initialized to false (0).

Depth First Search (DFS) Algorithm

n ← number of nodes Initialize visited[ ] to false (0) for(i=0;i<n;i++) visited[i] = 0; void DFS(vertex i) [DFS starting from i] { visited[i]=1; for each w adjacent to i if(!visited[w]) DFS(w); }

n ← number of nodes

Initialize visited[ ] to false (0)

for(i=0;i<n;i++)

visited[i] = 0;

void DFS(vertex i) [DFS starting from i]

{

visited[i]=1;

for each w adjacent to i

if(!visited[w])

DFS(w);

}

Depth First Search (DFS) Program in C [Adjacency Matrix]

#include<stdio.h>

void DFS(int);

int G,visited,n;   //n is no of vertices and graph is sorted in array G

void main()

{

int i,j;

printf(“Enter number of vertices:”);

scanf(“%d”,&n);

printf(“\nEnter adjecency matrix of the graph:”);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

scanf(“%d”,&G[i][j]);

//visited is initialized to zero

for(i=0;i<n;i++)

visited[i]=0;

DFS(0);

}

void DFS(int i)

{

int j;

printf(“\n%d”,i);

visited[i]=1;

for(j=0;j<n;j++)

if(!visited[j]&&G[i][j]==1)

DFS(j);

}

}

OUTPUT DEPTH FIRST SEARCH (DFS) PROGRAM IN C USING STRUCTURE

#include<stdio.h>

#include<stdlib.h>

typedef struct node

{

struct node *next;

int vertex;

}node;

node *G;

int visited;

int n;

void insert(int,int);

//insert an edge (vi,vj) in te adjacency list

void DFS(int);

void main()

{

int i;

//initialised visited to 0

for(i=0;i<n;i++)

visited[i]=0;

DFS(0);

}

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 i,vi,vj,no_of_edges;

printf(“Enter number of vertices:”);

scanf(“%d”,&n);

//initialise G[] with a null

for(i=0;i<n;i++)

{

G[i]=NULL;

//read edges and insert them in G[]

printf(“Enter number of edges:”);

scanf(“%d”,&no_of_edges);

for(i=0;i<no_of_edges;i++)

{

printf(“Enter an edge(u,v):”);

scanf(“%d%d”,&vi,&vj);

insert(vi,vj);

}

}

}

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 number vi

if(G[vi]==NULL)

G[vi]=q;

else

{

//go to end of the linked list

p=G[vi];

while(p->next!=NULL)

p=p->next;

p->next=q;

}

OUTPUT C program to implement Breadth First Search(BFS). Breadth First Search is an algorithm used to search a Tree or Graph. BFS search starts from root node then traverses into next level of graph or tree, if item found it stops other wise it continues with other nodes in the same level before moving on to the next level. The algorithm can also be used for just Tree/Graph traversal, without actually searching for a value. This is what being done in the program below. The disadvantage of BFS is it requires more memory compare to Depth First Search(DFS).

### PROGRAM

#include<stdio.h>

#include<stdlib.h>

#define MAX 100

#define initial 1

#define waiting 2

#define visited 3

int n;

int state[MAX];

void create_graph();

void BF_Traversal();

void BFS(int v);

int queue[MAX], front = -1,rear = -1;

void insert_queue(int vertex);

int delete_queue();

int isEmpty_queue();

int main()

{

create_graph();

BF_Traversal();

return 0;

}

void BF_Traversal()

{

int v;

for(v=0; v<n; v++)

state[v] = initial;

printf(“Enter Start Vertex for BFS: \n”);

scanf(“%d”, &v);

BFS(v);

}

void BFS(int v)

{

int i;

insert_queue(v);

state[v] = waiting;

while(!isEmpty_queue())

{

v = delete_queue( );

printf(“%d “,v);

state[v] = visited;

for(i=0; i<n; i++)

{

if(adj[v][i] == 1 && state[i] == initial)

{

insert_queue(i);

state[i] = waiting;

}

}

}

printf(“\n”);

}

void insert_queue(int vertex)

{

if(rear == MAX-1)

printf(“Queue Overflow\n”);

else

{

if(front == -1)

front = 0;

rear = rear+1;

queue[rear] = vertex ;

}

}

int is Empty_queue()

{

if(front == -1 || front > rear)

return 1;

else

return 0;

}

int delete_queue()

{

int delete_item;

if(front == -1 || front > rear)

{

printf(“Queue Underflow\n”);

exit(1);

}

delete_item = queue[front];

front = front+1;

return delete_item;

}

void create_graph()

{

int count,max_edge,origin,destin;

printf(“Enter number of vertices : “);

scanf(“%d”,&n);

max_edge = n*(n-1);

for(count=1; count<=max_edge; count++)

{

printf(“Enter edge %d( -1 -1 to quit ) : “,count);

scanf(“%d %d”,&origin,&destin);

if((origin == -1) && (destin == -1))

break;

if(origin>=n || destin>=n || origin<0 || destin<0)

{

printf(“Invalid edge!\n”);

count–;

}

else

{

}

}

OUTPUT  