**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.*

*#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