Depth First Search:
In Depth First Search we are using stack data structure to traverse a graph. First select a vertex randomly, mark it as visited vertex and push this node into the stack. Then select an unvisited and adjacent vertex of the vertex which is at the top of the stack. Mark that vertex as visited and push it into the stack. Continue the same process until there is no adjacent vertex of the vertex at the top of the stack. Then delete one element from the stack and continue the same process until stack is empty.
Steps:
1. Select a vertex randomly from the graph as a starting point.
2. Mark that vertex as visited and push that vertex into the stack.
3. Select an adjacent vertex of vertex at the top of the stack and which is not visited.
4. Mark that vertex as visited and push that vertex into the stack.
5. Continue the step 3 and 4 until there is no vertex to be visited from the vertex at the top of the stack.
6. If there is no vertex to be visited from the vertex at the top of the stack, delete one element from the stack.
7. Repeat step 3 and 4 until stack is empty.
/*==========================================================================================
**
** File Name : dfs_stack.c
** Creation Date : Fri 13 Oct 2017 04:13:10 PM IST
** Last Modified : Fri 13 Oct 2017 08:09:25 PM IST
** Compiler : gcc
** Author : Manoj Kumar Patra, Asst. Professor
** Organization : Vignan University, Guntur, India.
**
**=========================================================================================*/
#include<stdio.h>
void DepthFirstSearch(int);
int graph[100][100],visited[100],n;
void main()
{
int i,j;
printf("Enter total number of vertices in the graph: ");
scanf("%d",&n);
printf("\nEnter adjecency matrix of the graph:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&graph[i][j]);
}
printf("\n");
}
//initially mark all verteces as unvisited
printf("\nThe adjecency matrix of the graph is:\n");
printf("= = = = = = = = = = = = = = = = = = = =\n");
for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
{
printf("%d\t",graph[i][j]);
}
printf("\n");
}
printf("= = = = = = = = = = = = = = = = = = = =\n");
for(i=0;i<n;i++)
visited[i]=0;
printf("\nVisited Sequence: \n");
DepthFirstSearch(0);
printf("\n\n");
}
void DepthFirstSearch(int i)
{
int stack[n],top=-1;
int j, curr;
printf("V%d\t",i);
visited[i]=1;
stack[++top]=i;
while(top != -1)
{
curr=stack[top];
for(j=0;j<n;j++)
{
if(visited[j]==0 && graph[i][j]==1)
{
stack[++top]=j;
DepthFirstSearch(stack[top]);
}
}
top--;
}
}
OutPut:
manoj@ubuntu:~$ gcc dfs_stack.c -o dfs_stack
manoj@ubuntu:~$ ./dfs_stack
Enter total number of vertices in the graph: 5
Enter adjecency matrix of the graph:
0
1
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
The adjecency matrix of the graph is:
= = = = = = = = = = = = = = = = = = = =
0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 0
0 1 0 1 0
= = = = = = = = = = = = = = = = = = = =
Visited Sequence: V0 V1 V3 V2 V4
manoj@ubuntu:~$
In Depth First Search we are using stack data structure to traverse a graph. First select a vertex randomly, mark it as visited vertex and push this node into the stack. Then select an unvisited and adjacent vertex of the vertex which is at the top of the stack. Mark that vertex as visited and push it into the stack. Continue the same process until there is no adjacent vertex of the vertex at the top of the stack. Then delete one element from the stack and continue the same process until stack is empty.
Steps:
1. Select a vertex randomly from the graph as a starting point.
2. Mark that vertex as visited and push that vertex into the stack.
3. Select an adjacent vertex of vertex at the top of the stack and which is not visited.
4. Mark that vertex as visited and push that vertex into the stack.
5. Continue the step 3 and 4 until there is no vertex to be visited from the vertex at the top of the stack.
6. If there is no vertex to be visited from the vertex at the top of the stack, delete one element from the stack.
7. Repeat step 3 and 4 until stack is empty.
/*==========================================================================================
**
** File Name : dfs_stack.c
** Creation Date : Fri 13 Oct 2017 04:13:10 PM IST
** Last Modified : Fri 13 Oct 2017 08:09:25 PM IST
** Compiler : gcc
** Author : Manoj Kumar Patra, Asst. Professor
** Organization : Vignan University, Guntur, India.
**
**=========================================================================================*/
#include<stdio.h>
void DepthFirstSearch(int);
int graph[100][100],visited[100],n;
void main()
{
int i,j;
printf("Enter total number of vertices in the graph: ");
scanf("%d",&n);
printf("\nEnter adjecency matrix of the graph:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&graph[i][j]);
}
printf("\n");
}
//initially mark all verteces as unvisited
printf("\nThe adjecency matrix of the graph is:\n");
printf("= = = = = = = = = = = = = = = = = = = =\n");
for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
{
printf("%d\t",graph[i][j]);
}
printf("\n");
}
printf("= = = = = = = = = = = = = = = = = = = =\n");
for(i=0;i<n;i++)
visited[i]=0;
printf("\nVisited Sequence: \n");
DepthFirstSearch(0);
printf("\n\n");
}
void DepthFirstSearch(int i)
{
int stack[n],top=-1;
int j, curr;
printf("V%d\t",i);
visited[i]=1;
stack[++top]=i;
while(top != -1)
{
curr=stack[top];
for(j=0;j<n;j++)
{
if(visited[j]==0 && graph[i][j]==1)
{
stack[++top]=j;
DepthFirstSearch(stack[top]);
}
}
top--;
}
}
OutPut:
manoj@ubuntu:~$ gcc dfs_stack.c -o dfs_stack
manoj@ubuntu:~$ ./dfs_stack
Enter total number of vertices in the graph: 5
Enter adjecency matrix of the graph:
0
1
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
The adjecency matrix of the graph is:
= = = = = = = = = = = = = = = = = = = =
0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 0
0 1 0 1 0
= = = = = = = = = = = = = = = = = = = =
Visited Sequence: V0 V1 V3 V2 V4
manoj@ubuntu:~$
No comments:
Post a Comment