Friday, 27 October 2017

Depth First Search algorithm in C++ language:

In Depth-First search algorithm we progresses by exploring the starting vertex of the given graph and then moving deeper and deeper until the goal vertex  is found or you can say until the dead vertex ( means the vertex having no child vertex further to process) is found. When we encountered with a dead vertex, then algorithm backtrack until the most recent vertex that has not been completely explored. 
For Depth-First search algorithm we use STACK data structure for implementation. 

Application of Depth - First Search algorithm:

1. It is used to find the path between two specified node of any unleveled graph.
2. It is used to find the path between two specified node of any leveled graph.
3. It is used to find whether the graph is connected or not connected.
4. It is used for computing the spanning tree of any connected graph.

For the implementation of C++ code and then find the output we input the given graph (vertices and edges) as input.


Program Code:
#include<iostream>
#include<stdlib.h>
using namespace std;
int graph[10][10];
int i, j, k, vertices;
int stack[10],top;
int vertex, edges;
int visit[10],visited[10]; 
int main()
{
cout <<"Enter number of vertices : ";
cin >> vertices;
cout<<endl;
cout <<"Enter number of edges : ";
cin >> edges;
cout<<endl;
cout <<" Enter number of edges with start & end vertex :";
for(k=1; k<= edges; k++)
{
cin>>i>>j;
graph[i][j] = 1;
cout<<endl;
}
cout <<"Enter initial vertex for the graph traversal : ";
cin >>vertex;
cout<<endl;
cout <<"The order of visited vertices : ";
cout << vertex <<" ";
visited[vertex] = 1;
k=1;
while(k < vertices)
{
for(j = vertices; j >= 1; j--)
if(graph[vertex][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stack[top]=j;
top++;
}
vertex = stack[--top];
cout<<vertex << " ";
k++;
visit[vertex]=0; visited[vertex]=1;
}
}

The program output is tested on www.jdoodle.com
Note:  we are considering above graph as input

Output: 
Enter number of vertices : 6
Enter number of edges : 7
Enter number of edges with start & end vertex :
1  5
1  2
2  5
2  3
3  4
4  5
4  6
Enter initial vertex for the graph traversal : 1

The order of visited vertices : 1 2 3 4 6 5 


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput