Java Program to Implement Iterative Deepening

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.

import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
 
public class IterativeDeepening
{
    private Stack<Integer> stack;
    private int numberOfNodes;
    private int depth;
    private int maxDepth;
    private boolean goalFound = false;
 
    public IterativeDeepening()
    {
        stack = new Stack<Integer>();
    }
 
    public void iterativeDeeping(int adjacencyMatrix[][], int destination)
    {
        numberOfNodes = adjacencyMatrix[1].length - 1;
        while (!goalFound)
        {
            depthLimitedSearch(adjacencyMatrix, 1, destination);
            maxDepth++;
        }
        System.out.println("\nGoal Found at depth " + depth);
    }
 
    private void depthLimitedSearch(int adjacencyMatrix[][], int source, int goal)
    {
        int element, destination = 1;
        int[] visited = new int[numberOfNodes + 1];
        stack.push(source);
        depth = 0;
        System.out.println("\nAt Depth " + maxDepth);
        System.out.print(source + "\t");
 
        while (!stack.isEmpty())
        {
            element = stack.peek();
            while (destination <= numberOfNodes)
            {
                if (depth < maxDepth)
                {
                    if (adjacencyMatrix[element][destination] == 1)
                    {
                        stack.push(destination);
                        visited[destination] = 1;
                        System.out.print(destination + "\t");
                        depth++;
                        if (goal == destination)
                        { 
                            goalFound = true;
                            return;
                        }
                        element = destination;
                        destination = 1;
                        continue;
                    }
                } else 
                {
                    break;
                }
                destination++;
            }
            destination = stack.pop() + 1;
            depth--;
        }
    }
 
    public static void main(String... arg)
    {
        int number_of_nodes, destination;
        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 destination for the graph");
            destination = scanner.nextInt();
 
            IterativeDeepening iterativeDeepening = new IterativeDeepening();
            iterativeDeepening.iterativeDeeping(adjacency_matrix, destination);
        }catch (InputMismatchException inputMismatch)
        {
            System.out.println("Wrong Input format");
        }
        scanner.close();
    }
}
$javac IterativeDeepening.java
$java IterativeDeepening
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

Related posts:

Spring Boot Tutorial – Bootstrap a Simple Application
Intersection of Two Lists in Java
Spring Boot - Internationalization
Quick Guide to Spring Bean Scopes
Java Program to Implement WeakHashMap API
Java Program to Solve Knapsack Problem Using Dynamic Programming
Spring Boot - Logging
Hướng dẫn Java Design Pattern – Interpreter
Java Program to Check whether Directed Graph is Connected using DFS
So sánh HashMap và Hashtable trong Java
String Operations with Java Streams
Exploring the New Spring Cloud Gateway
Predicate trong Java 8
An Introduction to ThreadLocal in Java
Lập trình đa luồng trong Java (Java Multi-threading)
Spring Security 5 for Reactive Applications
Jackson – Decide What Fields Get Serialized/Deserialized
Java Program to Search for an Element in a Binary Search Tree
Converting Java Date to OffsetDateTime
Properties with Spring and Spring Boot
Java Program to Give an Implementation of the Traditional Chinese Postman Problem
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm
How to Manually Authenticate User with Spring Security
Lớp Properties trong java
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Apache Commons Collections OrderedMap
Java Program to Check Whether an Undirected Graph Contains a Eulerian Path
Composition, Aggregation, and Association in Java
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
Spring Webflux and CORS
Java Program to Perform Addition Operation Using Bitwise Operators