OpenSource Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we are going to discuss about the Iterative Deepening Search Technique. It is also, known as Iterative Deepening DepthFirst Search ( IDDFS) and is a modification of Depth First Search and Depth Limited Search.
Table of contents:
 Recap of DFS and BFS
 Drawbacks of DFS and BFS
 DepthLimited Search (DLS)
 Implementation of DLS
 Iterative Deepening DepthFirst Search ( IDDFS)
 Implementation of IDDFS
 Time Complexity
 Comparison between DFS, DLS and IDDFS
 Conclusion
The main goal of any graph search traversal technique is to find the shortest possible path between a source node and a goal node.
You are probably familiar with the DepthFirst Search and the BreadthFirst Search technique for graph traversal.
Let's revisit the concepts quickly:
1. DFS and BFS
DepthFirst Search is a graph traversal technique that explores the graph depthwise. It starts with a source node, explores one of its neighboring node and then explores the neighbor of this node. Once all the neighbor nodes of the current node are explored, the algorithm backtracks and continues this process until it has reached the desired node or explored all the nodes in the given graph at least once.
To know more about DFS, refer to DFS implementation
BreadthFirst Search is a graph traversal technique that explores the graph layerwise. It starts with a source node and explores all its adjacent nodes before moving to the next layer.
The following picture illustrates the DFS and BFS graph traversal:
2. Drawbacks of DFS and BFS
Both DFS and BFS have certain limitations as highlighted in the table below:
Consider the case of a search tree with an unknown (infinite) depth
Using DFS technique, we might not ever reach the goal node. DFS may get stuck in an infinite loop.
To overcome the shortcomings of DFS, we may use the depthlimited search technique.
3. Depth Limited Search
A depthlimited search (DLS) algorithm is similar to DFS with a depth limit i.e it only explores the nodes up to a finite depth, say d. The algorithm treats the nodes at depth d, as if they don't have any successor nodes.
Consider a case where depthlimit d=2
The Depth Limited Search arrives at the goal node faster if the goal node is at a depth equal to d, i.e in shortest possible path.
If the goal node is at a depth lesser than d, the suboptimal path may be arrived at whereas in the case of depth being greater than d, the goal node will be unreachable.

Depthlimited search overcomes the drawback of the infinite path in DFS. [Note that DFS is a special case where the depth limit is infinity]

DLS fails in the following two cases:
 The goal node is beyond the depth limit.
 There is no path as the goal node does not exist in the graph/tree.
4. Implementation of DepthLimited Search
Given below is the recursive implementation of DLS.
The search terminates if limit<0 or if the goal node does not exist within the depth limit.
#include <bits/stdc++.h>
using namespace std;
class Graph {
public:
map<int, vector<int>> adj;
void addEdge(int v, int w)
{
adj[v].push_back(w);
}
int DLS(int v, int g,int l);
};
int Graph::DLS(int v,int goal,int limit)
{
if(v==goal)
{
return 1;
}
for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
{
if(limit1>=0)
{
if(DLS(*i,goal,limit1)!=1)
return 1;
}
}
return 1;
}
int main()
{
int goal,limit;
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
g.addEdge(3, 7);
cout<<"Enter the goal node: ";
cin>>goal;
cout<<"Enter depth limit: ";
cin>>limit;
int res=g.DLS(0,goal,limit);
if(res==1)
cout<<"Goal node not found !\n";
else
cout<<"Goal node found within depth limit";
return 0;
}
5. Iterative Deepening DepthFirst Search (IDDFS)
The Iterative Deepening DepthFirst Search (or Iterative Deepening search) algorithm, repeatedly applies depthlimited search with increasing limits.
It gradually increases limits from 0,1,...d, until the goal node is found.
It terminates in the following two cases:
 When the goal node is found
 The goal node does not exist in the graph/tree.
5. Implementation of IDDFS
#include <bits/stdc++.h>
using namespace std;
class Graph {
public:
map<int, vector<int>> adj;
void addEdge(int v, int w)
{
adj[v].push_back(w);
}
int DLS(int v, int g,int l);
int IDDFS(int v,int g,int l);
};
int Graph::DLS(int v,int goal,int limit)
{
if(v==goal)
{
return 1;
}
for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
{
if(limit1>=0)
{
cout<<*i<<" ";
if(DLS(*i,goal,limit1)!=1)
return 1;
}
}
return 1;
}
int Graph::IDDFS(int src, int goal, int limit)
{
for(int i=0;i<=limit;i++)
{
cout<<"Iteration "<<i<<": "<<src<<" ";
if(DLS(src,goal,i)==1)
{
return 1;
}
cout<<"\n";
}
return 1;
}
int main()
{
Graph gp;
gp.addEdge(0, 1);
gp.addEdge(0, 2);
gp.addEdge(1, 3);
gp.addEdge(1, 4);
gp.addEdge(2, 5);
gp.addEdge(2, 6);
gp.addEdge(3, 7);
gp.addEdge(5, 8);
gp.addEdge(6, 9);
int src=0, goal=9, limit=3;
if(gp.IDDFS(src,goal,limit)==1)
cout<<"\nGoal node found within depth limit";
else
cout<<"Goal node not found !\n";
return 0;
}
Output
Iteration 0: 0
Iteration 1: 0 1 2
Iteration 2: 0 1 3 4 2 5 6
Iteration 3: 0 1 3 7 4 2 5 8 6 9
Goal node found within depth limit
IDDFS overcomes the drawbacks of dfs and bfs discussed previously. It combines the spaceefficiency of DFS  O(bd) and timeefficiency of BFS algorithm  O(b^d).
7. Time Complexity of IDDFS
Branching factor (b): The average number of children of each node.
If b is the branching factor, and d is the depth of the goal node or the depth at which the iteration of IDDFS function terminates, the time complexity is O(b^d) and space complexity is O(bd).
Explanation:
The total number of nodes generated in the worst case is
b(d) + b^2(d1) + .......b^d(1).
Comparison between DFS,DLS and IDDFS
The criteria for evaluating the performance of a search algorithm are completeness, optimality, time and space complexity.
Complete  A search algorithm is complete if it guarantees to find the goal node if it exists.
Optimal  A search algorithm is optimal if it finds the shortest path from the source node.
Time Complexity  The time taken to complete the search.
Space Complexity  The memory requirement of the search algorithm.
Here l = depthlimit, d = depth of the goal node, m = depth of the search tree/graph.
Conclusion
With this article at OpenGenus, you now have a complete understanding of the Iterative Deepening DepthFirst Search (IDDFS) algorithm, and how it compares with the DepthFirst Search (DFS), BreadthFirst Search (BFS) and DepthLimited Search (DLS).