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.

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