0

这是我在 java 中的完整代码，我想对其应用深度限制搜索。有人可以帮帮我吗？

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

注意：S(0) = Start, G(5) = Goal 使用 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;
              }
          }
          }
}
}
4

2 回答 2

0

您可以使用临时类或 ADT 来存储从启动到节点的当前距离，当您将它们堆叠（推送）时，您添加当前距离 +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....                   -> ....

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

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

于 2013-09-20T00:40:33.060 回答
0

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

于 2013-09-20T00:42:42.730 回答