Warum DFS und nicht BFS zum Auffinden des Zyklus in Diagrammen?

82

Vorwiegend wird DFS verwendet, um einen Zyklus in Diagrammen und nicht in BFS zu finden. Irgendwelche Gründe? Beide können feststellen, ob beim Durchlaufen des Baums / Diagramms bereits ein Knoten besucht wurde.

schlechte Gesellschaft
quelle
3
In gerichteten Graphen kann nur DFS zum Erkennen eines Zyklus verwendet werden. In ungerichteten Diagrammen können jedoch beide verwendet werden.
Hengameh

Antworten:

71

Die Tiefensuche ist speichereffizienter als die Breitensuche, da Sie früher zurückverfolgen können. Es ist auch einfacher zu implementieren, wenn Sie den Aufrufstapel verwenden. Dies hängt jedoch davon ab, dass der längste Pfad den Stapel nicht überläuft.

Auch wenn Ihr Diagramm ist gerichtet dann müssen Sie nicht nur daran erinnern , wenn Sie einen Knoten oder nicht besucht haben, sondern auch , wie du da. Andernfalls könnten Sie denken, Sie hätten einen Zyklus gefunden, aber in Wirklichkeit haben Sie nur zwei separate Pfade A-> B, aber das bedeutet nicht, dass es einen Pfad B-> A gibt. Beispielsweise,

Wenn Sie BFS ab ausführen 0, wird erkannt, dass ein Zyklus vorhanden ist, aber tatsächlich kein Zyklus vorhanden ist.

Bei einer Tiefensuche können Sie Knoten beim Besuch als besucht markieren und beim Zurückverfolgen die Markierung aufheben. In den Kommentaren finden Sie eine Leistungsverbesserung für diesen Algorithmus.

Den besten Algorithmus zum Erkennen von Zyklen in einem gerichteten Graphen finden Sie im Tarjan-Algorithmus .

Mark Byers
quelle
3
(Speicher effizient, weil Sie schneller zurückverfolgen können, und einfacher zu implementieren, weil Sie den Stapel einfach für das Speichern der offenen Liste sorgen lassen können, anstatt sie explizit pflegen zu müssen.)
Amber
3
IMO, es ist nur einfacher, wenn Sie sich auf die Schwanzrekursion verlassen können.
Hank Gay
2
"Markieren Sie sie beim Zurückverfolgen" - auf eigene Gefahr! Dies kann leicht zu O (n ^ 2) -Verhalten führen, insbesondere würde eine solche DFS Querkanten als "Baum" -Kanten missverstehen ("Baum" -Kanten wären ebenfalls eine Fehlbezeichnung, da sie eigentlich keinen Baum mehr bilden würden)
Dimitris Andreou
1
@ Dimitris Andreo: Sie können drei besuchte Zustände anstelle von zwei verwenden, um die Leistung zu verbessern. Bei gerichteten Graphen gibt es einen Unterschied zwischen "Ich habe diesen Knoten schon einmal gesehen" und "Dieser Knoten ist Teil einer Schleife". Mit ungerichteten Graphen sind sie äquivalent.
Mark Byers
Genau, Sie benötigen definitiv einen dritten Zustand (um den Algorithmus linear zu machen), daher sollten Sie überlegen, diesen Teil zu überarbeiten.
Dimitris Andreou
28
  1. DFS ist einfacher zu implementieren
  2. Sobald DFS einen Zyklus gefunden hat, enthält der Stapel die Knoten, die den Zyklus bilden. Das Gleiche gilt nicht für BFS. Sie müssen also zusätzliche Arbeit leisten, wenn Sie auch den gefundenen Zyklus drucken möchten. Dies macht DFS viel bequemer.
IVlad
quelle
10

Ein BFS könnte sinnvoll sein, wenn das Diagramm ungerichtet ist (sei mein Gast, wenn es darum geht, einen effizienten Algorithmus mit BFS zu zeigen, der die Zyklen in einem gerichteten Diagramm meldet!), Wobei jede "Kreuzkante" einen Zyklus definiert. Wenn die Querkante {v1, v2}und die Wurzel (im BFS-Baum), die diese Knoten enthält, ist r, ist der Zyklus r ~ v1 - v2 ~ r( ~ist ein Pfad, -eine einzelne Kante), der fast so einfach wie in DFS gemeldet werden kann.

Der einzige Grund für die Verwendung eines BFS wäre, wenn Sie wissen, dass Ihr (ungerichteter) Graph lange Pfade und eine kleine Pfadabdeckung aufweist (mit anderen Worten, tief und schmal). In diesem Fall würde BFS proportional weniger Speicher für seine Warteschlange benötigen als der Stapel von DFS (beide natürlich immer noch linear).

