Was sind BFS- und DFS-Algorithmen, und wann sollten Sie welchen wählen?
BFS und DFS sind Algorithmen zur Graphtraversierung, die systematisch Knoten finden, die von einem Startknoten aus erreichbar sind. BFS erweitert die Suche Ebene für Ebene von nahegelegenen Knoten aus und eignet sich daher, wenn Sie in einem ungewichteten Graphen einen Pfad mit der geringsten Anzahl an Kanten benötigen. DFS verfolgt einen Zweig so weit wie möglich, bevor es zurückgeht, und dient daher als Grundlage für Probleme wie Strukturanalyse, Zyklenerkennung und topologische Sortierung. Keiner der beiden ist immer besser; die Wahl hängt vom Pfadkriterium und dem Zweck des Graphen ab. ocw.mit.edualgs4.cs.princeton.edu
Was finden BFS und DFS bei der Graphtraversierung?
Ein Graph ist eine relationale Struktur aus Knoten und Kanten. Knoten repräsentieren Entitäten wie Personen, Städte, Webseiten oder Aufgaben, während Kanten Verbindungen zwischen ihnen darstellen, etwa Freundschaften, Straßen, Links oder Abhängigkeitsbeziehungen. Die Knotenmenge wird mit und die Kantenmenge mit bezeichnet.
Haben Kanten keine Richtung, ist der Graph ungerichtet. Eine gegenseitige Freundschaft kann beispielsweise meist als bidirektional betrachtet werden. Beziehungen wie das Folgen von A zu B oder die Vorgabe, dass Aufgabe A vor Aufgabe B abgeschlossen sein muss, bilden dagegen einen gerichteten Graphen. In einem gerichteten Graphen können Sie sich nur in Richtung eines Pfeils bewegen; eine Bewegung in die Gegenrichtung ist nicht automatisch möglich. ocw.mit.edu
Die grundlegendste Frage bei der Graphtraversierung lautet: „Welche Knoten sind von einem Startpunkt aus erreichbar?“ Bei der Beantwortung dieser Frage können BFS und DFS auch zusätzliche Informationen speichern, etwa ob ein Knoten bereits besucht wurde, über welchen Pfad jeder Knoten erstmals erreicht wurde und in welcher Reihenfolge traversiert wird. Eine Traversierung, die an einem Knoten beginnt, verarbeitet jedoch nur den Teil, der tatsächlich von diesem Knoten aus erreichbar ist. Sie besucht nicht zwingend jeden Knoten im Graphen. ocw.mit.edu
Auch ein Baum ist eine Art von Graph. Daher können BFS und DFS für Probleme verwendet werden, die wie Bäume aussehen, beispielsweise Ordnerhierarchien oder Organigramme. Es ist jedoch wichtig, sich daran zu erinnern, dass ein allgemeiner Graph Zyklen enthalten kann, die zu einem Knoten zurückführen, sowie mehrere Pfade zum selben Knoten. Wenn eine Implementierung, die nur für Baumtraversierungen entworfen wurde, direkt auf einen allgemeinen Graphen angewendet wird, kann dies zu doppelten Besuchen führen.
Wie erkundet BFS zuerst nahegelegene Knoten?
BFS steht für Breadth-First Search, auf Deutsch Breitensuche. Zuerst findet es Knoten, die vom Startpunkt über eine Kante erreichbar sind, dann Knoten, für die zwei Kanten nötig sind, dann drei Kanten, und erweitert den Suchbereich in dieser Reihenfolge. Die Distanz ist hier keine physische Entfernung oder ein Kostenwert, sondern die Anzahl der Kanten, die vom Startpunkt aus durchlaufen werden müssen. algs4.cs.princeton.edu
BFS verwendet dafür üblicherweise eine Warteschlange. Eine Warteschlange ist eine FIFO-Datenstruktur (First In, First Out): Das zuerst eingefügte Element wird auch zuerst entnommen. Fügen Sie den Startknoten in die Warteschlange ein und markieren Sie ihn als besucht. Entnehmen Sie dann einen Knoten am Anfang der Warteschlange. Markieren Sie alle noch unentdeckten Nachbarn dieses Knotens als besucht und fügen Sie sie am Ende der Warteschlange ein. Wiederholen Sie dies, bis die Warteschlange leer ist. Weil zuvor entdeckte, nahegelegene Knoten zuerst verarbeitet werden, bleibt die Erweiterung Ebene für Ebene erhalten. gh.cp-algorithms.comalgs4.cs.princeton.edu
Angenommen, Sie entdecken ausgehend von A die Nachbarn B und C von A. Wenn BFS B verarbeitet, entdeckt es die Nachbarn von B; anschließend verarbeitet es C und entdeckt dessen Nachbarn. Selbst wenn ein von B entdeckter Knoten tiefer liegt, wird C, das bereits auf derselben Ebene in die Warteschlange eingefügt wurde, zuerst oder kurz danach verarbeitet. Die genaue Reihenfolge zwischen B und C kann davon abhängen, in welcher Reihenfolge benachbarte Knoten gespeichert sind.
Entscheidend bei BFS ist, einen Knoten sofort bei seiner Entdeckung als besucht zu markieren. Verzögern Sie die Markierung, bis er aus der Warteschlange entnommen wird, können zwei Knoten denselben Nachbarn entdecken und ihn mehrfach in die Warteschlange einfügen. Bei einem typischen BFS ist es einfacher und sicherer, einen neuen Nachbarn genau in dem Moment als entdeckt zu markieren, in dem er in die Warteschlange eingefügt wird.
Unter welchen Bedingungen liefert BFS einen kürzesten Pfad?
BFS wird häufig gewählt, weil es in einem ungewichteten Graphen für jeden erreichbaren Knoten einen Pfad mit der geringsten Anzahl an Kanten vom Startknoten findet. Es untersucht alle Knoten in einem Schritt Entfernung vom Start, bevor es Knoten in zwei Schritten Entfernung untersucht. Daher kann später kein Pfad mit weniger Kanten als der Pfad auftauchen, der einen Knoten zuerst entdeckt. Wenn Sie während BFS beim ersten Entdecken jedes Knotens den vorhergehenden Knoten als Elternknoten speichern, bilden diese Elternzeiger einen Kürzeste-Wege-Baum. algs4.cs.princeton.edu
Um einen Pfad zu rekonstruieren, folgen Sie den Elternzeigern vom Zielknoten rückwärts bis zum Startknoten und kehren anschließend die Reihenfolge um. Wenn beispielsweise parent[D] = B und parent[B] = A gilt, lautet der entdeckte Pfad von A nach D: A → B → D. Verwenden Sie eine separate Markierung, um anzuzeigen, dass der Startknoten keinen Elternknoten hat.
Eine zu weit gefasste Interpretation von „kürzest“ führt jedoch zu Fehlern. BFS garantiert die geringste Anzahl von Kanten nur dann, wenn alle Kanten als gleich teuer behandelt werden können. Haben Straßen unterschiedliche Fahrzeiten oder Flüge unterschiedliche Preise, kann ein Pfad mit zwei Kanten günstiger oder schneller sein als einer mit nur einer Kante. In diesem Fall ist Standard-BFS kein Kürzeste-Wege-Algorithmus nach Kosten. Ziehen Sie abhängig von den Eigenschaften der Gewichte spezielle gewichtete Verfahren wie den Dijkstra-Algorithmus oder den Bellman-Ford-Algorithmus in Betracht. algs4.cs.princeton.edu
Daher eignet sich BFS gut für Fragen wie „Wie viele Verbindungsgrade trennen zwei Freunde?“ oder „Wie viele Züge sind nötig, um einen Punkt in einem Gitter zu erreichen, wenn die Bewegung um eine Zelle nach oben, unten, links oder rechts jeweils als ein Zug zählt?“ Geht es dagegen um die geringste Zeit oder die niedrigsten Kosten, prüfen Sie zuerst, ob die Kantengewichte tatsächlich gleich sind.
Warum geht DFS vor dem Zurückgehen in die Tiefe?
DFS steht für Depth-First Search, auf Deutsch Tiefensuche. Vom aktuellen Knoten aus wählt es einen unbesuchten Nachbarn und bewegt sich weiter, bis ein Zweig so tief wie möglich erkundet wurde. Erreicht es eine Sackgasse, kehrt es zum vorherigen Knoten zurück und sucht nach einem weiteren noch nicht erkundeten Nachbarn. Dieser Rückkehrvorgang wird auch Backtracking genannt. ocw.mit.edu
DFS lässt sich leicht mit rekursiven Aufrufen implementieren. Beim Betreten eines Knotens markieren Sie ihn zunächst als besucht und rufen dann dieselbe Traversierungsfunktion für jeden unbesuchten Nachbarn dieses Knotens auf. Wenn ein rekursiver Aufruf endet, kehrt die Kontrolle auf natürliche Weise zu der Stelle zurück, die ihn aufgerufen hat. Dadurch wird der Ablauf des tiefen Vordringens und anschließenden Zurückgehens ausgedrückt.
Rekursion ist nicht die einzige Möglichkeit. DFS kann auch iterativ mit einem expliziten Stack implementiert werden. Ein Stack ist eine LIFO-Datenstruktur (Last In, First Out): Das zuletzt eingefügte Element wird zuerst entnommen. Durch das zuerst erfolgende Entnehmen des zuletzt entdeckten Knotens können Sie Tiefensuche-Verhalten erzeugen. Bei einer rekursiven Implementierung übernimmt der Aufruf-Stack des Programms diese Rolle implizit. ocw.mit.edugh.cp-algorithms.com
Von DFS erzeugte Elternzeiger können ebenfalls einen Pfad vom Startknoten zu einem Knoten zeigen. Dieser Pfad hat jedoch nicht garantiert die geringste Anzahl an Kanten. Da DFS dem zuerst gewählten Zweig möglichst tief folgt, kann es einen kürzeren Pfad in einem anderen Zweig erst später entdecken. ocw.mit.edu
Welche Arten der Strukturanalyse verwenden DFS?
DFS zeigt seinen Nutzen bei der Analyse der Graphstruktur, statt nur die Erreichbarkeit zu prüfen. Das Finden zusammenhängender Komponenten ist ein typisches Beispiel. In einem ungerichteten Graphen findet ein einmaliges Ausführen von DFS von einem beliebigen unbesuchten Knoten aus alle mit ihm verbundenen Knoten als eine Gruppe. Ein erneuter DFS-Start von einem verbleibenden unbesuchten Knoten findet eine weitere Gruppe.
Die Zyklenerkennung ist eine weitere häufige Anwendung von DFS. Ein Zyklus ist eine Struktur, bei der das Folgen von Kanten zum Startpunkt oder zu einem Knoten zurückführen kann, der bereits auf dem aktuellen Pfad liegt. In einem gerichteten Graphen können Sie einen Zyklus erkennen, indem Sie feststellen, ob Sie auf einen Knoten treffen, der bereits auf dem aktuellen rekursiven Pfad liegt. Deshalb müssen Sie zwischen einem Knoten, der lediglich einmal besucht wurde, und einem Knoten, der sich aktuell auf dem Traversierungspfad befindet, unterscheiden.
Die topologische Sortierung ordnet gerichtete Abhängigkeiten, beispielsweise Voraussetzungen zwischen Aufgaben, in einer Reihenfolge an. Sie ist nur in einem gerichteten azyklischen Graphen möglich, einem DAG. Ein DAG ist ein gerichteter Graph ohne Zyklus, der durch Folgen der Kantenrichtungen zu seinem Startpunkt zurückkehrt. Existiert ein Zyklus, entsteht ein Widerspruch – etwa wenn B vor A fertig sein muss und A vor B fertig sein muss –, sodass keine lineare Ordnung alle Kanten erfüllen kann. Eine Methode, die die Abschlussreihenfolge von DFS verwendet, ist eine Grundlage der topologischen Sortierung. algs4.cs.princeton.edu
Auch das Finden stark zusammenhängender Komponenten ist ein wichtiges, auf DFS basierendes Thema. Eine stark zusammenhängende Komponente ist eine Menge von Knoten in einem gerichteten Graphen, bei der je zwei Knoten derselben Gruppe einander erreichen können. Dieses Problem wird jedoch nicht durch nur ein einfaches DFS gelöst; es erfordert eine algorithmische Konstruktion, die Traversierungsreihenfolge und Kantenrichtungen nutzt. algs4.cs.princeton.edu
Welche Probleme entstehen ohne Besuchsmarkierungen?
In einem allgemeinen Graphen ist ein Array oder eine Menge für besuchte Knoten nicht optional, sondern für Terminierung und Korrektheit unerlässlich. Wenn A und B beispielsweise verbunden sind, können Sie von A nach B und dann von B zurück nach A gelangen. Ohne Prüfung des Besuchsstatus kann DFS rekursiv endlos zwischen A und B wechseln, und BFS kann denselben Knoten mehrfach in die Warteschlange einfügen. ocw.mit.edu
Der Begriff „besucht“ kann je nach Implementierung etwas unterschiedlich unterteilt werden. Bei BFS wird ein Knoten normalerweise in dem Moment als „entdeckt“ markiert, in dem er in die Warteschlange eingefügt wird. Bei DFS ist es üblich, einen Knoten direkt beim Eintritt in seine Funktion als besucht zu markieren. Bei anspruchsvollerer Analyse gerichteter Graphen kann zwischen einem unbesuchten Zustand, einem aktuell untersuchten Zustand und einem abgeschlossenen Zustand unterschieden werden.
Das Prinzip, jeden Knoten nur einmal zu besuchen, steht in direktem Zusammenhang mit der Traversierungseffizienz. Wenn Sie bereits verarbeitete Knoten nicht erneut erweitern, untersuchen Sie mit Adjazenzlisten jeden Knoten und jede Kante nur begrenzt oft. Außerdem ist klar, welcher Pfad einen Knoten zuerst entdeckt hat, wenn Sie einen Elternzeiger nur beim ersten Entdecken eines Knotens vergeben.
Um einen gesamten Graphen zu traversieren, benötigen Sie eine äußere Schleife. Untersuchen Sie jeden Knoten der Reihe nach, und starten Sie immer dann ein neues BFS oder DFS von ihm, wenn Sie einen noch nicht besuchten Knoten finden. In einem ungerichteten Graphen führt dies zu einer Traversierung nach zusammenhängenden Komponenten. In einem gerichteten Graphen verarbeitet es nacheinander die Bereiche, die in den gewählten Kantenrichtungen erreichbar sind. ocw.mit.edu
Warum hängt die Zeitkomplexität von der Graphdarstellung ab?
Die Zeitkomplexität von BFS und DFS wird häufig mit angegeben. Dies ist die Standardanalyse bei Verwendung von Adjazenzlisten. Eine Adjazenzliste speichert für jeden Knoten die Liste seiner direkt verbundenen Nachbarn. Mit Besuchsmarkierungen wird jeder Knoten einmal verarbeitet, und Kanten werden beim Durchlaufen der Nachbarlisten geprüft. Der Gesamtaufwand ist daher proportional zur Anzahl der Knoten plus der Anzahl der Kanten. ocw.mit.edu
Der zusätzliche Speicherbedarf beträgt üblicherweise . Darin enthalten sind das Besuchsarray, das Elternarray sowie die BFS-Warteschlange oder der DFS-Stack. Bei rekursivem DFS gehört auch der für die Rekursionstiefe benötigte Aufruf-Stack zum zusätzlichen Speicher. Es ist sinnvoll, zwischen dem Speicher für den Graphen selbst und dem zusätzlichen Speicher des Traversierungsalgorithmus zu unterscheiden. ocw.mit.edu
Eine Adjazenzmatrix speichert für jedes Knotenpaar in einer Tabelle, ob eine Kante existiert. Um die Nachbarn eines Knotens zu finden, müssen Sie möglicherweise jeden möglichen Knoten prüfen. Daher können BFS oder DFS mit einer Adjazenzmatrix typischerweise Zeit benötigen. Für dünn besetzte Graphen mit wenigen Kanten sind Adjazenzlisten besonders effizient, da sie nur tatsächlich verbundene Nachbarn durchsuchen. ocw.mit.edu
| Darstellung | Prüfung von Nachbarn | Typische Traversierungszeit |
|---|---|---|
| Adjazenzliste | Über die Liste der tatsächlich verbundenen Nachbarn iterieren | |
| Adjazenzmatrix | Verbindungen zu jedem möglichen Knoten prüfen |
Die Komplexitätsnotation beschreibt, wie der Ressourcenverbrauch mit wachsender Eingabegröße tendenziell zunimmt. Die tatsächliche Laufzeit wird außerdem durch Knotenkennungen, die Implementierung der Adjazenzlisten, das Speicherlayout und die Größe des vom Startpunkt der Traversierung aus erreichbaren Bereichs beeinflusst. Bei der Auswahl eines Algorithmus ist es dennoch sinnvoll, zunächst zu prüfen, ob der Graph dünn besetzt ist und wie er dargestellt wird.
Ist die tatsächliche Besuchsreihenfolge von BFS oder DFS festgelegt?
Nein. BFS folgt dem Prinzip, zuerst nähere Ebenen zu verarbeiten, und DFS dem Prinzip, den aktuellen Zweig tief zu erkunden. Welcher Knoten innerhalb derselben Ebene zuerst besucht wird oder welcher Zweig unter mehreren Nachbarn zuerst erkundet wird, hängt jedoch von der Speicherreihenfolge benachbarter Knoten ab. gh.cp-algorithms.comgh.cp-algorithms.com
Wenn beispielsweise die Nachbarliste von A in der Reihenfolge B, C vorliegt, entdeckt BFS in der Regel zuerst B. Wird die Liste in C, B geändert, kann C zuerst entdeckt werden. Bei DFS kann dieser Unterschied größere Auswirkungen haben. Ändert sich der zuerst gewählte Nachbar, ändert sich auch der tief erkundete Zweig selbst – ebenso wie der Traversierungsbaum und die durch Elternzeiger erzeugten DFS-Pfade.
Diese Tatsache ist bei der Bewertung eines Algorithmusergebnisses wichtig. Wenn ein Problem „die lexikografisch erste Besuchsreihenfolge“ verlangt, müssen Sie Adjazenzlisten sortieren oder eine Prioritätsregel festlegen. Wenn Sie dagegen nur Erreichbarkeit, die Anzahl zusammenhängender Komponenten oder Distanzen in der geringsten Kantenzahl benötigen, ist die genaue Reihenfolge auf derselben Ebene oder Tiefe möglicherweise nicht zentral für das Ergebnis.
Insbesondere bei einer iterativen DFS-Implementierung mit einem Stack kann die Reihenfolge, in der Nachbarn auf den Stack gelegt werden, die Umkehrung der Reihenfolge sein, in der sie tatsächlich entnommen werden. Wenn Sie dieselbe Besuchsreihenfolge wie bei einer rekursiven Implementierung mit einer bestimmten Adjazenzlistenreihenfolge erzielen möchten, müssen Sie die Richtung, in der Nachbarn auf den Stack gelegt werden, gezielt anpassen. Dies ist keine andere Definition von DFS, sondern ein Implementierungsunterschied aufgrund des LIFO-Verhaltens.
Was sind häufige Missverständnisse und Fehler?
Ein erstes Missverständnis besteht darin, dass BFS jede Art von Kürzeste-Wege-Problem löst. Wie bereits erläutert, garantiert BFS in einem ungewichteten Graphen die geringste Anzahl von Kanten. Unterscheiden sich die Gewichte, hat ein Zug nicht zwangsläufig denselben Wert wie ein anderer; damit ändert sich bereits das Problemmodell. algs4.cs.princeton.edualgs4.cs.princeton.edu
Zweitens wird manchmal angenommen, DFS verwende immer weniger Speicher als BFS. Einschließlich Besuchsarrays und Traversierungszustand können beide Algorithmen im Allgemeinen zusätzlichen Speicher benötigen. Die maximale Größe der Warteschlange oder des Stacks kann sich bei bestimmten Graphformen und Implementierungen unterscheiden, doch allein die asymptotische Komplexität begründet keinen bedingungslosen Vorteil für einen der beiden Algorithmen. ocw.mit.edu
Drittens ist die Annahme falsch, dass rekursives DFS für jede Eingabe sicher ist. In einem Graphen mit sehr großer Tiefe wächst auch die Rekursionstiefe. Sie sollten die Begrenzung des Aufruf-Stacks der Programmiersprache und Ausführungsumgebung berücksichtigen; in solchen Fällen kann eine iterative Implementierung mit explizitem Stack praktischer sein. Wichtig ist auch zu verstehen, dass der rekursive Aufruf-Stack Teil des zusätzlichen Speichers von DFS ist. ocw.mit.edu
Viertens darf ein gerichteter Graph nicht so behandelt werden, als wäre er ungerichtet. Die Existenz einer Kante von A nach B bedeutet nicht, dass Sie von B nach A gelangen können. Beim Speichern der Eingabe in Adjazenzlisten fügt ein ungerichteter Graph üblicherweise eine Kante zu den Listen beider Knoten hinzu, während ein gerichteter Graph sie nur zur Liste des Quellknotens hinzufügt. Dieser Unterschied verändert die Bedeutung von Erreichbarkeit, Zusammenhang und Zyklen. ocw.mit.edu
Fünftens sollte ein Traversierungsergebnis nicht mit einem eindeutigen korrekten Pfad verwechselt werden. Wenn mehrere Pfade dieselbe geringste Anzahl an Kanten haben, speichert BFS einen davon über Elternzeiger. DFS kann je nach Nachbarreihenfolge ebenfalls unterschiedliche Pfade erzeugen. Wenn der Pfad selbst eine Priorität benötigt, müssen Sortierregeln oder zusätzliche Bedingungen im Problem festgelegt werden.
Welche Kriterien sollten Sie bei der Auswahl für ein Problem verwenden?
Am besten formulieren Sie zunächst das Ziel in Worten. Wenn die Frage nur lautet: „Ist es vom Startpunkt aus erreichbar?“, sind sowohl BFS als auch DFS möglich; Sie können dann anhand der Implementierungsumgebung und der anschließend benötigten Analyse wählen. Benötigen Sie die geringste Anzahl an Kanten, etwa bei „Wie viele gleichartige Züge sind nötig, um anzukommen?“, ist BFS die naheliegende Wahl. Müssen Sie einen Pfad tief verfolgen und gleichzeitig die Struktur analysieren oder ist der Zeitpunkt des Zurückkehrens wichtig, ist DFS vermutlich geeignet.
Prüfen Sie als Nächstes, was die Kanten bedeuten. Stellen Sie fest, ob jede Bewegung dieselben Kosten hat oder ob Gewichte wie Zeit, Distanz oder Kosten beteiligt sind. Falls Gewichte existieren, wenden Sie die Kürzeste-Wege-Eigenschaft von BFS nicht direkt an. Prüfen Sie außerdem im Voraus, ob der Graph gerichtet ist, ob Zyklen möglich sind und ob der gesamte Graph untersucht werden muss. ocw.mit.edualgs4.cs.princeton.edu
Die Auswahlkriterien lassen sich wie folgt zusammenfassen.
| Situation oder Frage | Zuerst zu erwägende Methode | Zu beachtende Bedingungen |
|---|---|---|
| Geringste Anzahl an Zügen, Erweiterung Ebene für Ebene | BFS | Kantengewichte müssen gleich sein |
| Einfache Erreichbarkeit | BFS oder DFS | Erkunden nur den vom Startpunkt aus erreichbaren Teil |
| Finden zusammenhängender Komponenten als Gruppen | DFS oder BFS | Traversierung für jeden unbesuchten Knoten wiederholen |
| Analyse von Zyklen, topologischer Ordnung oder stark zusammenhängender Struktur | DFS-basierte Methoden | Topologische Sortierung ist nur in einem DAG möglich |
| Kürzeste Wege mit unterschiedlichen Zeiten oder Kosten | Andere gewichtete Kürzeste-Wege-Methode | Die Garantien von Standard-BFS gelten nicht |
Berücksichtigen Sie schließlich die Eingabegröße und Darstellung. Für einen dünn besetzten Graphen eignen sich Adjazenzlisten und die Standardanalyse für BFS und DFS gut. In Umgebungen, in denen die Rekursionstiefe problematisch werden kann, sollten Sie iteratives DFS erwägen. Wenn die Besuchsreihenfolge die Bewertung oder Geschäftsregeln beeinflusst, gehört auch die Reihenfolge der Adjazenzlisten zum Entwurf.
Fazit: Traversierungsziele und Bedingungen sind wichtiger als Namen
BFS und DFS sind unterschiedliche Strategien, um einen Graphen gründlich zu traversieren. BFS verwendet eine Warteschlange, um sich von nahegelegenen Knoten aus zu erweitern, und bietet den Vorteil von Pfaden mit der geringsten Kantenzahl in ungewichteten Graphen. DFS verwendet Rekursion oder einen Stack, um einen Zweig tief zu erkunden und zurückzugehen, und bildet die Grundlage für viele Verfahren zur Arbeit mit Graphstrukturen, darunter zusammenhängende Komponenten, Zyklen und topologische Sortierung in DAGs. ocw.mit.edualgs4.cs.princeton.edu
Beide benötigen Besuchsmarkierungen und haben bei Verwendung von Adjazenzlisten im Allgemeinen dieselbe asymptotische Zeitkomplexität. Entscheidend für die Wahl zwischen ihnen ist daher nicht eine einzelne Bezeichnung wie Geschwindigkeit, sondern was einen kürzesten Pfad definiert, ob Kanten gewichtet sind, wie Richtung und Zyklen zu interpretieren sind und ob der gesamte Graph verarbeitet werden muss. Wenn Sie diese Bedingungen zuerst unterscheiden, können Sie BFS und DFS für den richtigen Zweck einsetzen.