If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Der Algorithmus für die Breitensuche

Bei der Breitensuche werden jedem Knoten v zwei Werte zugewiesen:
  • Ein Abstandswert gibt die minimale Anzahl von Kanten an, die zwischen einem Startknoten und einem Zielknoten v liegen.
    • Der Vorgängerknoten gibt den Knoten an, der direkt vor v auf dem kürzesten Weg vom Startknoten liegt. Der Vorgänger des Startknotens ist null, denn er hat keinen Vorgänger.
Wenn es keinen Pfad vom Startknoten zum Knoten v gibt, dann ist der Abstand von v unendlich und sein Vorgängerwert ist auch null.
Wir betrachten als Beispiel einen ungerichteten Graphen mit acht Knoten, die wir von 0 bis 7 nummerieren, wobei die Knotenzahlen oberhalb oder unterhalb der Knoten erscheinen. Innerhalb jedes Knotens sind zwei weitere Zahlen: sein Abstand vom Startknoten 3, gefolgt von seinem Vorgänger auf einem kürzesten Weg von Knoten 3. Ein Bindestrich zeigt null an:
Bei der Breitensuche setzen wir zunächst den Abstand und Vorgänger jedes Knotens auf den Startwert (null). Wir starten die Suche am Startknoten und weisen ihm eine Distanz von 0\ zu. Dann besuchen wir alle Nachbarn des Startknotens und geben jedem Nachbar einen Abstand von 1 und setzen den Startknoten als seinen Vorgänger. Dann besuchen wir alle Nachbarn der Knoten, deren Distanz 1 ist und die noch nicht besucht worden sind, geben jedem dieser Knoten einen Abstandswert von 2 und setzen seinen Vorgänger als den Knoten, von dem wir ihn besuchten. Wir machen solange weiter, bis alle Knoten, die vom Startknoten erreichbar sind, besucht worden sind indem wir immer alle Knoten der Entfernung von k vom Startknoten besuchen, bevor wir Knoten mit der Entfernung k+1 besuchen.
Wir schauen uns das Schritt für Schritt für das obige Beispiel an:
  • Beginne mit dem Besuch von Knoten 3, des Startknotens. Setze seine Entfernung auf 0.
    • Dann besuche die Knoten 2 und 6, indem du ihre Entfernung auf 1 setzt und ihre Vorgänger auf 3.
    • Besuche alle Knoten der Entfernung 1 vom Startknoten, beginnend mit Knoten 2. Von Knoten 2 ausgehend, besuche die Knoten 4 und 5, indem du ihre Entfernung auf 2 setzt und ihren Vorgänger auf 2. Besuche nicht den Knoten 3, denn er wurde ja bereits besucht.
    • Von Knoten 6, besuche nicht Knoten 5, weil er gerade erst von Knoten 2 besucht wurde und besuche auch nicht Knoten 3.
    • Weiter geht es mit den Knoten der Entfernung 2 vom Startknoten. Das ist zuerst Knoten 4 : Besuche nicht Knoten 2, weil dieser bereits besucht wurde. Besuche aber den Knoten 1 und setze seinen Abstand auf 3 und seinen Vorgänger auf 4.
    • Aus dem Knotenpunkt 5 heraus, besuche keinen seiner Nachbarn, weil sie alle bereits besucht worden sind.
    • Anschließend besuchst du alle Knoten der Entfernung 3 vom Startknoten. Der einzige Knotenpunkt mit diesem Wert ist Knoten 1 . Seine Nachbarn, Knoten 4 und 5, wurden bereits besucht, aber Knoten 0 noch nicht. Besuche also den Knoten 0, setze den Abstand auf 4 und seinen Vorgänger auf den Knoten 1.
    • Jetzt fahren wir fort mit den Knoten der Abstandswerte 4 vom Startknoten. Das ist nur Knotenpunkt 0. Sein einziger Nachbar, Knoten 1, wurde bereits besucht. Wir sind fertig!