In allen anderen Fällen ist die DFS eindeutig der Gewinner. Es funktioniert sowohl mit gerichteten als auch mit ungerichteten Graphen, und es ist trivial, die Zyklen zu melden. Konzentrieren Sie einfach eine beliebige Hinterkante auf den Pfad vom Vorfahren zum Nachkommen, und Sie erhalten den Zyklus. Alles in allem viel besser und praktischer als BFS für dieses Problem.

Dimitris Andreou
quelle
4

BFS funktioniert beim Finden von Zyklen nicht für einen gerichteten Graphen. Betrachten Sie A-> B und A-> C-> B als Pfade von A nach B in einem Diagramm. BFS wird sagen, dass nach dem Gehen eines der Pfade, die B besucht wird. Wenn Sie den nächsten Pfad weiterfahren, wird angezeigt, dass der markierte Knoten B erneut gefunden wurde, sodass ein Zyklus vorhanden ist. Hier gibt es eindeutig keinen Zyklus.

Aditya Raman
quelle
Können Sie erklären, wie DFS in Ihrem Beispiel eindeutig erkennt, dass der Zyklus nicht existiert? Ich stimme zu, dass der Zyklus in dem angegebenen Beispiel nicht existiert. Wenn wir jedoch von A-> B und dann von A-> C-> B gehen, werden wir finden dass B bereits besucht wurde und sein übergeordnetes Element A ist, nicht C..und ich habe gelesen, dass DFS den Zyklus erkennt, indem es das übergeordnete Element des bereits besuchten Elements mit dem aktuellen Knoten vergleicht, aus welcher Richtung wir in diesem Moment prüfen Was?
Smasher
Alles, was Sie hier gezeigt haben, ist, dass diese spezielle Implementierung nicht funktioniert und nicht, dass dies mit BFS unmöglich ist. In der Tat, es ist möglich, auch wenn es mehr Arbeit und Platz in Anspruch nimmt.
Beschneiden Sie
@Prune: Alle Threads (glaube ich) hier versuchen zu beweisen, dass bfs nicht zum Erkennen von Zyklen funktioniert. Wenn Sie wissen, wie man Beweise kontert, sollten Sie den Beweis erbringen. Nur zu sagen, dass die Anstrengungen größer sind, wird nicht ausreichen
Aditya Raman
Da der Algorithmus in den verlinkten Beiträgen angegeben ist, halte ich es nicht für angebracht, die Gliederung hier zu wiederholen.
Beschneiden Sie den
Ich konnte keine verlinkten Beiträge finden und wurde daher darum gebeten. Ich stimme Ihrem Standpunkt zur Fähigkeit von bfs zu und habe gerade über die Implementierung nachgedacht. Danke für den Tipp :)
Aditya Raman
3

Ich weiß nicht, warum so eine alte Frage in meinem Feed aufgetaucht ist, aber alle vorherigen Antworten sind schlecht, also ...

DFS wird verwendet, um Zyklen in gerichteten Graphen zu finden, da es funktioniert .

In einer DFS wird jeder Scheitelpunkt "besucht", wobei der Besuch eines Scheitelpunkts bedeutet:

  1. Der Scheitelpunkt wird gestartet
  2. Der von diesem Scheitelpunkt aus erreichbare Untergraph wird besucht. Dies umfasst das Verfolgen aller nicht verfolgten Kanten, die von diesem Scheitelpunkt aus erreichbar sind, und das Aufrufen aller erreichbaren nicht besuchten Scheitelpunkte.

  3. Der Scheitelpunkt ist fertig.

Das entscheidende Merkmal ist, dass alle von einem Scheitelpunkt aus erreichbaren Kanten verfolgt werden, bevor der Scheitelpunkt fertig ist. Dies ist eine Funktion von DFS, jedoch nicht von BFS. In der Tat ist dies die Definition von DFS.

Aufgrund dieser Funktion wissen wir, dass beim Starten des ersten Scheitelpunkts in einem Zyklus:

  1. Keine der Kanten im Zyklus wurde verfolgt. Wir wissen das, weil Sie sie nur von einem anderen Scheitelpunkt im Zyklus aus erreichen können, und wir sprechen über den ersten Scheitelpunkt, der gestartet wird.
  2. Alle nicht verfolgten Kanten, die von diesem Scheitelpunkt aus erreichbar sind, werden vor Abschluss verfolgt, und dies schließt alle Kanten im Zyklus ein, da noch keine von ihnen verfolgt wurde. Wenn es also einen Zyklus gibt, finden wir eine Kante zurück zum ersten Scheitelpunkt, nachdem dieser gestartet wurde, aber bevor er beendet ist. und
  3. Da alle Kanten, die verfolgt werden, von jedem gestarteten, aber nicht abgeschlossenen Scheitelpunkt aus erreichbar sind, zeigt das Finden einer Kante zu einem solchen Scheitelpunkt immer einen Zyklus an.

