경로를 반환하지 않는 BFS

Question

시작 지점과 끝점이 지정된 2 차원 배열에 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이 필요하면 알려주세요. 추가하겠습니다.

나중에 편집 :

이 같은 클래스에 포인트 부모 필드를 추가해야합니다

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