BFS不返回路徑

Question

我想在給定起點和終點的2d數組上實現BFS。我試着在網格上給出我的函數兩點，但它返回一個空數組，意味着沒有路徑。

有人可以請指出我哪裏錯了，如果可能幫助我糾正我的錯誤？謝謝。

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()]); 
} 

編輯：

 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，我會添加它。

後來編輯：

你需要一個Point父字段添加到您的類，像這樣：

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; 
      } 
     }