### What is Depth First Search?

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes.

For example, in the above graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. Depth First Traversal of the following graph is 2, 0, 1, 3.

[adinserter block=”1″]For Breadth First Search implementation –> see here

Download: dfs.cpp

### Program to implement Depth First Search C++:

#include <iostream> using namespace std; int c = 0; struct node { char data; int st_time, lv_time; }*p = NULL, *r = NULL; struct stack { node *pt; stack *next; }*top = NULL, *q = NULL, *np= NULL; // Insert Node void push(node *ptr) { np = new stack; np->pt = ptr; np->next = NULL; if (top == NULL) { top = np; } else { np->next = top; top = np; } } node *pop() { if (top == NULL) { cout<<"underflown"; } else { q = top; top = top->next; return(q->pt); delete(q); } } void create(int a[], int b[][7], int i, int j) { c++; p = new node; cout<<"enter data for new noden"; cin>>p->data; p->st_time = c; cout<<"start time for "<<p->data<<" is "<<c<<endl; a[i] = 1; push(p); while (j < 7) { if ((b[i][j] == 0) || (b[i][j] == 1 && a[j] == 1)) { j++; } else if (b[i][j] == 1 && a[j] == 0) { create(a,b,j,0); } } r = pop(); cout<<"node poppedn"; c++; cout<<"leave time for "<<r->data<<" is "<<c<<endl; } //Main Function int main() { int a[7]; for (int i = 0; i < 7; i++) { a[i] = 0; } int b[7][7]; cout<<"enter values for adjacency matrix"<<endl; for (int i = 0 ; i < 7 ; i++ ) { cout<<"enter values for "<<(i+1)<<" row"<<endl; for (int j = 0; j < 7; j++) { cin>>b[i][j]; } } create(a,b,0,0); return 0; }

### OUTPUT:

enter values for adjacency matrix enter values for 1 row 0 1 1 0 0 1 1 enter values for 2 row 1 0 0 0 0 0 0 enter values for 3 row 1 0 0 0 0 0 1 enter values for 4 row 0 0 0 0 1 1 0 enter values for 5 row 0 0 0 1 0 1 1 enter values for 6 row 1 0 0 1 1 0 0 enter values for 7 row 1 0 1 0 1 0 0 enter data for new node a start time for a is 1 enter data for new node b start time for b is 2 node popped leave time for b is 3 enter data for new node c start time for c is 4 enter data for new node d start time for d is 5 enter data for new node e start time for e is 6 enter data for new node f start time for f is 7 enter data for new node g start time for g is 8 node popped leave time for g is 9 node popped leave time for f is 10 node popped leave time for e is 11 node popped leave time for d is 12 node popped leave time for c is 13 node popped leave time for a is 14