SHARE
TWEET

Untitled

a guest Mar 24th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //package Artificial_Intelligence.DLS;
  2.  
  3. import java.util.InputMismatchException;
  4. import java.util.Scanner;
  5. import java.util.Stack;
  6.  
  7. public class DepthLimitedSearch
  8. {
  9.     private Stack stack;
  10.     private int numberOfNodes;
  11.     private static final int MAX_DEPTH = 3;
  12.  
  13.     public DepthLimitedSearch(int numberOfNodes)
  14.     {
  15.         this.numberOfNodes = numberOfNodes;
  16.         this.stack = new Stack();
  17.     }
  18.  
  19.     public void depthLimitedSearch(int adjacencyMatrix[][], int source)
  20.     {
  21.         int visited[] = new int[numberOfNodes + 1];
  22.         int element, destination;
  23.         int depth = 0;
  24.  
  25.         System.out.println(source + " at depth " + depth);
  26.         stack.push(source);
  27.         visited[source] = 1;
  28.         depth = 0;
  29.  
  30.         while (!stack.isEmpty())
  31.         {
  32.             element = (int) stack.peek();
  33.             destination = element;
  34.             while (destination <= numberOfNodes)
  35.             {
  36.                 if (depth < MAX_DEPTH)
  37.                 {
  38.                     if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)
  39.                     {
  40.                         stack.push(destination);
  41.                         visited[destination] = 1;
  42.                         depth++;
  43.                         System.out.println(destination + " at depth " + depth);
  44.                         element = destination;
  45.                         destination = 1;
  46.                     }
  47.                 }
  48.                 else
  49.                 {
  50.                     return;
  51.                 }
  52.                 destination++;
  53.             }
  54.             stack.pop();
  55.             depth--;
  56.         }
  57.     }
  58.  
  59.     public static void main(String... arg)
  60.     {
  61.         int number_of_nodes, source;
  62.         Scanner scanner = null;
  63.         try
  64.         {
  65.             System.out.println("Enter the number of nodes in the graph");
  66.             scanner = new Scanner(System.in);
  67.             number_of_nodes = scanner.nextInt();
  68.  
  69.             int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  70.             System.out.println("Enter the adjacency matrix");
  71.             for (int i = 1; i <= number_of_nodes; i++)
  72.                 for (int j = 1; j <= number_of_nodes; j++)
  73.                     adjacency_matrix[i][j] = scanner.nextInt();
  74.  
  75.             System.out.println("Enter the source for the graph");
  76.             source = scanner.nextInt();
  77.  
  78.             System.out.println("The Depth limited Search Traversal of Max Depth 3 is");
  79.             DepthLimitedSearch depthLimitedSearch = new DepthLimitedSearch(number_of_nodes);
  80.             depthLimitedSearch.depthLimitedSearch(adjacency_matrix, source);
  81.  
  82.         } catch (InputMismatchException inputMismatch)
  83.         {
  84.             System.out.println("Wrong Input format");
  85.         }
  86.         scanner.close();
  87.     }
  88. }
  89.  
  90. /* input and output
  91.  
  92. Enter the number of nodes in the graph
  93. 5
  94. Enter the adjacency matrix
  95. 0 1 0 0 0
  96. 0 0 1 0 0
  97. 0 0 0 1 0
  98. 0 0 0 0 1
  99. 0 0 0 0 0
  100. Enter the source for the graph
  101. 1
  102. The Depth limited Search Traversal  of Max Depth 3 for the graph is given by
  103. 1 at depth 0
  104. 2 at depth 1
  105. 3 at depth 2
  106. 4 at depth 3
  107.  
  108. 1--->2--->3--->4---5
  109.  
  110. another example :
  111.  
  112. Enter the number of nodes in the graph
  113. 5
  114. Enter the adjacency matrix
  115. 0 1 1 0 0
  116. 0 0 0 1 0
  117. 0 0 0 0 1
  118. 0 0 0 0 0
  119. 0 0 0 0 0
  120. Enter the source for the graph
  121. 1
  122. The Depth limited Search Traversal of Max Depth 3 is
  123. 1 at depth 0
  124. 2 at depth 1
  125. 4 at depth 2
  126. 3 at depth 1
  127. 5 at depth 2
  128.  
  129.    1
  130.   /\
  131.  2  3
  132. /   \
  133. 4    5
  134.  
  135.  
  136. * */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top