Deutsch
Menü

Breitensuche vs. Tiefensuche (BFS vs. DFS): Besuchsreihenfolge, Datenstruktur, kürzeste Wege, Speicher und Einsatz

Beide sind Verfahren, um alle Knoten eines Graphen oder Baums entlang seiner Kanten zu besuchen. Die Breitensuche (BFS) breitet sich nach Entfernung aus: Sie besucht alle Knoten, die eine Kante vom Start entfernt sind, dann die zwei Kanten entfernten und so weiter. Die Tiefensuche (DFS) folgt einem Weg so weit wie möglich, und wenn sie in eine Sackgasse gerät, geht sie zurück und probiert einen anderen Weg. Die Breitensuche wird mit einer Warteschlange (Queue) implementiert, die Tiefensuche mit einem Stack oder mit Rekursion; bei einem als Adjazenzlisten gespeicherten Graphen besuchen beide alles in einer Zeit proportional zur Anzahl der Knoten plus der Anzahl der Kanten. Die Breitensuche ist die übliche Wahl für kürzeste Wege in ungewichteten Graphen, die Tiefensuche für das erschöpfende Durchsuchen aller Wege oder das Erkennen von Zyklen.

MerkmalBreitensuche (BFS)Tiefensuche (DFS)
BesuchsreihenfolgeNächste zuerst (wenigste Kanten vom Start), Schicht für Schicht nach außenGeht einem Weg in die Tiefe nach, kehrt an einer Sackgasse um und nimmt den nächsten Weg
Verwendete DatenstrukturWarteschlange (Queue; First In, First Out)Stack (Last In, First Out) oder rekursive Aufrufe
Kürzeste WegeIn einem ungewichteten Graphen ist die Kantenzahl beim ersten Erreichen eines Knotens seine kürzeste Entfernung vom StartNicht garantiert: Ein Knoten kann zuerst über einen Umweg erreicht werden
Zeitkomplexität (V Knoten, E Kanten)O(V + E) mit Adjazenzlisten, O(V²) mit einer AdjazenzmatrixWie bei der Breitensuche: O(V + E) mit Adjazenzlisten, O(V²) mit einer Adjazenzmatrix
SpeicherbedarfDie als Nächstes zu besuchenden Knoten liegen in der Warteschlange; bei vielen Verzweigungen liegt eine ganze Schicht von Knoten gleichzeitig darin, sodass sie groß wirdRekursiv geschrieben braucht sie nur die Knoten auf dem aktuellen Weg, der Speicher wächst also mit der Tiefe des Weges; sehr tiefe Suchen können den Aufrufstapel überlaufen lassen
Ob eine Lösung gefunden wirdBei endlich vielen Knoten immer; selbst wenn der Suchraum unbegrenzt wächst, werden flache Lösungen zuerst gefundenIn einem endlichen Graphen immer, wenn besuchte Knoten vermerkt werden; können Wege unbegrenzt tief werden, läuft sie womöglich einen Weg immer weiter hinab und kehrt nie zurück
Reihenfolge beim BaumdurchlaufLevel-Order (Ebene für Ebene ab der Wurzel, von links nach rechts)Pre-Order, In-Order und Post-Order
Typischer EinsatzKürzeste Wege in ungewichteten Graphen, minimale Zugzahl in einem Labyrinth, wie viele Hops ein Netzwerk weit reichtErschöpfende Suche in Labyrinthen und Rätseln (Backtracking), Finden von Zusammenhangskomponenten und Zyklen, topologische Sortierung

Die Zahlenwerte sind typische Größenordnungen und variieren je nach Prozessgeneration und Produkt.

Wann welche Variante?

Breitensuche
Wenn die minimale Schrittzahl oder der kürzeste Weg in einem ungewichteten Graphen gesucht ist oder Knoten in der Reihenfolge ihrer Nähe zum Start untersucht werden sollen. Für kürzeste Wege mit gewichteten Kanten nimmt man den Dijkstra-Algorithmus.
Tiefensuche
Wenn alle Wege oder Kombinationen erschöpfend untersucht, Zusammenhangskomponenten oder Zyklen gefunden oder Aufgaben per topologischer Sortierung geordnet werden sollen. Mit Rekursion lässt sie sich kompakt schreiben.

Häufige Fragen

Findet die Breitensuche kürzeste Wege, wenn Kanten Gewichte haben?

