In einem Tiefenbaum definieren die Kanten den Baum (dh die Kanten, die in der verwendet wurden) Durchquerung).
Es gibt einige übrig gebliebene Kanten, die einige der anderen Knoten verbinden. Was ist der Unterschied zwischen einer Querkante und einer Vorderkante?
Aus Wikipedia:
Basierend auf diesem Spannbaum werden die Kanten Der ursprüngliche Graph kann in drei Klassen unterteilt werden: Vorderkanten, die von einem Knoten des Baums zu einem seiner Nachkommen zeigen, Hinterkanten, die von einem Knoten zu einem seiner Vorfahren zeigen, und Kreuzkanten, die beides nicht tun. Manchmal werden Baumkanten, Kanten, die zum Spanning Tree selbst gehören, getrennt von den Vorderkanten klassifiziert. Wenn das ursprüngliche Diagramm ungerichtet ist, sind alle seine Kanten Baumkanten oder Hinterkanten.
Keine Kante, die beim Durchlaufen nicht verwendet wird Punkte von einem Knoten zum anderen stellen eine Eltern-Kind-Beziehung her?
Kommentare
- Verwandte Themen: cs.stackexchange.com/questions/99988/… versucht, einen Algorithmus zu etablieren, der für gerichtete Graphen während der Ausführung von Vorwärtskanten anstelle von Kreuzkanten bevorzugt Tiefensuche.
Antwort
Wikipedia hat die Antwort:
In diesem Bild werden alle Arten von Kanten angezeigt. Verfolgen Sie die DFS in diesem Diagramm (die Knoten werden in numerischer Reihenfolge untersucht) und sehen Sie, wo Ihre Intuition schlägt fehl.
Dies erklärt das Diagramm: –
Vorwärtskante: (u, v), wobei v ein Nachkomme von u ist, aber keine Baumkante Es ist eine Nicht-Baumkante Dies verbindet einen Scheitelpunkt mit einem Nachkommen in einem DFS-Baum.
Kreuzkante: jede andere Kante. Kann zwischen Scheitelpunkten in demselben Tiefenbaum oder in verschiedenen Tiefenbäumen wechseln. (Laie)
Es ist eine beliebige andere Kante in Grafik G. Sie verbindet Scheitelpunkte in zwei verschiedenen DFS-Bäumen oder zwei Scheitelpunkte in demselben DFS-Baum, von denen keiner der Vorfahr des anderen ist. (formal)
Kommentare
- Warum ist es nicht unmöglich, dass 6 zuerst durchlaufen wurden (rechte Seite zuerst)? Wenn dies geschehen wäre, wie würde die 2- > 3-Kante aufgerufen worden sein?
- @soandos. Ich schlage vor, Sie nehmen sich die Zeit, um den Algorithmus selbst zu verfolgen. Unter der Annahme, dass die Wikipedianer ‚ keinen Fehler gemacht haben, beschreibt das Bild einen echten DFS-Lauf in diesem Diagramm. Daher gibt es eine Möglichkeit, den Algorithmus in diese Ablaufverfolgung einzupassen. Die Arten von Kanten sind in Wikipedia klar genug beschrieben, und Sie können auch dieses Beispiel konsultieren.
- Ich verstehe, dass dies eine gültige Methode für eine DFS ist. Ich frage nur, was passiert, wenn es anders gemacht wird.
- Dann wären die Ergebnisse anders. Es tut mir ‚ leid, Sie ‚ müssten es selbst herausfinden.
- @soandos Im Allgemeinen gibt es dort kann sehr gut mehrere DFS-Durchquerungen sein. Die hier verwendeten Begriffe beziehen sich auf eine bestimmte Durchquerung und unterscheiden sich für mehrere Durchquerungen.
Antwort
Eine DFS-Durchquerung in einem ungerichteten Diagramm hinterlässt keine Querkante, da alle Kanten, die auf einen Scheitelpunkt fallen, untersucht werden.
In einem gerichteten Diagramm können Sie jedoch auf eine Kante stoßen Dies führt zu einem Scheitelpunkt, der zuvor entdeckt wurde, sodass dieser Scheitelpunkt kein Vorfahr oder Nachkomme des aktuellen Scheitelpunkts ist. Eine solche Kante wird als Kreuzkante bezeichnet.
Kommentare
- Aporov, vielen Dank für die Antwort. Es scheint mir immer noch, dass, wenn Sie zum Scheitelpunkt 6 in der DFS gelangen, wie in Wikipedia dargestellt, Sie drei Kanten von 6 durchlaufen müssen. Zu diesem Zeitpunkt ist Scheitelpunkt 6 “ current „. Schließlich werden Sie die Kante zum Scheitelpunkt 3 durchlaufen. Während 3 bereits besucht wurde, ist 3 ein Nachkomme des Stroms „, da es eine Kante von 6 bis 3 gibt “ Scheitelpunkt 6. Wenn dies der Fall ist, verstößt dies gegen die Definition einer Querkante. Die Definition muss etwas mehr enthalten, das nicht ‚ nicht sehr explizit gemacht wird.
- Tatsächlich enthält DFS nur eine der Baumkanten für Hinterkanten (Intro to Algorithmen Thm. 22.10).
Antwort
Bei einer DFS-Durchquerung werden Knoten beendet, sobald alle ihre untergeordneten Elemente vorhanden sind fertig. Wenn Sie die Erkennungs- und Endzeiten für jeden Knoten während des Durchlaufs markieren, können Sie überprüfen, ob ein Knoten ein Nachkomme ist, indem Sie die Start- und Endzeiten vergleichen. Tatsächlich partitioniert jede DFS-Durchquerung ihre Kanten gemäß der folgenden Regel.
Sei d [Knoten] die Erkennungszeit des Knotens, sei auch f [Knoten] die Endzeit.
Klammersatz Für alle u, v gilt genau einer der folgenden Punkte:
1.d [u] < f [u] < d [v] < f [ v] oder d [v] < f [v] < d [u] < f [u] und keiner von u und v ist ein Nachkomme des anderen.
d [u] < d [v] < f [v] < f [u] und v ist ein Nachkomme von u.
d [v] < d [u] < f [u] < f [v] und u ist ein Nachkomme von v.
Also, d [u] < d [v] < f [u] < f [v] kann nicht passieren.
Gefällt mir Klammern: () [], ([]) und [()] sind in Ordnung, aber ([)] und [(]) sind nicht in Ordnung.
Betrachten Sie beispielsweise das Diagramm mit den Kanten:
A -> B
A -> C
B -> C
Lassen Sie die Reihenfolge des Besuchs durch darstellen eine Zeichenfolge der Knotenbezeichnungen, wobei „ABCCBA“ A -> B -> C (fertig) B (fertig) A (fertig) bedeutet, ähnlich wie ((())).
„ACCBBA“ könnte also ein Modell für „(() ())“ sein.
Beispiele:
„CCABBA“: Dann ist A -> C ein Kreuz Kante, da sich der CC nicht innerhalb von A befindet.
„ABCCBA“: Dann ist A -> C eine Vorwärtskante (indirekter Nachkomme).
„ACCBBA“: Dann ist A -> C eine Baumkante (direkter Nachkomme).
Quellen:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm