* This is an important search algorithm in artificial intelligence and robotics.
* We learned BFS is very good for local searches BUT it is very very memory consuming.
* We have to keep pointers and references in a queue.
* DFS can be implemented easily with recursion BUT it keeps going further and futher.
* DFS is very memory friendly.
* It inherits the advantages of both DFS and BFS.

* IDDFS visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.
* We keep going deeper and deeper in the given tree with DFS on each iteration.
* The time complexity of IDDFS in well-balanced trees works out to be the same as Depth-first search ie O(V+E).
* The major disadvantage here is we keep recomputing the same problem over and over again. However even after this, the time complexity of the algo is only marginally greater than DFS.

Look at the following example:

Here we consider the Depth parameter as 0. Hence only the first node will be visited:
Next, for Depth parameter : 1

For Depth parameter: 2

Codes of the Java files included in the program are given below:

Node.java

In [ ]:
package iddfs;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author ANIRUDDHA
 */

//Node in the tree
public class Node {
    
    private String name;
    private int depthLevel = 0;
    private List<Node> adjacenciesList;
    
	//Constructor
    public Node(String name){
        this.name = name;
        this.adjacenciesList = new ArrayList<Node>();
    }
    
    public void addNeighbour(Node node){
        this.adjacenciesList.add(node);
    }

	//Getters and Setters
    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getDepthLevel() {
        return depthLevel;
    }

    public void setDepthLevel(int depthLevel) {
        this.depthLevel = depthLevel;
    }

    public List<Node> getAdjacenciesList() {
        return adjacenciesList;
    }
    
	//Override the toString method to get the path
    public String toString(){
        return this.name;
    }
    
}

IDDFS.java

In [ ]:
package iddfs;

import java.util.Stack;

/**
 *
 * @author ANIRUDDHA
 */

// Iterative Deepening DFS algorithm
public class IDDFS {
    
    private Node targetNode;
    private boolean isTargetFound;
    
    public IDDFS(Node targetNode){
        this.targetNode = targetNode;
    }

    
    // Running the Search
    public void runDeepningSearch(Node startNode){
        
        int depth = 0;
        
        while(!isTargetFound){
            System.out.println();
            dfs(startNode,depth);
            depth++;
        }
    }

    // DFS using stack
    private void dfs(Node startNode, int depth) {
        
        Stack<Node> stack = new Stack<>();
        startNode.setDepthLevel(0);
        stack.push(startNode);
        
        while(!stack.isEmpty()){
            
            //Pop the actual vertices for display
            Node actualNode = stack.pop();
            System.out.print(actualNode+" ");
            
            // Check if we found the target node
            if(actualNode.getName().equals(this.targetNode.getName())){
                System.out.println("\nNode is found... ");
                this.isTargetFound = true; // break the while loop
                return;
            }
            
            // Continue if the target node is deeper than the current set depth
            if(actualNode.getDepthLevel() >= depth){
                continue;
            }
            
            for(Node node: actualNode.getAdjacenciesList()){
                node.setDepthLevel(actualNode.getDepthLevel()+1); // Incrementing the DepthLevel;
                stack.push(node);
            }
            
        }
    }

}

Main.java

In [ ]:
package iddfs;

/**
 *
 * @author ANIRUDDHA
 */
public class Main {
    public static void main(String[] args) {
        
        // Create nodes
        Node node1 = new Node("A");
        Node node2 = new Node("B");
        Node node3 = new Node("C");
        
        //Add neighbours to nodes
        node1.addNeighbour(node2);
        node2.addNeighbour(node3);
        
        // Running the IDDFS
        //IDDFS iddfs = new IDDFS(node1);
        IDDFS iddfs = new IDDFS(node3);
        iddfs.runDeepningSearch(node1);
        
    }
    
}

Output of the program is :

A 
A B 
A B C 
Node is found... 

You can download the complete source code here : Source Code