Java Program to Implement 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.

  1. import java.util.InputMismatchException;
  2. import java.util.Scanner;
  3. import java.util.Stack;
  4.  
  5. public class DepthLimitedSearch
  6. {
  7.     private Stack<Integer> stack;
  8.     private int numberOfNodes;
  9.     private static final int MAX_DEPTH = 3;
  10.  
  11.     public DepthLimitedSearch(int numberOfNodes)
  12.     {
  13.         this.numberOfNodes = numberOfNodes;
  14.         this.stack = new Stack<Integer>();
  15.     }
  16.  
  17.     public void depthLimitedSearch(int adjacencyMatrix[][], int source)
  18.     {
  19.         int visited[] = new int[numberOfNodes + 1];
  20.         int element, destination;
  21.         int depth = 0;
  22.  
  23.         System.out.println(source + " at depth " + depth);
  24.         stack.push(source);
  25.         visited[source] = 1;
  26.         depth = 0;
  27.  
  28.         while (!stack.isEmpty())
  29.         {
  30.             element = stack.peek();
  31.             destination = element;
  32.             while (destination <= numberOfNodes)
  33.             {
  34.                 if (depth < MAX_DEPTH)
  35.                 {
  36.                     if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)
  37.                     {
  38.                         stack.push(destination);
  39.                         visited[destination] = 1;
  40.                         depth++;
  41.                         System.out.println(destination + " at depth " + depth);
  42.                         element = destination;
  43.                         destination = 1;
  44.                     }
  45.                 }
  46.                 else
  47.                 {
  48.                     return;
  49.                 }
  50.                 destination++;
  51.             }
  52.             stack.pop();
  53.             depth--;
  54.         }
  55.     }
  56.  
  57.     public static void main(String... arg)
  58.     {
  59.         int number_of_nodes, source;
  60.         Scanner scanner = null;
  61.         try
  62.         {
  63.             System.out.println("Enter the number of nodes in the graph");
  64.             scanner = new Scanner(System.in);
  65.             number_of_nodes = scanner.nextInt();
  66.  
  67.             int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  68.             System.out.println("Enter the adjacency matrix");
  69.             for (int i = 1; i <= number_of_nodes; i++)
  70.                 for (int j = 1; j <= number_of_nodes; j++)
  71.                     adjacency_matrix[i][j] = scanner.nextInt();
  72.  
  73.             System.out.println("Enter the source for the graph");
  74.             source = scanner.nextInt();
  75.  
  76.             System.out.println("The Depth limited Search Traversal of Max Depth 3 is");
  77.             DepthLimitedSearch depthLimitedSearch = new DepthLimitedSearch(number_of_nodes);
  78.             depthLimitedSearch.depthLimitedSearch(adjacency_matrix, source);
  79.  
  80.         } catch (InputMismatchException inputMismatch)
  81.         { 
  82.             System.out.println("Wrong Input format");
  83.         }
  84.         scanner.close();
  85.     }
  86. }


$javac DepthLimitedSearch.java
$java DepthLimitedSearch
Enter the number of nodes in the graph
5
Enter the adjacency matrix
0 1 0 0 0 
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
Enter the source for the graph
1
The Depth limited Search Traversal  of Max Depth 3 for the graph is given by 
1 at depth 0
2 at depth 1
3 at depth 2
4 at depth 3

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.