W pierwszym drzewie głębi znajdują się krawędzie definiujące drzewo (tj. Krawędzie, które były używane w traversal).
Istnieją pewne pozostałości krawędzi łączące niektóre inne węzły. Jaka jest różnica między krawędzią poprzeczną a krawędzią przednią?
Z Wikipedii:
Na podstawie tego drzewa rozpinającego krawędzie pierwotnego wykresu można podzielić na trzy klasy: krawędzie przednie, które wskazują od węzła drzewa do jednego z jego potomków, krawędzie tylne, które wskazują od węzła do jednego z jego przodków, oraz krawędzie poprzeczne, które nie mają takiego znaczenia. Czasami krawędzie drzewa, które należą do samego drzewa opinającego, są klasyfikowane oddzielnie od krawędzi przednich. Jeśli oryginalny wykres jest nieukierunkowany, to wszystkie jego krawędzie są krawędziami drzewa lub tylnymi krawędziami.
Nie ma krawędzi, która nie jest używana w przemierzaniu, wskazuje z jednego węzła na drugi, ustanawiając relację rodzic-dziecko?
Komentarze
- Powiązane: cs.stackexchange.com/questions/99988/… ma na celu ustalenie algorytmu, który w przypadku grafu skierowanego będzie wolał tworzyć przednie krawędzie zamiast krzyżujących się krawędzi podczas wyszukiwanie w głębi.
Odpowiedź
Wikipedia ma odpowiedź:
Na tym obrazku pojawiają się wszystkie typy krawędzi. Prześledź DFS na tym wykresie (węzły są badane w kolejności numerycznej) i zobacz, gdzie intuicja zawodzi.
To wyjaśnia diagram: –
Przednia krawędź: (u, v), gdzie v jest potomkiem u, ale nie jest krawędzią drzewa To jest krawędź niebędąca drzewem która łączy wierzchołek z potomkiem w drzewie DFS.
Skrzyżowanie: dowolna inna krawędź. Może przechodzić między wierzchołkami w tym samym drzewie z pierwszą głębią lub w różnych drzewach z pierwszą głębią. (laik)
To jest jakakolwiek inna krawędź w grafie G. Łączy wierzchołki w dwóch różnych drzewach DFS lub dwa wierzchołki w tym samym drzewie DFS, z których żaden nie jest przodkiem drugiego. (formalne)
Komentarze
- Dlaczego nie jest niemożliwe, aby 6 został przekroczony jako pierwszy (prawa strona najpierw)? Gdyby tak się stało, jak zostałaby nazwana krawędź 2- > 3?
- @soandos, sugeruję, abyś poświęcił trochę czasu na prześledzenie algorytmu. Zakładając, że wikipedyści nie ' popełnili błąd, obraz przedstawia autentyczny przebieg DFS na tym wykresie, więc istnieje sposób na dopasowanie algorytmu do tego śladu. Typy krawędzi są wystarczająco jasno opisane w Wikipedii i możesz również zapoznać się z tym przykładem.
- Rozumiem, że jest to poprawny sposób wykonywania DFS. Po prostu pytam, co by było, gdyby zostało to zrobione w inny sposób.
- Wtedy wyniki byłyby inne. ' przepraszam, ' musiałbyś sam to rozwiązać.
- @soandos Ogólnie rzecz biorąc, bardzo dobrze może być wielokrotnym przejściem DFS. Użyte tutaj pojęcia odnoszą się do jednego podanego przejścia i będą się różnić dla wielu przejść.
Odpowiedź
Przejście DFS na wykresie nieukierunkowanym nie pozostawi krawędzi poprzecznej, ponieważ badane są wszystkie krawędzie, które występują na wierzchołku.
Jednak na wykresie skierowanym możesz natknąć się na krawędź która prowadzi do wierzchołka, który został wcześniej odkryty, tak że wierzchołek ten nie jest przodkiem ani potomkiem bieżącego wierzchołka. Taka krawędź nazywana jest poprzeczną krawędzią.
Komentarze
- Aporov, Dziękuję za odpowiedź. Nadal wydaje mi się, że kiedy dojdziesz do wierzchołka 6 w DFS, jak pokazano na schemacie w Wikipedii, masz trzy krawędzie do przejścia od 6. W tym momencie wierzchołek 6 jest ” bieżący „. Ostatecznie masz zamiar przejść przez krawędź do wierzchołka 3. Chociaż 3 zostało już odwiedzone, ale ponieważ istnieje krawędź od 6 do 3, to 3 jest potomkiem ” prądu ” wierzchołek 6. Jeśli tak jest, narusza to definicję krawędzi poprzecznej. W definicji musi być coś więcej, niż ' t wyrażona bardzo wyraźnie.
- W rzeczywistości DFS zawiera tylko krawędzie drzewa dla tylnych krawędzi (wprowadzenie do Algorytmy Thm. 22.10).
Odpowiedź
W przemierzaniu DFS węzły są kończone, gdy wszystkie ich elementy podrzędne są skończone. Jeśli zaznaczysz czasy odnajdywania i zakończenia dla każdego węzła podczas przemierzania, 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ą regułą.
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, jest dokładnie jedna z następujących zachowań:
1.d [u] < f [u] < d [v] < f [ v] lub d [v] < f [v] < d [u] < f [u] i żadne z uiv nie jest potomkiem drugiego.
d [u] < d [v] < f [v] < f [u] i v jest potomkiem u.
d [v] < d [u] < f [u] < f [v] i u jest potomkiem v.
Więc, d [u] < d [v] < f [u] < f [v] nie może się zdarzyć.
Lubię nawiasy: () [], ([]) i [()] są OK, ale ([)] i [(]) nie są OK.
Rozważ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 (gotowe) B (gotowe) A (gotowe), podobnie do ((())).
Zatem „ACCBBA” może być wzorem dla „(() ())”.
Przykłady:
„CCABBA”: Wtedy A -> C to krzyżyk krawędź, ponieważ CC nie znajduje się wewnątrz A.
„ABCCBA”: Wtedy A -> C jest przednią krawędzią (pośrednim potomkiem).
„ACCBBA”: Wtedy A -> C jest krawędzią drzewa (bezpośredni potomek).
Źródła:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Notatki do wykładu http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm