BFS and DFS are the two most prevalent strategies to traverse a graph. Both BFS and DFS are inefficient when dealing with a Tree (or Graph) of enormous height and width for the following reasons.
1. DFS explores nodes in this order: one near to the root, then the next adjacent. The difficulty with this method is that if a node is near to the root but not in the first few subtrees searched by DFS, DFS will get at that node late. DFS may also fail to discover the shortest path to a node (in terms of a number of edges).
2. BFS progresses level by level, but it takes up more room. DFS requires O(d) space, where d is the depth of the tree, but BFS requires O(n) space, where n is the number of nodes in the tree (Why?). Note that the last level of the tree can have approximately n/2 nodes, and the second last level can have around n/4 nodes, and in BFS, we must queue each level one by one).
IDDFS combines the space-efficiency of depth-first search with the speed of breadth-first search (for nodes closer to root).
Starting with an initial value, IDDFS calls DFS for various depths. DFS is not allowed to go beyond a certain depth in any call. So, in a nutshell, we do DFS in a BFS manner.
It's worth noting that we go to top-level nodes many times. The final (or maximum depth) level is visited once, twice for the second last level, and so on. It may appear to be costly, but it turns out to be less so because the majority of nodes in a tree are found at the bottom level. As a result, it doesn't matter if the top levels are visited several times.
IDDFS calls DFS for different depths starting from an initial value. In every call, DFS is restricted from going beyond the given depth. So basically we do DFS in a BFS fashion.
// Returns true if target is reachable from
// src within max_depth
bool IDDFS(src, target, max_depth)
for limit from 0 to max_depth
if DLS(src, target, limit) == true
bool DLS(src, target, limit)
if (src == target)
// If reached the maximum depth,
// stop recursing.
if (limit <= 0)
foreach adjacent i of src
if DLS(i, target, limit?1)
The iterative deepening depth-first search algorithm is a mix of BFS and DFS. Although IDDFS isn't directly utilised in many computer science applications, it is used to search for data in infinite space by incrementally increasing the depth limit. This is quite valuable, as it has applications in AI and the rapidly growing data sciences business.
Author : Dwayne Smith
University : University of Michigan
Designation : Computer Science Professor and Programming Assignment Examiner