Definition - Breitensuche

• Beispiele:
  • AlMa EA2.1
• Generalisierungen:
  • Suchverfahren
• Involvierte Definitionen:
  • Graph
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Breitensuche

Die Breitensuche ist ein Verfahren zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen.

Ausgehend vom Startknoten wird der Graph in die Breite nach einem Element durchsucht.

1. Wähle einen Startknoten aus. Speichere ihn in der Warteschlange ab.
2. Entnimm einen Knoten aus der Warteschlange.
3. Betrachte von diesem Knoten aus jede Kante :

• Prüfe, ob der Knoten das gesuchte Element ist.
• Prüfe, ob der Knoten schon entdeckt wurde.
  • Falls nicht, übernimm den Knoten in die Warteschlange (Queue)

1. Fahre fort wie in Schritt 2.

Anmerkung