Direkt zum Inhalt
  1. Startseite
  2. Illustrationen
  3. #916

Illustration Breitensuche (Breadth-first search - BFS)

Breitensuche (Breadth-first search - BFS)
Download

Teilen — es ist erlaubt die Illustration vervielfältigen und weiterverbreiten

Bearbeiten — es ist erlaubt die Illustration zu verändern und darauf aufzubauen und zwar für beliebige Zwecke, sogar kommerziell.

Diese Illustration ist kostenlos mit Angabe des Copyrights: universaldenker.org

Ein ungerichteter Graph mit 8 Knoten und 10 Knoten. Für die Breitensuche (eine Traversierungsmethode von Graphen, kurz: BFS) wird zuerst ein beliebiger Startknoten gewählt. Wähle z.B. den Knoten A:

BFS = [A]

Dann werden (wenn nicht festgelegt) die Nachbarknoten von A besucht. Wir legen es so fest, dass die Nachbarknoten alphabetisch besucht werden:

BFS = [A, B, E, F]

Dann werden die Nachbarknoten von B besucht. Nachbarknoten A wurde schon besucht und wird deshalb nicht doppelt gezählt:

BFS = [A, B, E, F, C, D]

Dann werden die Nachbarknoten von E besucht. Da die Nachbarknoten A und F schon besucht wurden, werden diese nicht gezählt:

BFS = [A, B, E, F, C, D, G]

Dann werden die Nachbarknoten von F besucht. Alle seine Nachbarknoten wurden bereits besucht. Die Nachbarknoten von C ebenfalls:

BFS = [A, B, E, F, C, D, G]

Dann werden die Nachbarknoten von D besucht. Die Nachbarknoten B, C und G wurden schon besucht. Nur der Nachbarknoten von H wurde noch nicht besucht:

BFS = [A, B, E, F, C, D, G, H]

Nun wurden alle Knoten besucht. Das heißt der Breitendurchlauf des Graphen ist erledigt.

Details zur Illustration
  • Lizenz: CC BY 4.0Diese Illustration darf mit der Angabe des Copyrights weiterverwendet werden!
  • Copyright: © 2020
  • Diese Illustration wurde hochgeladen von FufaeV am .
  • Diese Illustration wurde aktualisiert von FufaeV am .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?