Nein, denn der Weg mit den wenigsten Kanten hat nicht unbedingt das kleinste Gesamtgewicht. Sind die Gewichte null oder größer, nimmt man den Dijkstra-Algorithmus. Er ersetzt die Warteschlange durch eine Prioritätswarteschlange, die zuerst den Knoten mit der kleinsten Entfernung vom Start entnimmt, und lässt sich als Erweiterung der Breitensuche auf gewichtete Graphen auffassen.

Sollte man die Tiefensuche rekursiv oder mit einem eigenen Stack schreiben?

Rekursion ist kurz und gut lesbar, doch in sehr tiefen Graphen können die verschachtelten Aufrufe den Aufrufstapel überlaufen lassen. Schreibt man sie als Schleife mit einem eigenen Stack, lässt sich das vermeiden. Je nach Reihenfolge, in der die Nachbarn auf den Stack gelegt werden, kann die Besuchsreihenfolge jedoch von der rekursiven Version abweichen.

Was passiert, wenn besuchte Knoten nicht vermerkt werden?

In einem Graphen mit Zyklen werden dieselben Knoten immer wieder besucht. Bei der Breitensuche wächst die Warteschlange unbegrenzt, und die Tiefensuche kann endlos denselben Zyklus durchlaufen. Bei beiden Verfahren werden besuchte Knoten (oder bereits in Warteschlange bzw. Stack aufgenommene Knoten) daher markiert, damit sie nie erneut aufgenommen werden.

Verständnis prüfen

In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?

  1. ABreitensuche mit einer Warteschlange
  2. BTiefensuche mit einem Stack
  3. CBreitensuche mit einem Stack
Antwort und Erläuterung anzeigen

Antwort: A. Breitensuche mit einer Warteschlange

Die Breitensuche besucht die Knoten nach ihrer Entfernung: zuerst die eine Kante vom Start entfernten, dann die zwei Kanten entfernten und so weiter. Jeden neu gefundenen Knoten hinten in eine Warteschlange einzufügen und die Knoten vorn zu entnehmen, bewahrt diese Reihenfolge „Nächste zuerst“; die Zahl der Kanten beim ersten Erreichen eines Knotens ist daher die kürzeste. Die Tiefensuche (mit Rekursion oder einem Stack) geht auf einem Pfad so weit wie möglich und kann einen Knoten zuerst auf einem Umweg erreichen; kürzeste Entfernungen sind daher nicht garantiert. Verwendet man statt einer Warteschlange einen Stack, wird der Durchlauf einer Tiefensuche ähnlich.

In einem ungerichteten Graphen sind die Nachbarn der Knoten A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Eine rekursive Tiefensuche beginnt bei Knoten A. Die Nachbarn werden in der angegebenen Reihenfolge geprüft, und sobald ein unbesuchter Knoten gefunden wird, geht die Suche zu ihm weiter. In welcher Reihenfolge werden die Knoten besucht?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Antwort und Erläuterung anzeigen

Antwort: C. A, B, D, E, F, C

Von A geht die Suche zu B und dann zu D, dem ersten unbesuchten Nachbarn von B. Der einzige Nachbar von D, nämlich B, ist bereits besucht; die Suche kehrt zu B zurück, geht weiter zu E, von E zum unbesuchten F und von F zu dessen Nachbarn C. Die Reihenfolge ist daher A, B, D, E, F, C. A, B, C, D, E, F ist die Reihenfolge der Breitensuche, die die nächstgelegenen Knoten zuerst besucht. A, B, D, E, C, F kehrt bei E um, ohne zum unbesuchten F zu gehen, und ist daher keine Reihenfolge einer Tiefensuche.

Wie lässt sich ein dünn besetzter Graph, also einer mit wenigen Kanten im Verhältnis zur Zahl der Knoten, etwa ein Straßennetz mit rund 1 Million Knoten und 3 Millionen Kanten, geeignet im Speicher ablegen?

  1. AAls Adjazenzmatrix: Sie prüft in O(1), ob zwei Knoten verbunden sind, und braucht zudem den wenigsten Speicher
  2. BAls Adjazenzlisten: Der Speicherbedarf ist proportional zur Zahl der Knoten plus der Zahl der Kanten, und sie eignen sich, um die von einem Knoten ausgehenden Kanten der Reihe nach zu verfolgen
  3. CAls Adjazenzmatrix: Ihr Speicherbedarf ist nur proportional zur Zahl der Kanten
Antwort und Erläuterung anzeigen

Antwort: B. Als Adjazenzlisten: Der Speicherbedarf ist proportional zur Zahl der Knoten plus der Zahl der Kanten, und sie eignen sich, um die von einem Knoten ausgehenden Kanten der Reihe nach zu verfolgen

