Zum Hauptinhalt springen

Breitensuche

Bei der Breitensuche gehen wir – salopp gesagt – in alle Richtungen gleich schnell. Dabei werden etwaige Gewichte zwischen den Knoten ignoriert. Wir werden also einen Weg finden, aber nicht zwingend den Kürzesten!

Für die Suche brauchen wir zwei Listen, womit wir unseren Suchfortschritt festhalten:

Closed-List

Hier werden alle abgehandelten Knoten aufgelistet

Open-List

Hier werden alle bekannten Knoten welche als nächste Kandidaten in Frage kommen aufgeführt

Vorbereitung

Zu Beginn ist die Closed-List leer. Der Startknoten kommt auf die Open-List:

Closed-List: –
Open-List: I

Schritt 1

Wir nehmen den ersten Knoten von der Open-List – das ist I – und besuchen alle Nachbarn. Diese werden der Open-List angehängt. Der Knoten I gilt jetzt als besucht: Er wird von der Open-List gestrichen und kommt auf die Closed-List.

@
Closed-List: I
Open-List: M, C, B, H, P

Ergebnis

Die roten Linien und Knoten im Graphen stellen einen Baum dar. Wenn wir die Knoten nun etwas umpositionieren erhalten wir den folgenden erforschten Baum:

Dieser Baum zeigt zu jedem erforschten Knoten genau einen Weg vom Startknoten aus. Da wir den Algorithmus abgebrochen haben, sobald wir den Zielknoten gefunden haben, sind nicht alle Knoten aufgelistet. Aber wir finden den gesuchten Weg zum Zielknoten.

Wir zeichnen nun noch mit Pfeilen die Reihenfolge ein in welcher wir diese Knoten «durchsucht» haben:

Diese Art der Baumsuche nennt man Breitensuche.

Aufgabe

Führen Sie selbst eine Breitensuche durch: Finden Sie den Weg in umgekehrter Richtung, also vom Knoten L zum Knoten I.

  • Zeichnen Sie Ihren Fortschritt analog zum Beispiel im Graphen auf

  • Führen Sie daneben eine Open- und eine Closed-List