BFS gibt keinen Pfad zurück

Question

Ich versuche, BFS auf einem 2d-Array mit dem Start- und Endpunkt zu implementieren. Ich habe versucht, meine Funktion zwei Punkte auf dem Gitter zu geben, aber es gibt ein leeres Array zurück, was bedeutet, dass es keinen Pfad gibt.

Kann jemand bitte zeigen, wo ich falsch liege und, wenn möglich, mir helfen, meinen Fehler zu korrigieren? Vielen Dank.

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

Das erste Problem ist, dass Sie alle Elemente sind das Hinzufügen Sie aus der Warteschlange zu dem Pfad entfernen (ich bin auf der Linie unter Bezugnahme enthalten path.add(next);).

Stattdessen sollten Sie den übergeordneten Knoten verfolgen, von dem aus Sie die einzelnen Knoten besucht haben. Wenn Sie den Endknoten gefunden haben, können Sie Ihre Schritte zum Startknoten zurückverfolgen.

Wenn Sie alle Knoten ausgeschöpft haben und den Endknoten noch nicht gefunden haben, können Sie eine leere Liste zurückgeben.

Lassen Sie mich wissen, wenn Sie eine MCV example benötigen, und ich werde es hinzufügen.

Später bearbeiten:

Sie benötigen einen Punkt übergeordnete Feld zu Ihrer Klasse hinzuzufügen, wie folgt aus:

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

    // constructors, getters, setters, etc. 
} 

Dann können Sie Ihre BFS Implementierung ändern auch die Eltern für die aktuelle Einstellung Knoten beim Iterieren durch seine Nachbarn. Sie müssen die Schleife in etwa so ändern:

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