Eine Adjazenzmatrix verwendet für V Knoten eine Tabelle mit V × V Einträgen; 1 Million Knoten brauchen also 10¹² Einträge, selbst bei 1 Bit pro Eintrag etwa 125 GB. Adjazenzlisten speichern nur die Nachbarn jedes Knotens, der Speicherbedarf ist also O(V + E), in diesem Beispiel nur einige Millionen Einträge. Eine Adjazenzmatrix hat den Vorteil, eine Kante in O(1) prüfen zu können, und eignet sich für dicht besetzte Graphen oder Graphen mit wenigen Knoten. Für Verfahren, die nacheinander die von jedem Knoten ausgehenden Kanten verfolgen, etwa die Breitensuche und den Dijkstra-Algorithmus, sind Adjazenzlisten effizienter.

  1. In einem ungerichteten Graphen haben die Kanten die Gewichte (Entfernungen) S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 und A−T: 6. Welcher kürzeste Weg von S nach T und welche Länge ergeben sich mit dem Dijkstra-Algorithmus?
  2. Die Werte 50, 30, 70, 20, 40, 60, 80 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt. In welcher Reihenfolge werden die Knoten besucht, wenn der Baum in Post-Order (erst der linke Teilbaum, dann der rechte Teilbaum, dann der Knoten) durchlaufen wird?

Übungsfragen zu Datenstrukturen und Algorithmen

Wichtige Begriffe erklärt

Breitensuche (Breadth-First Search)
Verfahren zum Durchsuchen eines Graphen oder Baums, das die Knoten nach ihrer Entfernung vom Start besucht: zuerst die eine Kante entfernten, dann die zwei Kanten entfernten und so weiter. Es wird mit einer Warteschlange implementiert und findet in einem Graphen ohne Kantengewichte die kleinste Zahl von Kanten vom Start zu jedem Knoten. Abgekürzt BFS.
Tiefensuche (Depth-First Search)
Verfahren zum Durchsuchen eines Graphen oder Baums, das auf einem Pfad so weit wie möglich geht und bei einer Sackgasse zurückkehrt (Backtracking), um einen anderen Pfad zu versuchen. Es wird mit Rekursion oder einem Stack implementiert und für das Lösen von Labyrinthen, das Finden von Zusammenhangskomponenten und Zyklen sowie für die topologische Sortierung verwendet. Abgekürzt DFS.
Warteschlange (Queue)
FIFO-Datenstruktur (First In, First Out), bei der das zuerst hinzugefügte Element zuerst entnommen wird. Das Anfügen hinten heißt Enqueue, das Entnehmen vorn Dequeue. Warteschlangen dienen für anstehende Aufträge, für die Datenübergabe zwischen Tasks und für die Breitensuche.
Stack (Stapelspeicher)
LIFO-Datenstruktur (Last In, First Out), bei der das zuletzt hinzugefügte Element zuerst entnommen wird. Das Hinzufügen eines Elements heißt push, das Entnehmen pop. Stacks dienen zur Verwaltung von Rücksprungadressen und lokalen Variablen bei Funktionsaufrufen (Call Stack), zur Auswertung von Ausdrücken in umgekehrter polnischer Notation und für die Tiefensuche.
Rekursion
Aufruf einer Funktion durch sich selbst als Teil ihrer eigenen Verarbeitung. Das Problem wird in kleinere Probleme derselben Form zerlegt, und die Aufrufe enden bei einem Fall, der nicht weiter zerlegt wird (dem Basisfall). Jeder Aufruf belegt Stack-Speicher, daher läuft der Stack bei zu tiefer Rekursion über. Endrekursion, bei der der rekursive Aufruf das Letzte ist, was die Funktion tut, lässt sich in eine Schleife umwandeln.
Dijkstra-Algorithmus
Algorithmus, der in einem Graphen mit Kantengewichten größer oder gleich 0 die kürzesten Wege von einem Startknoten zu allen Knoten findet. Er legt wiederholt den nächstgelegenen Knoten, dessen Entfernung noch nicht feststeht, endgültig fest und aktualisiert die Entfernungen seiner Nachbarn. Bei negativen Kantengewichten arbeitet er nicht korrekt.
Zeitkomplexität (O-Notation)
Beschreibung, wie der Aufwand (Zeitkomplexität) oder der Speicherbedarf (Platzkomplexität) eines Algorithmus mit der Zahl n der Datenelemente wächst. Angegeben wird sie in O-Notation, etwa O(n), O(n log n) oder O(n²), wobei konstante Faktoren und Terme niedrigerer Ordnung entfallen.

Verwandte Vergleiche