Depth First Search in C++ Algorithm and Source Code

Basic Theory

Depth – first searches are performed by diving downward into a tree as quickly as possible. It does this by always generating a child node from the most recently expanded node, then generating that child’s children, and so on until a goal is found or some cutoff depth point d is reached. If a goal is not found when a leaf node is reached or at the cutoff point, the program backtracks to the most recently expanded node and generates another of its children. This process continues until a goal is found or failure occurs.

Algorithm

• An algorithm for the depth – the first search is the same as that of breadth first search except in the ordering of the nodes.
• Place the starting nodes on the top of the stack.
• If the stack is empty, return failure and stop.
• If the element on the stack is goal node g, return success and stop. Otherwise,
• Remove and expand the first element , and place the children at the top of the stack.
• Return to step2.

Example

Source Code

#include <iostream>

#include <ctime>

#include <malloc.h> 

using namespace std;

struct node{

int info;

struct node *next;

}; 

class stack{

struct node *top;

public:

stack();

void push(int);

int pop();

bool isEmpty();

void display();

}; 

stack::stack(){

top = NULL;

} 
void stack::push(int data){

node *p;

if((p=(node*)malloc(sizeof(node)))==NULL){

cout<<"Memory Exhausted";

exit(0);

}

p = new node;

p->info = data;

p->next = NULL;

if(top!=NULL){

p->next = top;

}

top = p;

} 
int stack::pop(){

struct node *temp;

int value;

if(top==NULL){

cout<<"\nThe stack is Empty"<<endl;

}else{

temp = top;

top = top->next;

value = temp->info;

delete temp;

}

return value;

} 

bool stack::isEmpty(){

return (top == NULL);

} 
void stack::display(){

struct node *p = top;

if(top==NULL){

cout<<"\nNothing to Display\n";

}else{

cout<<"\nThe contents of Stack\n";

while(p!=NULL){

cout<<p->info<<endl;

p = p->next;

}

}

} 

class Graph {

private:

int n;

int **A;

public:

Graph(int size = 2);

~Graph();

bool isConnected(int, int);

void addEdge(int x, int y);

void DFS(int , int);

}; 
Graph::Graph(int size) {

int i, j;

if (size < 2) n = 2;

else n = size;

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){

stack 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;

}

Complexity

The depth – the first search is preferred over the breadth – first when the search tree is known to have a plentiful number of goals. The time complexity of the depth-first tree search is the same as that for breadth-first, O(bd). It is less demanding in space requirements, however, since only the path from the starting node to the current node needs to be stored. Therefore, if the depth cutoff is d, the space complexity is just O(d).