BFSがパスを返さない

Question

開始点と終了点を指定して2次元配列にBFSを実装しようとしています。私は、グリッド上に2点の関数を与えようとしましたが、パスがないことを意味する空の配列を返します。

誰かが間違っていることを指摘してください、可能であれば、私のエラーを修正するのに役立ちますか？ありがとう。

public Point[] bfs2(Point start, Point end) { 
    boolean[][] visited = new boolean[50][50]; 
    for (int i = 0; i < visited.length; i++) 
     for(int j = 0; j < visited.length; j++) 
      visited[i][j] = false; 

    visited[start.getX()][start.getY()] = true; 
    LinkedList<Point> path = new LinkedList<>(); 
    Queue<Point> q = new LinkedList<>(); 
    q.add(start); 

    while (!q.isEmpty()) { 
     Point next = q.remove(); //i think the error is here 
     Point[] neighbours = next.getNeighbours(); 
     path.add(next); 

     if (next.getX() == end.getX() && next.getY() == end.getY()) 
      break; 
     else if (!visited[next.getX()][next.getY()]) { 
      for (Point neighbour : neighbours) { 
       if (!visited[neighbour.getX()][neighbour.getY()]) { 
        q.add(neighbour); 
       } 

       visited[neighbour.getX()][neighbour.getY()] = true; 
      } 
     } 
    } 

    Point current = path.removeLast(); 
    ArrayList<Point> v = new ArrayList<>(); 
    while (current.getX() != start.getX() || current.getY() != start.getY()) { 
     v.add(current); 
     current = path.removeLast(); 
    } 

    return v.toArray(new Point[v.size()]); 
} 

EDIT：

 Point current=q.peek(); 
    ArrayList<Point> v=new ArrayList<>(); 
    if(start.getX()==end.getX() && start.getY()==end.getY()) return new Point[0]; 
    while(current.getX()!=start.getX() || current.getY()!=start.getY()){ 
     v.add(current); 
     current=current.parent; 
    } 
    return v.toArray(new Point[v.size()]); 

Answer 1

最初の問題は、あなたが（私はpath.add(next);を含む行を参照しています）あなたがパスにキューから削除するすべての要素を追加しているということです。

代わりに、各ノードにアクセスした親ノードを追跡する必要があります。終了ノードを見つけると、開始ノードにステップをトレースバックすることができます。

すべてのノードを使い切っても、まだエンドノードが見つからない場合は、空のリストを返すことができます。

MCV exampleが必要な場合はお知らせください。追加します。あなたはこのように、あなたのクラスにポイント親フィールドを追加する必要が

：

class Point { 
    int x; 
    int y; 
    Point parent; // reference to the Point from which this Point was visited 

    // constructors, getters, setters, etc. 
} 

その後、あなたはまた、現在の親を設定するためにあなたのBFSの実装を変更することができます

後の編集ノード間で反復処理を行う場合ループを次のように変更する必要があります。

 for (Point neighbour : neighbours) { 
      if (!visited[neighbour.getX()][neighbour.getY()]) { 
       q.add(neighbour); 
       visited[neighbour.getX()][neighbour.getY()] = true; 
       neighbour.parent = next; 
      } 
     }