Question

Breitensuche (BFS) funktioniert nicht

Erste Frage Aufrufe: 892 Aktiv: 22.02.2021 um 17:01

0

ich sitze jetzt schon ziemlch lange an einem Code. Dafür muss ich BFS implementiren, aber es funktioniert nicht richtig

Alles was ich bisher habe :

public ArrayList bfs(Graph graph, Vertex source, Vertex sink) { Stack pathStack = new Stack(); Queue queue = new LinkedList(); pathStack.push(source); queue.add(source); HashMap visited = new HashMap(); visited.put(source, true); while (!queue.isEmpty()) { Vertex current = queue.poll(); for (Vertex child : current.getChildren()) { if (!visited.containsKey(child)) { queue.add(child); visited.put(child, true); pathStack.push(child); if (current.getIdentifier().equals(sink.getIdentifier())) { break; } } } } ArrayList path = new ArrayList(); Vertex current = sink; Vertex vtx; path.add(sink); while (!pathStack.isEmpty()) { vtx = pathStack.pop(); if (current.isParent(vtx)) { path.add(vtx); current = vtx; if (vtx.getIdentifier().equals(source.getIdentifier())) { break; } } } return path; }

Teilen Diese Frage melden

gefragt 22.02.2021 um 16:24

samet476
Punkte: 10

Kommentar schreiben

1 Antwort

daniel.kuenkel · Answer 1 · 2021-02-22T17:01:35Z

Zu deiner Implementierung kann ich ein paar Dinge sagen:

Verwende keine HashMap, sondern ein HashSet zum Speichern der schon besuchten Knoten, da du sonst redundant immer "true" als Value speicherst, was unnötig ist.
Wenn du die Implementierung mit dem Stack wählst, dann musst du entweder innerhalb der for-Schleife den Befehl zum pushen auf den Stack NACH der if-Anweisung stellen oder schreiben:

Vertex current = pathStack.pop();

Das liegt daran, weil du ja den "sink"-Vertex am Ende noch auf den Stack pusht, bevor du die while-Schleife abbrichst.

Ich würde dir tatsächlich von der Methode mit dem Stack abraten, auch wenn sie vielleicht unter Umständen funktioniert. Das liegt daran, dass jeder Knoten mehrere Eltern haben kann, d. h. die Abfrage isParent(...) wäre nicht eindeutig. Was du aber machen könntest, wäre für jeden Knoten einfach eine Vorgängerreferenz zu speichern, d. h. in der Implementierung von Vertex einfach ein weiteres Attribut einfügen:

private Vertex prev;

Innerhalb der for-Schleife, bei der du alle Kinder des Knotens durchläufst, schreibst du dann einfach:

child.prev = current;

Am Ende kannst du dann einfach rekursiv vom Zielknoten bis zum Startknoten durchlaufen, indem du einfach immer den Vorgängerknoten aufrufst, dessen Referenz ja in "prev" gespeichert ist.