Program to implement Depth First Search C++

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.

depth first search c++

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

 

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

Leave a Reply