将深度优先搜索转换为深度受限搜索

Question

这是我用java编写的完整代码，我想对它进行深度有限的搜索。有人能帮帮我吗？

输出: S>A>B>C>D>G

注: S(0) =开始，G(5) =目标深度优先搜索使用adj矩阵。

import java.util.Stack;


public class DFS {

Stack<Integer> st;
  int vFirst;

  int[][] adjMatrix;
  int[] isVisited = new int[6];

/**
 * @param args
 */
public static void main(String[] args) {
    int[][] adjMatrix = {
           //S, A, B, C, D, G, 
            {0, 1, 0, 1, 0, 0},
            {1, 0, 1, 0, 1, 0},
            {0, 1, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 0},
            {0, 1, 0, 1, 0, 1},
            {0, 0, 1, 0, 1, 0},
             };


  new DFS(adjMatrix);

}

public DFS(int[][] Matrix) {

     this.adjMatrix = Matrix;
     st = new Stack<Integer>();
     //int i;
     int[] node = {0, 1, 2, 3, 4, 5};
     int firstNode = node[0];
     depthFirst(firstNode, 6);



      }

      public void depthFirst(int vFirst,int n)
      {
      int v,i;
      char out=' ';

      st.push(vFirst);

      while(!st.isEmpty())
      {
          v = st.pop();
          if(v==0)out='S';
          else if(v==1)out='A';
          else if(v==2)out='B';
          else if(v==3)out='C';
          else if(v==4)out='D';
          else if(v==5)out='G';

          if(isVisited[v]==0)
          {
              System.out.print("\n"+out);
              isVisited[v]=1;
          }
          for ( i=0;i<n;i++)
          {
              if((adjMatrix[v][i] == 1) && (isVisited[i] == 0))
              {
                  st.push(v);
                  isVisited[i]=1;
                  if(i==0)out='S';
                  else if(i==1)out='A';
                  else if(i==2)out='B';
                  else if(i==3)out='C';
                  else if(i==4)out='D';
                  else if(i==5)out='G';
                  System.out.print("-> " + out);
                  v = i;
              }
          }
          }
}
}

Answer 1

您可以使用temp类或ADT来存储当前从start到节点的距离，当您将它们堆叠在一起(Push)时，添加curr distance +1 (开始时的距离=0)。弹出时，检查距离是否大于或小于最大值，然后继续。这就是我的想法。

Curr Node,Curr Distance ->  Stack   <-
1st (S,0)               -> (A,1) (C,1)
2nd (C,1)               -> (A,1) (B,2) (D,2)
3rd (D,2)               -> (A,1) (B,2) (A,3) (G,3) 
4....                   -> ....

(可能想要跟踪，哪些在堆栈中或不在堆栈中...)

希望你能理解我的建议，让我知道你的想法。

Answer 2

您在depthFirst中已经有一个未使用的参数n，请在每次调用depthFirst时递减n，并在调用n==0时返回。