Breitensuche

Breitensuche

Breitensuche (englisch breadth-first search, BFS) ist ein Verfahren in der Informatik, zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen. Sie zählt zu den uninformierten Suchen. Im Gegensatz zur Tiefensuche werden zunächst alle Knoten beschritten, die vom Ausgangsknoten erreichbar sind. Erst danach werden Folgeknoten beschritten (siehe Abbildung).

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.

Eine Landkarte von Deutschland mit den Verbindungen zwischen einigen Städten.

Der Baum, welcher entsteht, wenn man BFS auf die Landkarte anwendet und in Frankfurt startet.

Weiteres Beispiel für Breitensuche

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, die sich noch nicht in der Warteschlange befinden, 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 Schritt 2.

Algorithmus (formal)

Nachstehend formulierte Algorithmen sind als Pseudocode zu verstehen und geben aus Gründen der Lesbarkeit nur an, ob der Zielknoten gefunden wurde. Weitere, in Anwendungsfällen wichtige Informationen - wie z.B. die aktuelle Pfadtiefe oder der bisherige Suchweg - könnten zusätzlich eingefügt werden.

Rekursiv formuliert:

BFS(start_node, goal_node) {
  return BFS'({start_node}, ∅, goal_node);
}
BFS'(fringe, visited, goal_node) {
  if(fringe == ∅) {
    // Knoten nicht gefunden
    return false; 
  }
  if (goal_node ∈ fringe) {
    return true;
  }
  return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node);
}

Als Schleife formuliert:

BFS(start_node, goal_node) {
 for(all nodes i) visited[i] = false; // anfangs sind keine Knoten besucht
 queue.push(start_node);              // mit Start-Knoten beginnen
 visited[start_node] = true;
 while(! queue.empty() ) {            // solange queue nicht leer ist
  node = queue.pop();                 // erstes Element von der queue nehmen
  if(node == goal_node) {
   return true;                       // testen, ob Ziel-Knoten gefunden
  }
  foreach(child in expand(node)) {    // alle Nachfolge-Knoten, ...
   if(visited[child] == false) {      // ... die noch nicht besucht wurden ...
    queue.push(child);                // ... zur queue hinzufügen...
    visited[child] = true;            // ... und als bereits gesehen markieren
   }
  }
 }
 return false;                        // Knoten kann nicht erreicht werden
}

Eigenschaften

Bezeichne $\vert V\vert$ die Anzahl der Knoten (Vertex) und $\vert E\vert$ die Anzahl der Kanten (Edge) im Graphen. Speicherplatzverbrauch und Laufzeit des Algorithmus in Landau-Notation angegeben.

Speicherplatzverbrauch

Da alle bisher entdeckten Knoten gespeichert werden, beträgt der Speicherplatzverbrauch von Breitensuche $O(\vert V\vert +\vert E\vert )$. Somit ist die 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 $O(\vert V\vert +\vert E\vert )$.

Vollständigkeit

Wenn in jedem Knoten nur endlich viele Alternativen existieren, ist die Breitensuche vollständig. Dies bedeutet, dass, wenn eine Lösung existiert, diese auch gefunden wird. Dies ist unabhängig davon, ob der zugrunde liegende 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 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.

Die uniforme Kostensuche (englisch uniform-cost search, UCS) ist eine Erweiterung der Breitensuche für Graphen mit gewichteten Kanten. Der Algorithmus besucht Knoten in Reihenfolge aufsteigender Pfadkosten vom Wurzelknoten (und wird deshalb üblicherweise mit einer Vorrangwarteschlange (engl. priority queue) implementiert, in der alle noch nicht besuchten Nachbarn bereits besuchter Knoten mit der Pfadlänge als Schlüssel verwaltet werden). Die Optimalität ist nur für nicht-negative Kantengewichte garantiert.

Anwendung

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

• Finde alle Knoten innerhalb einer Zusammenhangskomponente
• Finde zwischen zwei Knoten u und w einen kürzesten Pfad (ungewichtete Kanten)
• Kürzeste-Kreise-Problem

Siehe auch

• Beschränkte Tiefensuche

Literatur

• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, 2^nd edition 2001, ISBN 0-262-53196-8
• Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. Springer Vieweg, 3. Auflage, 2012, ISBN 978-3-8348-1849-2

Weblinks

Commons: Breitensuche – Sammlung von Bildern, Videos und Audiodateien

Wikibooks: Breitensuche – Lern- und Lehrmaterialien