Unterschied zwischen Querkanten und Vorderkanten in einer DFT

In einem tiefen ersten Baum definieren die Kanten den Baum (dh die Kanten, die beim Durchlaufen verwendet wurden).

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 Spanning Tree können die Kanten des ursprünglichen Diagramms in drei Klassen unterteilt werden: Vorwärtskanten, die von einem Knoten des Baums zu einem seiner Nachkommen zeigen, Hinterkanten, die von einem Knoten zu einem seiner Vorfahren zeigen, und Querkanten, die beides nicht tun. Manchmal werden Baumkanten, Kanten, die zum Spannbaum selbst gehören, getrennt von den Vorderkanten klassifiziert. Wenn das ursprüngliche Diagramm ungerichtet ist, sind alle Kanten Baumkanten oder Hinterkanten.

Stellt eine Kante, die nicht in der Durchquerung verwendet wird, die von einem Knoten auf einen anderen zeigt, keine Eltern-Kind-Beziehung her?

Wikipedia hat die Antwort:

In diesem Bild erscheinen alle Arten von Kanten. Verfolgen Sie die DFS in diesem Diagramm (die Knoten werden in numerischer Reihenfolge untersucht) und sehen Sie, wo Ihre Intuition fehlschlägt.

Dies erklärt das Diagramm: -

Vorwärtskante: (u, v), wobei v ein Nachkomme von u, aber keine Baumkante ist. Es ist eine Nichtbaumkante, die einen Scheitelpunkt mit einem Nachkommen in einem DFS-Baum verbindet.

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)

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, die zu einem zuvor entdeckten Scheitelpunkt führt, sodass dieser Scheitelpunkt kein Vorfahr oder Nachkomme des aktuellen Scheitelpunkts ist. Eine solche Kante wird als Kreuzkante bezeichnet.

Bei einer DFS-Durchquerung werden Knoten beendet, sobald alle ihre untergeordneten Knoten fertig sind. 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 Entdeckungszeit des Knotens, sei auch f [Knoten] die Endzeit.

Satz in Klammern Für alle u, v gilt genau eine der folgenden Aussagen:
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.

2. d [u] <d [v] <f [v] <f [u] und v ist ein Nachkomme von u.

3. d [v] <d [u] <f [u] <f [v] und u ist ein Nachkomme von v.

Also kann d [u] <d [v] <f [u] <f [v] nicht passieren.
Wie Klammern: () [], ([]) und [()] sind OK, aber ([)] und [(]) sind nicht OK.

Betrachten Sie beispielsweise das Diagramm mit Kanten:
A -> B
A -> C
B -> C.

Die Reihenfolge des Besuchs soll durch eine Zeichenfolge der Knotenbezeichnungen dargestellt werden, 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 eine Querkante, da der CC nicht innerhalb von A liegt.
"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