# 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 – first search is the same as that for breadth first search except in the ordering of the nodes.

- Place the starting node s 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 step 2.

**Example**

**Source Code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | #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 – 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(

*b*). It is less demanding in space requirements, however, since only the path form the starting node to the current node needs to be stored. Therefore, if the depth cutoff is^{d}*d*, the space complexity is just O(*d*).
error in line 121. should be if(k==required)

Error corrected … thanking for your help

Line 123: i > 0, otherwise segfaults.

In line 26-30 why are you allocating memory twice using both malloc as well as new for node ptr ?

This code is easy to understand. But I dont know why do people prefer to use malloc() over 'new' for memory allocation.

If you are using C++, then i prefer to use new rather than malloc(). Many C++ programmers prefer to use new.

oh you are right.. the first allocation is actually not needed, it is just to check whether memory is available or not. You can check it using new also. So you can simply omit the memory allocation using malloc.

May be its better to comment that portion and address in comments as alternative way of memory allocation for the sake of clarity for beginners. Also in isConnected function when you do x-1 and y-1 kindly make sure that it lies within the bounds of the array size and doesn't become negative.

Hi

I added the following edges

g.addEdge(1, 3);

g.addEdge(1, 5);

g.addEdge(2, 4);

g.addEdge(2, 5);

g.addEdge(3, 6);

g.addEdge(4, 6);

g.addEdge(4, 7);

g.addEdge(5, 7);

g.addEdge(5, 8);

g.addEdge(6, 9);

g.addEdge(6, 10);

g.addEdge(7, 9);

g.addEdge(8, 9);

g.addEdge(8, 10);

and performed DFS for g.DFS(1, 8);

But my program crashes.. Can you tell me why this is happening? Thanks in advance.

You don't need to code an extra Stack class.There is one already in the C++ STL library though it use's a container adapter. Just include the header file .

http://www.cplusplus.com/reference/stack/stack/ <<— Look here for details

You are right… I have coded from the scratch. But the use of STL library is always recomended.

dear ur selection of egedes r not good for ur code . so kindly chang ur selection of code . thankx

for (i = n; i >= 0 ; –i)

if (isConnected(k, i) && !visited[i]) {

s.push(i);

visited[i] = true;

}

you are visiting every unvisited adjacent of the vertex k in order… this is breadth first , not depth first..in depth first, we go down the tree (for instance, here we would have had to recursively call dfs(i, reqd))…

also in the constructor itself instead of using the nested for loop to set all values to 0 cant we do it in the above for loop itself as:

for (int i = 0; i < n; i++) {

A[i] = new int[n];

// set this row to 0's

memset(A[i], 0, n);

}

Combination of these two lines gives a memory leak:

113 | bool *visited = new bool[n+1];

….

120 | if(x == required) return;

Well this is called c hangover

There is some mistake in concept :

for (i = n; i >= 0 ; –i)

if (isConnected(k, i) && !visited[i])

{

s.push(i);

visited[i] = true;

}

Depth first traversal will need recursion, here code is using method of Breadth first search.

This seems to be BFS rather than DFS.

can i get the opengl DFS code in C

can i get an opengl code for DFS in C language

Implementation using stack STL

/* Algorithm

1. Place the starting node s on the top of the stack.

2. If the stack is empty, return failure and stop.

3. If the element on the stack is goal node g, return success and stop. Otherwise,

4. Remove and expand the first element , and place the children at the top of the stack.

5. Return to step 2.

*/

#include

#include

#include

#include

using namespace std;

struct node

{

int info;

node *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(int i=0; i s;

bool *vis = new bool[n+1];

for(int i=0; i<=n; i++)

vis[i] = false;

s.push(x);

vis[x] = true;

if(x == req) return;

cout<<"Depth first Search starting from vertex";

cout<=0; –i)

if(isConnected(k, i) && !vis[i])

{

s.push(i);

vis[i] = true;

}

}

cout<<endl;

delete [] vis;

}

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;

}

Hey, but you malloc it to test if there's enough memory, then don't free it. So what have you tested? Maybe there was enough memory but there isn't now! You could use placement new with the malloc'ed memory – but better just catch the out of memory exception from the new if it happens!

hai i getting the error while not expanded online functions in searching techniques techniques program using c++(linear search,binary search)

output does not show on the compiler..

output appear for few seconds and then disappear..

compiler dosent show the output…

screen is displayed just 1 second and dissaper plz help me

type:

system("pause");

between line 138 and 139, so just above the return statement of main.

This will make the cmd window wait for you to hit the any key before disappearing and ending the program.

output is not displaying on borland turboC . is there any problem with using the differnt compilers