Wenn es also einen Zyklus gibt, finden wir garantiert eine Kante zu einem gestarteten, aber noch nicht abgeschlossenen Scheitelpunkt (2), und wenn wir eine solche Kante finden, ist uns garantiert, dass es einen Zyklus gibt (3).

Aus diesem Grund wird DFS verwendet, um Zyklen in gerichteten Graphen zu finden.

BFS bietet keine solchen Garantien, daher funktioniert es einfach nicht. (ungeachtet perfekt guter Algorithmen zur Zyklusfindung, die BFS oder ähnliches als Teilprozedur enthalten)

Ein ungerichteter Graph hat andererseits einen Zyklus, wenn zwischen einem Scheitelpunktpaar zwei Pfade liegen, dh wenn es sich nicht um einen Baum handelt. Dies ist während BFS oder DFS leicht zu erkennen. - Die Kanten, die auf neue Scheitelpunkte zurückgeführt werden, bilden einen Baum, und jede andere Kante zeigt einen Zyklus an.

Matt Timmermans
quelle
In der Tat ist dies die am meisten (vielleicht die einzige) Antwort hier, in der die tatsächlichen Gründe erläutert werden.
Plasmacel
2

Wenn Sie einen Zyklus an einer zufälligen Stelle in einem Baum platzieren, trifft DFS den Zyklus in der Regel, wenn er ungefähr die Hälfte des Baums bedeckt hat und die Hälfte der Zeit, in der er bereits den Zyklus durchlaufen hat, und die Hälfte der Zeit nicht ( und findet es im Durchschnitt in der Hälfte des restlichen Baumes), so dass es im Durchschnitt etwa 0,5 * 0,5 + 0,5 * 0,75 = 0,625 des Baumes bewertet.

Wenn Sie einen Zyklus an einer zufälligen Stelle in einem Baum platzieren, trifft BFS den Zyklus in der Regel nur dann, wenn die Ebene des Baums in dieser Tiefe ausgewertet wird. Daher müssen Sie normalerweise die Blätter eines Balance-Binärbaums bewerten, was im Allgemeinen dazu führt, dass mehr vom Baum bewertet werden. Insbesondere erscheint 3/4 der Zeit mindestens einer der beiden Links in den Blättern des Baums, und in diesen Fällen müssen Sie durchschnittlich 3/4 des Baums (wenn es einen Link gibt) oder 7 / bewerten. 8 des Baums (wenn es zwei gibt), sodass Sie bereits die Erwartung haben, 1/2 * 3/4 ​​+ 1/4 * 7/8 = (7 + 12) / 32 = 21/32 = zu suchen 0,656 ... des Baums, ohne die Kosten für die Suche nach einem Baum mit einem Zyklus zu addieren, der von den Blattknoten weg hinzugefügt wird.

Darüber hinaus ist DFS einfacher zu implementieren als BFS. Es ist also diejenige, die Sie verwenden sollten, es sei denn, Sie wissen etwas über Ihre Zyklen (z. B. befinden sich Zyklen wahrscheinlich in der Nähe der Wurzel, von der aus Sie suchen, und an diesem Punkt bietet Ihnen BFS einen Vorteil).

Rex Kerr
quelle
Viele magische Zahlen dort. Ich bin mit den Argumenten "DFS ist schneller" nicht einverstanden. Dies hängt vollständig von der Eingabe ab, und in diesem Fall ist keine Eingabe häufiger als eine andere.
IVlad
@Vlad - Die Zahlen sind nicht magisch. Sie sind Mittelwerte, werden als solche angegeben und sind unter den von mir angegebenen Annahmen fast trivial zu berechnen. Wenn die Annäherung an den Mittelwert eine schlechte Annäherung ist, wäre dies eine berechtigte Kritik. (Und ich habe ausdrücklich erklärt, dass sich die Antwort ändern könnte, wenn Sie Annahmen über die Struktur treffen könnten.)
Rex Kerr
Die Zahlen sind magisch, weil sie nichts bedeuten. Sie haben einen Fall angenommen, bei dem DFS besser abschneidet, und diese Ergebnisse auf den allgemeinen Fall hochgerechnet. Ihre Aussagen sind unbegründet: "DFS neigt dazu, den Zyklus zu erreichen, wenn es etwa die Hälfte des Baumes bedeckt": Beweisen Sie es. Ganz zu schweigen davon, dass Sie nicht über Zyklen in einem Baum sprechen können. Ein Baum hat per Definition keinen Zyklus. Ich verstehe nur nicht, worum es dir geht. DFS geht einen Weg, bis es in eine Sackgasse gerät, sodass Sie nicht wissen können, wie viel von dem GRAFIK (NICHT Baum) es durchschnittlich erforschen wird. Sie haben gerade einen zufälligen Fall ausgewählt, der nichts beweist.
IVlad
@Vlad - Alle nichtzyklischen, vollständig verbundenen, ungerichteten Diagramme sind (ungerootete, ungerichtete) Bäume. Ich meinte "ein Diagramm, das ein Baum wäre, abgesehen von einem falschen Link". Vielleicht ist dies nicht die Hauptanwendung für den Algorithmus - vielleicht möchten Sie Zyklen in einem verworrenen Diagramm finden, das sehr viele Links enthält, die es nicht zu einem Baum machen. Wenn es jedoch baumartig ist und über alle Diagramme gemittelt wird, ist es wahrscheinlich, dass jeder Knoten die Quelle dieser falschen Verbindung ist, wodurch die erwartete Baumabdeckung 50% beträgt, wenn die Verbindung getroffen wird. Ich akzeptiere also, dass das Beispiel möglicherweise nicht repräsentativ war. Aber die Mathematik sollte trivial sein.
Rex Kerr
1

