Kleines Nachschlagewerk Informatik
Breitensuche
Worum geht es?
Die Breitensuche ist eine weitere Art, einen Graphen komplett zu durchlaufen.
Wie funktioniert die Breitensuche?
Im Gegensatz zum einsamen Forscher hat man hier eine Ameisenarmee, die sich an jeder Kreuzung aufteilen kann. Am Startknoten teilt sich die Ameisenarmee, so dass je eine Gruppe zu den verbundenen Knoten läuft. Dort teilt sie sich wieder. Eine Gruppe stoppt, wenn ein bereits besuchter Knotenn gefunden wurde.

Die Weglänge in Labyrinth spielt keine Rolle, die Knoten werden gleichzeitig erreicht.
Beispiel
Dieser Graph dient zur Verdeutlichung der Breitensuche.



Die Reihenfolge ist somit: A-BC-DGH-EF.
Der Algorithmus

      Markiere alle Knoten als unbesucht
      Markiere alle Knoten als unbearbeitet
      Markieren ersten Knoten als besucht
      solange unbearbeitete Knoten existieren
          fuer alle Knoten, die besucht und unbearbeitet sind
              Markiere diesen Knoten als bearbeitet
              Suche alle Nachbarn des Knoten, die unbesucht sind
                  markiere sie als besucht