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

11

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?

soandos
źródło
Powiązane: cs.stackexchange.com/questions/99988/… dąży do ustalenia algorytmu, który dla ukierunkowanego wykresu będzie preferował tworzenie krawędzi przednich zamiast krawędzi poprzecznych podczas wyszukiwania od pierwszej głębokości.
pfalcon,

Odpowiedzi:

23

Wikipedia ma odpowiedź:

wprowadź opis zdjęcia tutaj

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)

Yuval Filmus
źródło
Dlaczego nie jest niemożliwe, aby najpierw przejść 6 (najpierw prawa strona)? Gdyby tak się stało, jak nazwano by to zbocze 2-> 3?
soandos
@soandos, proponuję poświęcić trochę czasu na prześledzenie algorytmu. Zakładając, że Wikipedysta nie popełnił błędu, obraz opisuje rzetelny przebieg DFS na tym wykresie, więc istnieje sposób, aby dopasować algorytm do tego śladu. Rodzaje krawędzi są wystarczająco jasno opisane w Wikipedii i możesz również zapoznać się z tym przykładem.
Yuval Filmus
Rozumiem, że jest to prawidłowy sposób wykonywania DFS. Pytam po prostu, co zrobiono w drugą stronę.
soandos
Wtedy wyniki byłyby inne. Przepraszam, musiałbyś sam to wypracować.
Yuval Filmus
2
@soandos Zasadniczo może istnieć wiele przejść DFS. Zastosowane tutaj pojęcia odnoszą się do jednego przejścia i będą się różnić dla wielu przejść.
Raphael
9

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ą.

Apoorv Gupta
źródło
Aporov, dziękuję za odpowiedź. Nadal wydaje mi się, że kiedy dojdziesz do wierzchołka 6 w DFS, jak pokazano na Wikipedii, masz trzy krawędzie do przejścia od 6. W tym momencie wierzchołek 6 jest „aktualny”. W końcu przejdziesz przez krawędź do wierzchołka 3. Chociaż 3 już odwiedzono, jednak ponieważ istnieje krawędź od 6 do 3, to 3 jest potomkiem „obecnego” wierzchołka 6. Jeśli tak, narusza to definicja krawędzi krzyżowej. W definicji musi być coś więcej, co nie jest bardzo wyraźne.
W rzeczywistości DFS zawiera tylko krawędzie drzewa dla krawędzi tylnych (wprowadzenie do algorytmów Thm. 22.10).
jrhee17,
2

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.

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

  2. 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

Chris Hafley
źródło