Das Kefk Network Wiki befindet sich im Testbetrieb.

Aus Kefk.

Breitensuche (Breadth First Search) ist ein Fachbegriff der Informatik, welcher ein Verfahren zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphens bezeichnet. Sie zählt zu den uninformierten Suchalgorithmen.

Arbeitsweise

Die Breitensuche ist eine Uninformierte Suche, welche durch Expansion der einzelnen Level der Graphen ausgehend vom Startknoten den Graph in die Breite nach einem Element durchsucht.

Zuerst wird ein Startknoten u ausgewählt. Von diesem Knoten aus wird nun jede Kante (u,v) betrachtet und getestet, ob der gegenüberliegende Knoten v schon entdeckt wurde bzw. das gesuchte Element ist. Ist dies noch nicht der Fall, so wird der entsprechende Knoten in einer Warteschlange gespeichert und im nächsten Schritt bearbeitet. Hierbei ist zu beachten, dass Breitensuche immer zuerst alle direkt nachfolgenden Knoten bearbeitet, und nicht wie die Tiefensuche einem Pfad in die Tiefe folgt. Nachdem alle Kanten des Ausgangsknotens betrachtet wurden, wird der erste Knoten der Warteschlange entnommen, und das Verfahren wiederholt.

Algorithmus (informell)

1. Bestimme den Knoten, an dem die Suche beginnen soll, und speichere ihn in einer Warteschlange ab.
2. Entnimm einen Knoten vom Beginn der Warteschlange und markiere ihn.
   • Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere "gefunden" zurück.
   • Anderenfalls hänge alle bisher unmarkierten Nachfolger dieses Knotens ans Ende der Warteschlange an.
3. Wenn die Warteschlange leer ist, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere "nicht gefunden" zurück.
4. Wiederhole ab Schritt 2.

Eigenschaften

Speicherplatzverbrauch

Da alle bisher entdeckten Knoten gespeichert werden beträgt der Speicherplatzverbrauch von Breitensuche wobei für die Anzahl der Knoten und für die Anzahl der Kanten im Graph steht. Somit ist Breitensuche aufgrund des immensen Platzverbrauches für größere Probleme ungeeignet.
Ein der Breitensuche ähnliches Verfahren, jedoch mit deutlich geringerem Speicherplatzverbrauch, ist die iterative Tiefensuche.

Laufzeit

Da im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen beträgt die Laufzeit von Breitensuche wobei für die Anzahl der Knoten (Vertex) und für die Anzahl der Kanten (Edge) im Graph steht.

Vollständigkeit

Wenn in jedem Knoten nur endlich viele Alternativen existieren ist Breitensuche vollständig. Dies bedeutet, dass, wenn eine Lösung existiert, diese auch gefunden wird. Dies ist unabhängig davon, ob der zugrundeliegende Graph endlich ist oder nicht. Sollte jedoch keine Lösung existieren, so divergiert die Breitensuche bei einem unendlichen Graphen.

Optimalität

Breitensuche ist im allgemeinen nicht optimal, da immer das Ergebnis mit dem kürzesten Pfad zum Anfangsknoten gefunden wird. Führt man Kantengewichte ein, so muss das Ergebnis, welches am nächsten zum Startknoten liegt, nicht notwendigerweise auch das Ergebnis mit den geringsten Pfadkosten sein. Dieses Problem umgeht man, indem man die Breitensuche zur Uniformen Kostensuche erweitert. Sind jedoch alle Kantengewichte äquivalent, so ist die Breitensuche optimal, da in diesem Fall die Lösung, die am nächsten zum Ausgangsknoten liegt, auch die Lösung mit den geringsten Kosten ist.

Uniforme Kostensuche (Uniform Cost Search) ist eine Modifizierung der Breitensuche. Der Unterschied besteht darin, dass bei der Uniformen Kostensuche die Kanten gewichtet sind. Der Algorithmus geht nun entlang der geringsten Gewichte (Kosten) der Kanten und findet so die optimale Lösung. Außerdem muss gelten, dass die Pfadkosten mit zunehmender Tiefe im Suchbaum nicht kleiner werden, die Kosten eines Knotens also nicht negativ sind. Andernfalls würde die Uniforme Kostensuche nicht die günstigste Lösung finden können.

Anwendung

Die Breitensuche kann für viele Fragestellungen in der Graphentheorie verwendet werden. Einige sind:

• Finde alle Zusammenhangskomponenten in einem Graph
• Finde alle Knoten innerhalb einer Zusammenhangskomponente
• Finde zwischen zwei Knoten u und w einen kürzesten Pfad (ungewichtete Kanten)

Siehe auch

• Beschränkte Tiefensuche
• Iterative Tiefensuche
• Tiefensuche

Literatur

• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, 2^nd edition 2001, ISBN 0262531968

Weblinks

• Java-Applet zur Demonstration

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Breitensuche, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.