Tiefen- und Breitensuche

Tiefen- und Breitensuche sind Verfahren zum Traversieren von Graphen. Als Ergebnis eines zusammenhängenden Graphen erhält man einen aufspannenden Baum.

Breitensuche

Die Breitensuche (BFS - breadth-first-search) ist ein Algorithmenmuster, das die Knoten eines Graphen nach der Entfernung von einem Startknoten geordnet durchläuft.
Zuerst werden alle von diesem Startknoten direkt durch eine Kante erreichbaren Knoten bearbeitet, danach die mit zwei Kanten Entfernung, dann die mit drei usw.

Tiefensuche

Mit der Tiefensuche (DFS - depth-first-search) geht man so weit wie möglich einen gewählten Pfad entlang. Wenn man am Ende eines Zweiges angekommen ist, geht man schrittweise zurück, bis man in einen bislang unbesuchten Teilbaum absteigen kann. Ist man wieder am Startknoten angelangt und es gibt keine unbesuchten Knoten, die mit dem Startknoten durch eine Kante verbunden sind, dann ist man fertig.
Dieseas Verfahren nennt man Backtracking: Man geht solange man kann, wenn man nicht mehr weiter kommt, geht man zurück bis man einen anderen Weg findet.

Beispiel:

Beispielgraph	Breitensuche	Tiefensuche