Java Implementation of Iterative Deepening Search

This Java program,Implements Iterative Deepening.Iterative deepening depth-first search(IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches , the depth of the shallowest goal state. IDDFS is equivalent to breadth-first search, but uses much less memory; on each iteration, it 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.

Here is the source code of the Java program implements iterative deepening. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

package Search_Algorithm;

/**

 *

 * @author sam

 */

import java.util.InputMismatchException;

import java.util.Scanner;

import java.util.Stack;

public class DepthLimitedSearch

{

    private Stack<Integer> stack;

    private int numberOfNodes;

    private static final int MAX_DEPTH = 3;

    public DepthLimitedSearch(int numberOfNodes)

    {

        this.numberOfNodes = numberOfNodes;

        this.stack = new Stack<Integer>();

    }

    public void depthLimitedSearch(int adjacencyMatrix[][], int startNode)

    {

        int visited[] = new int[numberOfNodes + 1];

        int element, destination;

        int depth = 0;

        System.out.println(startNode + " at depth " + depth);

        stack.push(startNode);

        visited[startNode] = 1;

        depth = 0;

        while (!stack.isEmpty())

        {

            element = stack.peek();

            destination = element;

            while (destination <= numberOfNodes)

            {

                if (depth < MAX_DEPTH)

                {

                    if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)

                    {

                        stack.push(destination);

                        visited[destination] = 1;

                        depth++;

                        System.out.println(destination + " at depth " + depth);

                        element = destination;

                        destination = 1;

                    }

                }

                else

                {

                    return;

                }

                destination++;

            }

            stack.pop();

            depth--;

        }

    }

    public static void main(String... arg)

    {

        int number_of_nodes, startNode;

        Scanner scanner = null;

        try

        {

            System.out.println("Enter the number of nodes in the graph");

            scanner = new Scanner(System.in);

            number_of_nodes = scanner.nextInt();

            int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];

            System.out.println("Enter the adjacency matrix");

            for (int i = 1; i <= number_of_nodes; i++)

                for (int j = 1; j <= number_of_nodes; j++)

                    adjacency_matrix[i][j] = scanner.nextInt();

            System.out.println("Enter the startNode for the graph");

            startNode = scanner.nextInt();

            System.out.println("The Depth limited Search Traversal of Max Depth 3 is");

            DepthLimitedSearch depthLimitedSearch = new DepthLimitedSearch(number_of_nodes);

            depthLimitedSearch.depthLimitedSearch(adjacency_matrix, startNode);

 } catch (InputMismatchException inputMismatch)

        { 

            System.out.println("Wrong Input format");

        }

        scanner.close();

    }

}

THE OUTPUT:

Enter the number of nodes in the graph
7
Enter the adjacency matrix
0 1 1 0 0 0 0 
0 0 0 1 1 0 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
Enter the destination for the graph
7

At Depth 0
1	
At Depth 1
1	2	3	
At Depth 2
1	2	4	5	3	6	7	
Goal Found at depth 2