Direkt zum Inhalt

Illustration Breitensuche (Breadth-first search - BFS)

<span>Breitensuche (Breadth-first search - BFS)</span>
Breitensuche (Breadth-first search - BFS)
Download

Teilen — es ist erlaubt die Illustration zu vervielfältigen und weiterzuverbreiten

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

Teilen und Bearbeiten der Illustration ist mit Angabe des Links zur Illustration erlaubt.

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.