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
 

Java Implementation of Depth-limited Search

This Java program,Implements Depth Limited Search.Like the normal depth-first search, depth-limited search is an uninformed search. It works exactly like depth-first search, but avoids its drawbacks regarding completeness by imposing a maximum limit on the depth of the search. Even if the search could still expand a vertex beyond that depth, it will not do so and thereby it will not follow infinitely deep paths or get stuck in cycles. Therefore depth-limited search will find a solution if it is within the depth limit, which guarantees at least completeness on all graphs.

Here is the source code of the Java program to implement depth limited search. 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:

run:

Enter the number of nodes in the graph

4

Enter the adjacency matrix

0 1 1 0

0 0 1 1

0 0 1 0

1 0 0 1

Enter the startNode for the graph

1

The Depth limited Search Traversal of Max Depth 3 is

1 at depth 0

2 at depth 1

3 at depth 2

4 at depth 2

BUILD SUCCESSFUL (total time: 35 seconds)

Depth First Search Algorithm Java Implementation

Depth First Search (DFS): always expands the deepest node in the current fringe of the search tree. Fringe is a LIFO queue (Stack).

This Java program,performs the DFS traversal on the given graph represented by a adjacency matrix.the DFS traversal makes use of an stack.

Here is the source code of the Java program to perform the dfs traversal. The Java program is successfully compiled and run on a Linux and WIndows system. 

package uninformed;

/**

 *

 * @author sam

 */

import java.util.InputMismatchException;

import java.util.Scanner;

import java.util.Stack;

public class DFS

{

    private Stack<Integer> stack;

    public DFS() 

    {

        stack = new Stack<Integer>();

    }

    public void dfs(int adjacency_matrix[][], int source)

    {

        int number_of_nodes = adjacency_matrix[source].length - 1;

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

        int element = source;

        int i = source, goalnode;

        Scanner scanner = new Scanner(System.in);

        System.out.print("ENTER THE GOAL NODE: ");

        goalnode = scanner.nextInt();

        System.out.print(element + "\t");

        visited[source] = 1;

        stack.push(source);

        while (!stack.isEmpty())

        {

            element = stack.peek();

            i = element;

    while (i <= number_of_nodes)

    {

              if (adjacency_matrix[element][i] == 1 && visited[i] == 0)

        {

                    stack.push(i);

                    visited[i] = 1;

                    element = i;

                    i = 1;

                    System.out.print(element + "\t");

            continue;

                }

                if(i == goalnode) return;

                i++;

    }

            stack.pop();

        }

    }

    public static void main(String...arg)

    {

        int number_of_nodes, source;

        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 source for the graph");

            source = scanner.nextInt(); 

            System.out.println("The DFS Traversal for the graph is given by \n");

            DFS dfs = new DFS();

            dfs.dfs(adjacency_matrix, source);

        }catch(InputMismatchException inputMismatch)

        {

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

        }

        scanner.close();

    }

}