Breitensuche
Die Breitensuche ist ein Algorithmus, um ein Element in einem Graphen zu suchen, ohne irgendwelche Informationen über dessen Verbindungen zu anderen Knoten zu haben.
Der Algorithmus beginnt bei einem Startknoten, besucht zunächst alle deren Nachbarn, dann deren noch nicht besuchte Nachbarn, dann deren noch nicht besuchte Nachbarn, bis entweder das gesuchte Objekt gefunden worden ist oder der gesamte Graph durchsucht wurde.
Die Liste der noch zu besuchenden Knoten kann bei der Breitensuche als Vorrangwarteschlange modelliert werden.
Wenn alle Kantengewichte des Graphen identisch sind, findet die Breitensuche immer einen kürzesten Weg zwischen dem Startknoten und dem gesuchten Knoten.
Die betrachteten Knoten und Kanten zwischen diesen bilden nach dem Ende einer Breitensuche einen Spannbaum mit dem Startknoten als Wurzel, allerdings nicht zwingend einen minimalen.
Beispiel
Das Objekt E soll vom Startknoten aus gefunden werden.
Anwendungen
Eine Anwendung von Breitensuche ist die Füllung von Farbflächen in einem Zeichenprogramm: zunächst wird der angeklickte Pixel gefärbt, dann alle von seinen Nachbarn, die dieselbe Farbe wie er hatten, dann deren Nachbarn mit derselben Farbe usw.
Auch der Weg aus einem Labyrinth kann mit einer Breitensuche gelöst werden. Dies wird u.a. in Computerspielen angewandt und in einer ähnlichen Situation auch beim Layouten von Leiterbahnen auf Platinen.
Weblinks
Suche: Breitensuche | Tiefensuche
Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus
Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus
