Ich verwende BFS, um verbundene Komponenten zu finden. Ich habe beschlossen, es mit einem Set zu implementieren, um besuchte Knoten zu verfolgen. Das Problem bei diesem Ansatz besteht darin, dass ein Scheitelpunkt der Warteschlange zweimal hinzugefügt werden kann. Also habe ich gerade die Warteschlange gewechselt. Ich interessiere mich nicht für Besuchsordnung, alle Knoten werden einmal besucht und der Algorithmus funktioniert gut. Das ist natürlich kein klassisches BFS mehr: der Auftrag ist gebrochen.Breitensuche mit Set statt Warteschlange
Pseudocode:
Set visited;
Set to_visit;
visited.insert(start)
to_visit.insert(start)
while (to_visit is not empty){
current = to_visit.first
to_visit.delete(current)
for each neighbour of current {
isNew = visited.insert(neighbour)
if (isNew) {
to_visit.insert(neighbour)
}
}
}
Ich bin mir ziemlich sicher, ich bin nicht der erste, der „erfunden“ es. Ich frage mich: Wie heißt diese I-dont-care-first-Suche?
Vielen Dank, ich weiß über ordnungsgemäße Implementierung von BFS. Eigentlich mache ich das selbe, behalte aber die Eindeutigkeit der Queue per Set bei. Und in meiner Implementierung wird ein Scheitelpunkt besucht, wenn _really_ besucht wurde, nicht wenn er zur Warteschlange hinzugefügt wurde. – ov7a
Ja, mit set sollte es auch funktionieren, ändern Sie einfach isVisited zu mySet [Vertex] = 1 oder etwas? Aber die Reihenfolge ist immer noch dieselbe. Ich sehe dein Problem! Sie können am Anfang eine if-Anweisung hinzufügen und prüfen, ob curr bereits besucht wurde oder nicht. Ich ändere meinen Pseudocode zu deiner Idee. –
'if (set [curr] == 1)' manipuliert die Komplexität des Algorithmus. Ein Eckpunkt kann mehr als einmal betrachtet werden. – ov7a