Złożoność czasu DFS

DFS oznacza wyszukiwanie w głębi głębokości. Odnosi się do tego, w jaki sposób odwiedzane są węzły drzewa, dopóki nie zostanie położony żądany węzeł. Dla uproszczenia odwiedzane są wszystkie węzły w tym artykule. Chodzi o to, aby zobaczyć wszystkie węzły, z każdym węzłem odwiedzanym raz. Węzeł jest również nazywany wierzchołkiem. Pierwsze wyszukiwanie głębokości może znajdować się w jednym z trzech zamówień: zamówienie w przedsprzedaży, na zamówienie lub po zamówieniu. W tym artykule używane jest przejście w przedsprzedaży. W tym artykule wykorzystano następujące drzewo do zilustrowania zamówienia w przedsprzedaży do wyszukiwania głębokości:

Gałąź na drzewie nazywa się krawędzią. Ten artykuł ma na celu zilustrowanie tak zwanej złożoności czasowej w wyszukiwaniu głębokości. DFS jest najpierw wyjaśniany krótko. C ++ jest używany do ilustracji kodu.

Przejazd w przedsprzedaży w celu wyszukiwania głębokości

Algorytm jest następujący:

1) Odwiedź obecny wierzchołek.
2) Przecinaj lewą pod-drzewo bieżącego wierzchołka w sposób rekurencyjny.
3) Przemierzaj prawą pod-drzewo bieżącego wierzchołka w sposób rekurencyjny.

Dla poprzedniego drzewa pierwszym wierzchołkiem, który można odwiedzić. To jest obecny wierzchołek. Rekursywnie przemierzanie lewego pod drzewa, a następnie prawy pod-drzewo oznacza wizytę B, podczas gdy odwiedzanie C jest rejestrowane w pamięci, które można odwiedzić później.

W B, B jest obecnym wierzchołkiem. Rekursywnie przemierzanie lewego pod drzewa, a następnie prawy pod-drzewo oznacza wizytę e podczas wizyty F jest rejestrowana w pamięci, która ma zostać odwiedzona później.

W E, e jest obecnym wierzchołkiem. E nie ma lewego ani prawego podredura (żadnych krawędzi). Ostatnim nagrywaniem w pamięci do odwiedzin była odpowiednia pod-drzewo (krawędź) dla B. Prawy pod-drzewo dla B składa się z F poprzedzona jego krawędzią. W tym momencie F jest odwiedzany.

Poprzednie nagrywanie w pamięci do odwiedzin jest teraz prawym pod-drzewem (krawędzi) dla. Właściwa podprzestopia na nagrane składa się z C, a następnie jego krawędzie i dzieci. W tym momencie C jest odwiedzane. C ma trzy krawędzie. Zgodnie z algorytmem, lewa krawędź jest dostępna najpierw.

Po uzyskaniu dostępu lewej krawędzi, g jest odwiedzane. Nie ma dziecka na g. Przez algorytm H dzieli tego samego rodzica z G, a ponieważ jest po prawej stronie G, jest on następny.

„Ja” jest po prawej stronie H i dzieli tego samego rodzica z H. Przez algorytm każdy węzeł po prawej stronie innego węzła należy odwiedzić po odwiedzeniu węzła. Nie ma znaczenia, czy właśnie odwiedzony węzeł znajduje się po prawej stronie innego węzła. Więc „ja” jest odwiedzane dalej.

Po prawej stronie „ja” nie ma węzła. C i wszyscy jego potomkowie zostali odwiedzeni. Należy jednak pamiętać, że po prawej stronie jest węzeł. Ten węzeł jest D. Według algorytmu każdy węzeł po prawej stronie innego węzła należy odwiedzić po węźle (odwiedzone). Nie ma znaczenia, czy odwiedzony węzeł był po prawej stronie innego węzła. Więc D jest odwiedzany następny.

D ma dwoje dzieci, J i K. J jest po lewej stronie k. J jest odwiedzany najpierw przed k.

Algorytm wyszukiwania głębokości pierwszego można podsumować w następujący sposób: Po wizycie w korzeni odwiedź lewy wierzchołek. Od dolnej lewej wierzchołki odwiedź prawe rodzeństwo tego wierzchołka, a następnie rekurencyjnie idź w górę drzewa, praworę i od czasu do czasu odpada.

Dzięki temu sekwencja DFS poprzedniego drzewa to: a, b, e, f, c, g, h, i, d, j, k.

Złożoność czasu

Poprzednie drzewo ma 11 wierzchołków i 10 krawędzi. Jeśli drzewo jest dobrze przechowywane, skanowanie całego drzewa będzie obejmować 11 wierzchołków i 10 krawędzi. Jest to uznanie prędkości działania wyszukiwania głębokości. To złożoność czasu. Jest napisane jako:

O (| v |+| e |)

Gdzie | v | to liczba wierzchołków (węzłów) i | e | to liczba krawędzi. Dla tego drzewa suma wynosi 21 = 11 + 10. „O” musi tam być.

Struktura drzewa

Organizację drzew można opisać w następujący sposób:

Wierzchołek A: Dzieci: B, C, D
Wierzchołek B: Dzieci: E, F
Wierzchołek C: Dzieci: G, H, I
Vertex D: Dzieci: J, K
Wierzchołek e
Wierzchołek f
Wierzchołek g
Wierzchołek h
Wierzchołek i
Vertex j
Wierzchołek k

Poprzednie drzewo będzie przechowywane w nieorządkowanym_mapie wektorów. Wierzchołek jest kluczem, a dzieci są wartościami wektora klucza. Wierzchołki od E do K nie mają dzieci.

Kodowanie C ++

Program może rozpocząć się od następującego nagłówka:

#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;

Kodowanie C ++ dla nieorządkowanych wektorów

UNOPOREDRED_MAP-of-Vectors jest tworzony z następującym kodem:

UNOPORDED_MAP > umv = 'a', 'b', 'c', 'd',
'B', 'e', 'f',
'C', 'g', 'h', 'i',
'D', 'j', 'k',
'E', ,
'F', ,
'G', ,
'H', ,
'I', ,
'J', ,
'K', ;

Można to umieścić tuż pod poprzednim nagłówkiem.

Funkcja głębokości

Jest to funkcja rekurencyjna, która drukuje każdy odwiedzany wierzchołek (węzeł). To jest:

void DeepthFirstsearch (char Parent)
Cout << parent << "; //print vertex
dla (int i = 0; iDepthFirstSearch (umv [macierz] [i]);

Po wydrukowaniu lewego wierzchołka, pętla drukowałaby prawe wierzchołki. For pętka ma wycofanie.

Główna funkcja C ++

Odpowiednią główną funkcją programu jest:

int main (int argc, char ** argv)

DEPTHFIRSTSEARCH („A”);
Cout << endl;
powrót 0;

Algorytm do wyszukiwania głębokości jest następujący:

1) Odwiedź obecny wierzchołek.
2) Przecinaj lewą pod-drzewo bieżącego wierzchołka w sposób rekurencyjny.
3) Przemierzaj prawą pod-drzewo bieżącego wierzchołka w sposób rekurencyjny.

Można to interpretować w następujący sposób: Po wizycie w korzeni odwiedź lewy wierzchołek, rekurencyjnie spada po lewej stronie. Od dolnej lewej wierzchołka odwiedź prawe rodzeństwo tego wierzchołka i rekurencyjnie idź w górę drzewa, w prawo, od czasu do czasu, odpowiednio, odpowiednio.

Złożoność czasu dla algorytmu wyszukiwania głębokości pierwszego wynosi:

O (| v |+| e |)

Wniosek

DFS oznacza wyszukiwanie w głębi głębokości. Odnosi się do tego, w jaki sposób odwiedzane są węzły drzewa, dopóki nie zostanie położony żądany węzeł. Dla uproszczenia odwiedzono wszystkie węzły drzewa tego artykułu. Chodzi o to, aby odwiedzić wszystkie węzły, z każdym węzłem odwiedzanym raz. Węzeł jest również nazywany wierzchołkiem. Pierwsze wyszukiwanie głębokości może znajdować się w jednym z trzech zamówień: zamówienie w przedsprzedaży, na zamówienie lub po zamówieniu. W tym artykule zastosowano przejście w przedsprzedaży.