Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Fehler Vorlesungsfolien?
Algorithmus bfs(v):
füge in die leere Schlange q den Knoten v ein;
solange q enthält Elemente führe aus: {
entnimm q das erste Element =: w;
markiere w als besucht;
verarbeite w;
für jeden Nachfolger w i von w führe aus: {
wenn w i noch nicht besucht,
dann hänge w i an q an;
}
}
Der Pseudocode zum Breitensuche-Algo aus den Vorlesungsfolien ist doch nicht ganz korrekt, oder? Mit diesem Algo könnte es passieren, dass man an q ein Element anhängt, dass im vorigen Durchlauf schon angehängt wurde, weil z.B. zwei Knoten den selben Nachbarn haben, aber noch nicht als “besucht” markiert ist, weil es noch nicht bearbeitet wurde. Wenn ich das Element nun bearbeite wird auch nicht mehr überprüft, ob es schon bearbeitet ist, somit kann es passieren, dass ein Element mehrfach besucht und bearbeitet wird.
Ja, stimme dir da zu. Dass diese Variante zu Duplikateinträgen in der Queue führt, würde aber an sich noch keine inkorrekte Breitensuche ergeben. Man müsste aber denke ich – um genau dem Beispielfall entgegenzuwirken den du erwähnst – direkt hinter “entnimm q das erste Element =: w;” noch eine Zeile einbauen wie : “wenn schon besucht, dann überspringe” , sodass man dann den Duplikatsknoten beim “x.mal erwischen” überspringt und nicht tatsächlich erneut besucht.
An sich wäre die Variante aber glaube ich etwas ineffizient bzw. hätte noch Raum für Optimierungen, da man die Duplikateinträge sich sparen könnte, indem man bereits vor dem enqueuen in das visited Set hinzufügt / als visited markiert, also sowohl beim ersten Knoten vor dem Eintritt in die Schleife, als auch beim enqueuen aller Nachbarknoten unten.
Ja, für einen Baum müsste der Algorithmus funktionieren, weil dort jeder Knoten den Eingangsgrad 1 (bzw. 0 für die Wurzel) hat wodurch die Situation nicht entstehen kann, für einen allgemeinen Graphen wird man ihn so wie du vorgeschlagen hast modifizieren müssen, sonst ist der Algorithmus NICHT korrekt, weil per Definition von DFS/BFS jeder Knoten nur EINMAL besucht werden darf. Man würde aber immer noch jeden Knoten erwischen, eine Endlosschleife sollte auch nicht möglich sein.
Tiefensuche Tafelübungsfolien
Der Tiefensuchen Algorithmus in den Tafelübungsfolien scheint mir auch keine echte Tiefensuche zu sein, da er alle Kinder des aktuellen Knoten als besucht markiert, was im späteren Verlauf dazu führen kann, dass ein Pfad über einen dieser Knoten nicht gegangen wird, da dieser schon als besucht markiert ist, obwohl er im Sinne der Tiefensuche, die so lange absteigt, bis ein Element keinen Nachfolger mehr hat oder auf ein Element trifft, das auf dem aktuellen oder vorigen Pfad liegt und schon besucht wurde, besucht werden müsste. Er ist zumindest nicht äquivalent zu einer rekursiven Implementierung.
Das hört sich nicht sinnvoll an was du schreibst,
oder meist du dass erst abgestiegen wird wenn alle markiert wurden
Für gewöhnlich markiert die rekursive Tiefensuche nur das eigene Element und steigt dann sofort rekursiv in den ersten Nachfolger ab, bis entweder kein Nachfolger mehr da ist, oder der Pfad über einen bereits besuchten Knoten führen würde. Der Tiefensuchen-Algo aus den Folien markiert in jedem Schritt alle Nachfolger, nicht nur das aktuelle Element, dass kann dazu führen, dass der Algorithmus beim Absteigen früher aufhört als er eigentlich sollte, weil er über einen dieser markierten Nachfolgerknoten gehen möchte, dieser aber wie gesagt schon markiert ist. Nimm den folgenden Graph als Beispiel,
normale Besuchsreihenfolge für Tiefensuche wäre v1, v2, v4, v3, v6, v5. Mit dem Algo aus den Folien wäre die Besuchsreihenfolge aber: v1, v2, v4, v5, v3, v6. Er hört bei v3 auf, weil der Knoten gleich am Anfang schon von v1 markiert wurde, obwohl er eigentlich weiter gehen müsste.
Attachment:
Bildschirmfoto von »2019-07-15 08-30-28«.png: https://fsi.cs.fau.de/unb-attachments/post_161129/Bildschirmfoto von »2019-07-15 08-30-28«.png