Weil es keinen Pfad von Knoten 3 zu Knoten 7 gibt, besucht die Suche nie Knoten 7 . Sein Abstand und Vorgänger bleiben unverändert von ihren Anfangswerten von null.
Wie stellt man fest, ob ein Knoten bereits besucht wurde? Das ist einfach: Der Abstand eines Knotens ist solangenull, bis er besucht wird. Zu diesem Zeitpunkt wird der Entfernungswert gesetzt. Wenn wir also die Nachbarn eines Knotens untersuchen, besuchen wir nur die Nachbarn, deren Entfernung null ist.
Wie merkt man sich, welche Ecken noch zu besuchen sind? Wir verwenden dazu eine Queue (Warteschlange). Das ist eine Datenstruktur, die es uns erlaubt, Elemente einzufügen und zu entfernen. Es wird immer das Element entfernt, das am längsten in der Warteschlange ist. Wir nennen dieses Verhalten first in, first out . Eine Queue hat drei Operationen:
  • enqueue(obj) fügt ein Objekt in die Warteschlange ein.
    • dequeue() entfernt aus der Warteschlange das Objekt, das am längsten in der Warteschlange ist und gibt dieses Objekt zurück.
    • isEmpty() gibt true zurück, wenn die Warteschlange derzeit keine Objekte enthält und false, wenn die Warteschlange mindestens ein Objekt enthält.
Immer wenn wir einen Knoten zuerst besuchen, schreiben wir ihn in die Queue. Am Anfang schreiben wir den Startknoten ein, denn das ist immer der erste Knoten, den wir besuchen. Um zu entscheiden, welcher Knoten als nächstes zu besuchen ist, wählen wir den Knoten, der in der Warteschlange am längsten ist und entfernen ihn aus der Warteschlange - mit anderen Worten, wir verwenden den Knoten, der von dequeue() zurückgegeben wird. An unserem Beispiel zeigen wir weiter unten die Warteschlange für jeden Schritt unseres Algorithmus, inklusive einer Visualisierung:
  • Anfänglich enthält die Warteschlange den Knoten 3 mit Abstand 0.
    • Dequeue Knoten 3 und enqueue Knoten 2 und 6, beide mit Abstand 1 . Die Warteschlange enthält nun den Knoten 2 mit Abstand 1 und den Knoten 6 mit Abstand 1.
    • Dequeue Knoten 2 und enqueue Knoten 4 und 5, beide mit Abstand 2 . Die Warteschlange enthält nun den Knotenpunkt 6 mit Abstand 1, Knoten 4 mit Abstand 2 und Knoten 5 mit Abstand 2.
    • Dequeue Knoten 6 und enqueue keinen Knoten. Die Warteschlange enthält nun Knoten 4 mit Abstand 2 und Knoten 5 mit Abstand 2.
    • Dequeue Knoten 4 und enqueue Knoten 1 mit Abstand 3. Die Warteschlange enthält nun Knoten 5 mit Abstand 2 und Knoten 1 mit Abstand 3.
  • Dequeue Knoten 5, und enqueue keinen Knoten. Die Warteschlange enthält nun nur Knoten 1 mit Abstand 3.
  • Dequeue Knoten 1 und enqueue Knoten 0 mit Abstand 4 . Die Warteschlange enthält nur noch Knotenpunkt 0 mit Abstand 4.
    • Dequeue Knotenpunkt 0, und enqueue keinen Knoten. Die Warteschlange ist jetzt leer. Da die Warteschlange leer ist, endet die Breitensuche.
Beachte, dass zu jedem Zeitpunkt die Warteschlange entweder Knoten mit der gleichem Abstand enthält, oder Knoten mit Abstand k gefolgt von Knoten mit Abstand k+1. Damit wird sichergestellt, dass wir zuerst alle Knoten der Entfernung k besuchen, bevor wir Knoten der Entfernung k+1 besuchen.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.