Die Breitensuche (BFS) ist ein Algorithmus zur Durchsuchung oder Traversierung eines Baumes oder Graphen. Dabei werden alle Knoten einer Ebene zuerst besucht, bevor die nächste Ebene durchlaufen wird. BFS eignet sich besonders gut zur Suche des kürzesten Pfads in ungewichteten Graphen, also dann, wenn alle Kanten gleich teuer sind.
Beispiel anhand des gegebenen Baumes: Der Baum beginnt mit dem Startknoten S (1). Die Kanten repräsentieren Verbindungen zwischen den Knoten. Die BFS erkundet den Baum in folgender Reihenfolge:
Die Reihenfolge der besuchten Knoten ist also: S → A → B → C → D → E → F → G
Die gezeigten Bäume, sind grundsätzlich nicht vollständig. Es wurden also einige Knoten weggeschnitten, um den Baum zu verkleinern.
Der schnellste Weg zum Ziel ist: S → A → G. Es gibt keinen anderen Weg, mit dem man das Ziel in zwei Schritten erreichen kann.
Wenn ein Knoten bereits in einer höheren Eben des Baumes gefunden wurde, wissen wir, dass wir den Knoten bereits in kürzerer Distanz erreicht haben. Ein Beispiel dafür wäre, dass wir E in der Tiefe 2 prunen können, da wir E schon nach einem Schritt erreicht haben.
In den auf dieser Webseite angezeigten Bäume wird ein Knoten geprunt, wenn er bereits in einer höheren Eben des Baumes gefunden wurde und kein Zielknoten ist. Es gibt jedoch sehr viel weitere Strategien, wie ein Suchbaum geprunt werden könnte.
Wir betrachten einen Graphen, welcher auf einem Viertel eines Schachbretts alle möglichen Wege für die Königsfigur vom Feld A1 bis Feld D1 abbildet. Intuitiv ist dieses Problem einfach zu verstehen. Es gibt jedoch bereits extrem viele Möglichkeiten um vom Start zum Ziel zu gelangen.
A1 → B2 → C3 → D4. Jeweils diagonal ziehen.
Es gibt 12 Wege, um in vier Zügen nach D4 zu gelangen.
Man könnte beispielweise von den Knoten, welche auf der gleichen Ebene zweimal gefunden wurden einen prunen.