Tuesday, February 17, 2015
Depth First Search DFS Traversal of a Graph Algorithm and Program
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). In this tutorial I will discuss about DFS.
Read Previous Articles:
1. Graphs: Introduction and Terminology
2. Representation of Graphs: Adjacency Matrix and Adjacency List
Depth First Search (DFS)
It is like preorder traversal of 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).
Algorithm for DFS
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);
}
The graph shown above is taken as input in both the programs mentioned below:
C Program to implement DFS traversal on a graph represented using an 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("
Enter adjecency matrix of the graph:");
Enter 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("
%d",i);
%d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}
C Program to implement DFS traversal on a graph represented using an adjacency list
#include<stdio.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("
%d",i);
%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;
}
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.