0

これは 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;
              }
          }
          }
}
}
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に減少し、が返されたときに戻ります。ndepthFirstn==0

于 2013-09-20T00:42:42.730 に答える