Różnica między krawędziami poprzecznymi i przednimi w DFT

W pierwszym drzewie głębokości znajdują się krawędzie, które definiują drzewo (tj. Krawędzie, które zostały użyte podczas przejścia).

Pozostały pewne krawędzie łączące niektóre inne węzły. Jaka jest różnica między krawędzią poprzeczną a przednią?

Z wikipedii:

Na podstawie tego drzewa łączącego krawędzie oryginalnego wykresu można podzielić na trzy klasy: krawędzie przednie, które wskazują od węzła drzewa do jednego z jego potomków, tylne krawędzie, które wskazują od węzła do jednego z jego przodków, i poprzeczne krawędzie, które też nie. Czasami krawędzie drzewa, które należą do samego drzewa opinającego, są klasyfikowane oddzielnie od krawędzi przednich. Jeśli oryginalny wykres nie jest przekierowywany, wówczas wszystkie jego krawędzie są krawędziami drzewa lub krawędziami tylnymi.

Czy krawędź, która nie jest używana podczas przejścia, która wskazuje od jednego węzła do drugiego, nie ustanawia relacji rodzic-dziecko?

Wikipedia ma odpowiedź:

Wszystkie rodzaje krawędzi pojawiają się na tym zdjęciu. Śledź DFS na tym wykresie (węzły są eksplorowane w kolejności numerycznej) i zobacz, gdzie zawodzi twoja intuicja.

To wyjaśni schemat:

Przednia krawędź: (u, v), gdzie v jest potomkiem u, ale nie krawędzią drzewa. Jest to krawędź inna niż drzewo, która łączy wierzchołek z potomkiem w drzewie DFS.

Krawędź poprzeczna: dowolna inna krawędź. Może przechodzić między wierzchołkami w tym samym drzewie o pierwszej głębokości lub w różnych drzewach o pierwszej głębokości. (laik)
Jest to dowolna inna krawędź na wykresie G. Łączy wierzchołki w dwóch różnych drzewach DFS lub dwa wierzchołki w tym samym drzewku DFS, z których żadne nie jest przodkiem drugiego. (formalne)

Przejście DFS na niekierowanym wykresie nie pozostawi krawędzi krzyżowej, ponieważ wszystkie krawędzie występujące na wierzchołku są badane.

Jednak na wykresie ukierunkowanym możesz natknąć się na krawędź prowadzącą do odkrytego wcześniej wierzchołka, tak że wierzchołek ten nie jest przodkiem ani potomkiem bieżącego wierzchołka. Taka krawędź nazywana jest krawędzią krzyżową.

W przejściu DFS węzły są kończone, gdy wszystkie ich dzieci są ukończone. Jeśli zaznaczysz czasy wykrywania i zakończenia dla każdego węzła podczas przejścia, możesz sprawdzić, czy węzeł jest potomkiem, porównując czasy rozpoczęcia i zakończenia. W rzeczywistości każde przejście DFS podzieli jego krawędzie zgodnie z następującą zasadą.

Niech d [węzeł] będzie czasem wykrywania węzła, podobnie niech f [węzeł] będzie czasem zakończenia.

Twierdzenie o nawiasach Dla wszystkich u, v, dokładnie jedno z następujących obejmuje:
1. d [u] <f [u] <d [v] <f [v] lub d [v] <f [v] <d [u ] <f [u] i żadne z u i v nie jest potomkiem drugiego.

2. d [u] <d [v] <f [v] <f [u] oraz v jest potomkiem u.

3. d [v] <d [u] <f [u] <f [v] au jest potomkiem v.

Zatem d [u] <d [v] <f [u] <f [v] nie może się zdarzyć.
Podobnie jak w nawiasach: () [], ([]) i [()] są OK, ale ([)] i [(]) nie są OK.

Weźmy na przykład wykres z krawędziami:
A -> B
A -> C
B -> C

Niech kolejność odwiedzin będzie reprezentowana przez ciąg etykiet węzłów, gdzie „ABCCBA” oznacza A -> B -> C (zakończone) B (zakończone) A (zakończone), podobnie jak ((())).

Zatem „ACCBBA” może być modelem dla „(() ())”.

Przykłady:
„CCABBA”: Zatem A -> C jest krawędzią krzyżową, ponieważ CC nie znajduje się wewnątrz A.
„ABCCBA”: Następnie A -> C jest krawędzią przednią (pośredni potomek).
„ACCBBA”: Zatem A -> C jest krawędzią drzewa (bezpośredni potomek).

Źródła:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm