DFS (Depth First Traversal) w strukturze danych: co to jest, zamawianie i aplikacje

Znaczenie DFS w strukturze danych

DFS w strukturze danych, znany również jako przechodzenie w głąb, to algorytm rekurencyjny używany głównie do wyszukiwania wszystkich wierzchołków struktury danych wykresu lub drzewa. Traversal to odwiedzenie każdego węzła grafu. Algorytm rozpoczyna się od węzła głównego (który może być dowolnym węzłem jako węzeł główny w grafie) i idzie tak daleko, jak to możliwe, wzdłuż każdej gałęzi przed cofaniem się.

Chodzi o to, aby zacząć od korzenia lub dowolnego węzła i zachować zaznaczony węzeł. Następnie musisz przejść do sąsiedniego węzła, który jest nieoznaczony i kontynuować tę pętlę, aż nie będzie żadnego nieoznaczonego sąsiedniego węzła. Następnie cofnij się i zbadaj inne nieoznaczone węzły i przemierz je. Ostatnim krokiem jest wydrukowanie węzłów w ścieżce.

Algorytm

Sformułuj funkcję rekurencyjną, która pobierze indeks węzła i odwiedzoną tablicę.

1. Pozostaw bieżący węzeł oznaczony jako odwiedzony, a następnie wydrukuj go.
2. Przejrzyj wszystkie sąsiednie nuty i te nieoznaczone i wywołaj funkcję rekurencyjną z indeksem sąsiedniego węzła.

Poznaj nasze popularne kursy inżynierii oprogramowania

Nieruchomości

Analiza czasu i przestrzeni w DFS w strukturze danych różni się w zależności od obszaru zastosowania. Teoretycznie DFS służy głównie do przekroczenia pełnego grafu i zajmuje czas O(|V|+|E|), gdzie |V| przedstawia liczbę wierzchołków i |E| przedstawia liczbę krawędzi. Ten wykres jest liniowy.

W tych aplikacjach przestrzeń O(|V|) jest również używana jako ostatnia deska ratunku do przechowywania stosu wierzchołków przechowywanych na ścieżce przeszukiwania i zbioru wierzchołków, które są już odwiedzone. Dlatego ustawienie granic czasowych i przestrzennych jest podobne do wyszukiwania wszerz. W tym przypadku dwa zastosowane algorytmy są mniej zależne od ich złożoności, a bardziej od różnych cech rzędów wierzchołków wytwarzanych przez oba algorytmy.

Jeśli chodzi o zastosowania DFS w strukturze danych związane z określonymi domenami, takie jak znajdowanie rozwiązań w indeksowaniu sieci lub sztucznej inteligencji, wykres, który wymaga przemierzania, może być zbyt obszerny, aby można go było odwiedzić w całości. W takich przypadkach wyszukiwanie jest wykonywane tylko do ograniczonej głębokości; ze względu na ograniczone zasoby, takie jak miejsce na dysku lub pamięć. Struktury danych nie są zwykle używane do śledzenia zestawu wszystkich odwiedzonych wcześniej wierzchołków. Wyszukiwanie przeprowadzone do ograniczonej głębokości nadal sprawia, że ​​czas staje się liniowy, jeśli chodzi o jednostkę rozszerzonych krawędzi i wierzchołków.

Pamiętaj jednak, że liczba ta nie ma tego samego rozmiaru co cały wykres, ponieważ niektóre wierzchołki mogą być przeszukiwane wielokrotnie, a inne nie.

W takich przypadkach DFS korzysta również z metod heurystycznych, aby wybrać bardziej obiecującą gałąź. Wreszcie, gdy nie można określić odpowiedniego limitu głębokości, a priori, powtarzane pogłębianie DFS jest wielokrotnie stosowane poprzez sekwencję rosnących limitów.

Ucz się kursów rozwoju oprogramowania online z najlepszych światowych uniwersytetów. Zdobywaj programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.

Algorytm pierwszego wyszukiwania głębokości

Każdy wierzchołek grafu w standardowej implementacji DFS jest podzielony na jedną z dwóch kategorii:

1. Nieodwiedzony
2. Odwiedzone

Algorytm jest używany do wskazania każdego wierzchołka i oznaczenia go jako odwiedzanego, a jednocześnie unikania cykli.

Tak działa algorytm DFS:

1. Umieść dowolny wierzchołek wykresu na stosie.
2. Element na szczycie stosu powinien zostać dodany do listy odwiedzonych.
3. Zrób listę przylegających węzłów tego wierzchołka i dodaj te, które nie znajdują się na liście odwiedzonych na szczycie stosu.
4. Powtarzaj poprzednie kroki, aż stos się opróżni.

Zamawianie DFS

Porządkowanie wierzchołków: Istnieją cztery sposoby liniowego porządkowania wierzchołków grafu lub drzewa w DFS:

1. Lista wierzchołków ułożonych w sposób, w jaki zostały one najpierw odwiedzone przez algorytm DFS, nazywa się pre-ordering. Jest to zwięzły sposób na opisanie postępu wyszukiwania.
2. Lista wierzchołków w kolejności, w jakiej były ostatnio odwiedzane przez algorytm, nazywana jest post-orderingiem.
3. Lista wierzchołków w kolejności odwrotnej do ich pierwszej wizyty jest odwrotną kolejnością wstępną. Dlatego nie należy go mylić z zamówieniem pocztowym.
4. Lista wierzchołków w kolejności odwrotnej do ich ostatniej wizyty jest odwróconą posortowaniem. Nie należy mylić tego z zamówieniem w przedsprzedaży.

Dodatkowo istnieje kolejność w kolejności i odwrotna kolejność dla drzew binarnych.

Głębokość First Search lub DFS dla wykresu

DFS dla grafu jest prawie taki sam jak DFS dla drzewa. Jedyna różnica polega na tym, że wykresy mogą mieć cykle, w przeciwieństwie do drzew. Węzeł może być odwiedzany wiele razy i aby uniknąć przetwarzania węzła, używana jest tablica odwiedzona typu Boolean.

Wyjście pierwszego wyszukiwania głębokości

Wyszukiwanie w głąb jest łatwiejsze do zobrazowania w postaci drzewa opinającego wierzchołków, do których już osiągnięto wyszukiwanie. Na podstawie tego drzewa opinającego oryginalne krawędzie grafu są podzielone na trzy klasy: krawędzie przednie, w których węzeł drzewa jest skierowany w stronę jednego z jego potomków, krawędzie tylne, w których węzeł jest skierowany w stronę jednego z jego przodków, oraz krawędzie poprzeczne , który nie wykonuje żadnej z poprzednich funkcji.

Zastosowania pierwszego przejścia w głąb (DFS)

Wyszukiwanie według głębokości jest wykorzystywane w następujących algorytmach jako element konstrukcyjny:

• Wyszukiwanie komponentów, które są połączone.
• Znajdowanie komponentów połączonych 2 (wierzchołkami lub krawędziami).
• Znajdowanie mostków grafu.
• Znajdowanie komponentów połączonych 3 (wierzchołkami lub krawędziami).
• Sortowanie topologiczne.
• Znajdowanie komponentów, które są silnie połączone.
• Ustalenie, czy gatunek jest podobny do jednego lub drugiego gatunku w drzewie filogenetycznym.
• Testy płaskości.
• Tworzenie słów w celu określenia zestawu granicznego dowolnej grupy.
• Rozwiązywanie zagadek, które mają tylko jedno rozwiązanie, np. labirynty.
• Pokolenie labiryntów .
• Poszukiwanie bi-łączności w grafach.

Pseudokod DFS i implementacja w Pythonie

Funkcja init() jest uruchamiana na każdym węźle w poniższym pseudokodzie, aby zapewnić odwiedzenie wszystkich wierzchołków. Jest to szczególnie ważne, ponieważ wykresy mogą mieć różne niepołączone obszary.

Oto pseudokod:

DFS(G, U)

u.odwiedzone = prawda

dla każdego v ∈ G.Adj[u]

jeśli v.visited == false

DFS(G,v)

w tym() {

Dla każdego G

u.odwiedzone = fałsz

Dla każdego G

DFS(G, U)

}

Oto implementacja DFS w Pythonie:

wykres = {

'5' : ['3′,'7'],

'2' : ['1', '3'],

'6' : ['7'],

'3' : [],

'4' : ['6'],

'7' : []

}

odwiedzone = set()

def dfs(odwiedzone, wykres, węzeł):

jeśli węzeł nie jest w odwiedzonym:

drukuj (węzeł)

odwiedzony.add(węzeł)

dla sąsiada w graph[node]:

dfs(odwiedzony, wykres, sąsiad)

print("To jest DFS:")

dfs(odwiedzone, wykres, '5')

Wyjście:

To jest DFS: 5

Poznaj nasze popularne kursy inżynierii oprogramowania

Złożoność Deep First Search

John Reif zbadał złożoność obliczeniową Depth First Search. Aby być precyzyjnym, w grafie danym faktem jest G, niech O będzie standardowym porządkiem wyznaczonym przez powtarzalny algorytm DFS. G reprezentuje wykres, a O reprezentuje wyjście porządkowania nadmiarowego algorytmu DFS. Te dane wyjściowe są nazywane leksykograficznym porządkowaniem DFS.

Wniosek

Głównym celem algorytmu DFS jest odwiedzanie każdego pojedynczego wierzchołka, który pozwala uniknąć cykli w grafach docelowych. Jeśli chcesz zaangażować się w zaawansowane wdrożenia operacji wyszukiwania lub operacji zamawiania, zdecydowanie powinieneś rozważyć skorzystanie z premium i holistycznego kursu w Depth First Search i Data Structure.

upGrad ma kilka najlepszych kursów DFS, takich jak Master of Science in Computer Science i Specialization in Big Data .

Jeśli starasz się zrobić kolejny krok i szukasz porady eksperta, UpGrad Mentorship stara się zapewnić Ci indywidualne sesje z najlepszymi doradcami zawodowymi i ekspertami w branży.