Um zu beweisen, dass ein Graph zyklisch ist, müssen Sie nur beweisen, dass er einen Zyklus hat (die Kante zeigt entweder direkt oder indirekt auf sich selbst).

In der DFS nehmen wir jeweils einen Scheitelpunkt und prüfen, ob er einen Zyklus hat. Sobald ein Zyklus gefunden wurde, können wir die Überprüfung anderer Scheitelpunkte unterlassen.

In BFS müssen wir viele Scheitelpunktkanten gleichzeitig verfolgen und am Ende finden Sie meistens heraus, ob es einen Zyklus gibt. Mit zunehmender Größe des Diagramms benötigt BFS im Vergleich zu DFS mehr Platz, Berechnung und Zeit.

Spiker
quelle
0

Es hängt davon ab, ob es sich um rekursive oder iterative Implementierungen handelt.

Recursive-DFS besucht jeden Knoten zweimal. Iterative-BFS besucht jeden Knoten einmal.

Wenn Sie einen Zyklus erkennen möchten, müssen Sie die Knoten sowohl vor als auch nach dem Hinzufügen ihrer Nachbarschaften untersuchen - sowohl beim "Starten" eines Knotens als auch beim "Beenden" eines Knotens.

Dies erfordert mehr Arbeit in Iterative-BFS, sodass sich die meisten Benutzer für Recursive-DFS entscheiden.

Beachten Sie, dass eine einfache Implementierung von Iterative-DFS mit beispielsweise std :: stack das gleiche Problem wie Iterative-BFS hat. In diesem Fall müssen Sie Dummy-Elemente in den Stapel einfügen, um zu verfolgen, wann Sie die Arbeit an einem Knoten "beendet" haben.

In dieser Antwort finden Sie weitere Informationen dazu, wie Iterative-DFS zusätzliche Arbeit erfordert, um festzustellen, wann Sie mit einem Knoten "fertig" sind (beantwortet im Kontext von TopoSort):

Topologische Sortierung mit DFS ohne Rekursion

Hoffentlich erklärt dies, warum Leute Recursive-DFS für Probleme bevorzugen, bei denen Sie bestimmen müssen, wann Sie die Verarbeitung eines Knotens "beenden".

Gemeinschaft
quelle
Dies ist völlig falsch, da es keine Rolle spielt, ob Sie die Rekursion verwenden oder die Rekursion durch Iteration eliminieren. Sie können eine iterative DFS implementieren, die jeden Knoten zweimal besucht, genauso wie Sie eine rekursive Variante implementieren können, die jeden Knoten nur einmal besucht.
Plasmacel
0

Sie müssen verwenden, BFSwenn Sie den kürzesten Zyklus mit einem bestimmten Knoten in einem gerichteten Diagramm suchen möchten.

Z.B:Geben Sie hier die Bildbeschreibung ein

Wenn der angegebene Knoten 2 ist, gibt es drei Zyklen, in denen er Teil von - ist. [2,3,4] , [2,3,4,5,6,7,8,9]& ist [2,5,6,7,8,9]. Am kürzesten ist[2,3,4]

Um dies mit BFS zu implementieren, müssen Sie den Verlauf der besuchten Knoten mithilfe geeigneter Datenstrukturen explizit verwalten.

Für alle anderen Zwecke (z. B. um einen zyklischen Pfad zu finden oder um zu überprüfen, ob ein Zyklus vorhanden ist oder nicht) DFSist dies aus von anderen genannten Gründen die klare Wahl.

Sameer
quelle