GRAPH OF DATA STRUCTURE AND ALGORITHMS

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 Herespardhavani android app

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[10][10],visited[10],n;   //n is no of vertices and graph is sorted in array G[10][10]

void main()

{

int i,j;

printf(“Enter number of vertices:”);

scanf(“%d”,&n);

//read the adjecency matrix

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

spardhavani.com

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[20];

//heads of linked list

int visited[20];

int n;

void read_graph();

//create adjacency list

void insert(int,int);

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

void DFS(int);

void main()

{

int i;

read_graph();

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

}

}

void read_graph()

{

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

spardhavani

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 adj[MAX][MAX];

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

{

adj[origin][destin] =1;

}

}

OUTPUT

Spardhavani

Without Water Mark Ready Project Buy Now Online  Rs 34/-  CLICK HERE

BUY NOW

spardhavani fb page spardhavani andriod app spardhavani youtube Spardhavani Twitter

323 total views, 1 views today

Leave a Reply

Your email address will not be published. Required fields are marked *

This site is protected by wp-copyrightpro.com