Depth First Search in C++

Depth First Search, or simply DFS, was first investigated by French Mathematician Charles Pierre Trémaux in 19^th century as a technique to solve mazes. Starting from the root node, DFS leads the target by exploring along each branch before backtracking.

During the course of searching, DFS dives downward into the tree as immediately as possible. It approaches the target node by expanding and generating the offspring/child recently expanded node. The process continues till the target is found or a cutoff depth is encountered. This same approach is used in this program source code for Depth First Search in C++.

If the selected branch doesn’t contain the target, the program backtracks into next branch. In case of leaf node and cutoff point, the program backtracks the most recently expanded node.

As per theoretical computer science, the time and space analysis of Depth First Search is essential which ultimately depends on the type of its field of application. Furthermore, whenever the entire graph is to be traversed with time O(|V|+|E|) linear with size of graph, DFS is preferred. It is believed that in the worst condition, stack of some vertices is stored in space O(|V|).

Algorithm of Depth First Search:

The algorithm of Depth First Search is almost similar to that of Breadth First Search. It also uses the queue data structure but the arrangement of node is different. The algorithm of DFS follows the following steps:

1. Put root node ‘r’ on the top of the stack.
2. Examine whether the stack is empty or not
   • If the stack is found to be void, return the failure and stop
   • Else proceed forward.
3. If the first element of the stack is the searched or target node’t’, return it as success. Otherwise,
4. Proceed ahead with expansion and removal of first element. The generates of first element should be placed at the top of stack.
5. Go back to step 2.

Pseudo Code:

Consider a graph ‘g’ with vertex ‘v’.  This can be designated as DFS (g,v). ‘v’ labeled as discovered are assumed to be output. There are two ways of presenting the Pseudo Code for DFS: using recursion and without recursion.

Without using Recursion:

1. Consider a stack ‘s’
2. push(v)
3. do
   while s is empty
4. vßpop
5. if v is found to be not labeled as undiscovered
   label it
6. for all edges between ‘v’ and ‘ w’ in g.adjcentEdge(v) do
   s.push(w)

By using Recursion:

1. Mark ‘v’ as discovered.
2. For edges between ‘v’ to ‘w’ within g.adjacentEdges(v) do
3. If any vertex ‘w’ is found to be not labeled as discovered then,
4. Call Recursive Function DFS(g,v).

Source Code for Depth First Search in C++:

#include <iostream>
#include <ctime>
#include <malloc.h>
using namespace std;
struct nod
{
    int info;
    struct nod *next;
};

class stak
{
    struct nod *top;
    public:
        stak();
        void push(int);
        int pop();
        bool isEmpty();
        void display();
};

stak::stak()
{
    top = NULL;
}

void stak::push(int data)
{
    nod *p;
    if((p=(nod*)malloc(sizeof(nod)))==NULL){
        cout<<"Memory Exhausted";
        exit(0);
    }
    p = new nod;
    p->info = data;
    p->next = NULL;
    if(top!=NULL)
    {
        p->next = top;
    }
    top = p;
}

int stak::pop()
{
    struct nod *temp;
    int value;
    if(top==NULL){
        cout<<"\nThe stak is Empty"<<endl;
    }
    else
    {
        temp = top;
        top = top->next;
        value = temp->info;
        delete temp;
    }
    return value;
}

bool stak::isEmpty()
{
    return (top == NULL);
}

void stak::display()
{
    struct nod *p = top;
    if(top==NULL){
        cout<<"\nNothing to Display\n";
    }
    else
    {
        cout<<"\n The contents of stak\n";
        while(p!=NULL){
            cout<<p->info<<endl;
            p = p->next;
        }
    }
}

class Graph
{
    private:
        int n;
        int **A;
    public:
        Graph(int siz = 2);
        ~Graph();
        bool isConnected(int, int);
        void addEdge(int x, int y);
        void DFS(int , int);
};

Graph::Graph(int siz)
{
    int i, j;
    if (siz < 2) n = 2;
    else n = siz;
    A = new int*[n];
    for (i = 0; i < n; ++i)
        A[i] = new int[n];
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            A[i][j] = 0;
}

Graph::~Graph()
{
    for (int i = 0; i < n; ++i)
    delete [] A[i];
    delete [] A;
}

bool Graph::isConnected(int x, int y)
{
    return (A[x-1][y-1] == 1);
}

void Graph::addEdge(int x, int y)
{
    A[x-1][y-1] = A[y-1][x-1] = 1;
}

void Graph::DFS(int x, int required)
{
    stak s;
    bool *visited = new bool[n+1];
    int i;
    for(i = 0; i <= n; i++)
        visited[i] = false;
    s.push(x);
    visited[x] = true;
    if(x == required) return;
    cout << " Depth first Search starting from vertex ";
    cout <<  x << " : " << endl;
    while(!s.isEmpty())
    {
        int k = s.pop();
        if(k == required) break;
        cout<<k<<" ";
        for (i = n; i >= 0 ; --i)
            if (isConnected(k, i) && !visited[i])
            {
                s.push(i);
                visited[i] = true;
            }
    }
    cout<<endl;
    delete [] visited;
}

int main()
{
    Graph g(8);
    g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(1, 4);
    g.addEdge(2, 5); g.addEdge(2, 6); g.addEdge(4, 7);
    g.addEdge(4, 8);
    g.DFS(1, 4);
    return 0;
}

In this program, malloc() has been used instead of new for memory allocation. Near lines 29-36, the memory has been allocated twice using both malloc and node pointer. The first allocation is not compulsory; it is just to check the memory. It can be checked using “new” as well.

Also see,
Breadth First Search in C++
Dijkstra’s Algorithm Program
Gaussian Filter Generation in C++

The source code of Depth First Search in C++ is simple to understand and completely error-free. If you have any queries, suggestions or feedbacks regarding this C++ tutorial, mention/discuss them in the comments section below.

You can find more C++ Tutorials here.