algorithm
Głębokie pierwsze wyszukiwanie

Wprowadzenie do głębokiego wyszukiwania

Głębokie wyszukiwanie jest algorytmem do przeszukiwania lub przeszukiwania struktur danych drzewa lub wykresu. Jeden zaczyna się od katalogu głównego i eksploruje w miarę możliwości wzdłuż każdej gałęzi przed cofnięciem. Wersja głębokiego poszukiwania została zbadana w XIX wieku przez francuskiego matematyka Charlesa Pierre'a Trémaux jako strategia rozwiązywania labiryntów.

Wyszukiwanie w pierwszej kolejności to systematyczny sposób znajdowania wszystkich wierzchołków dostępnych z wierzchołka źródłowego. Podobnie jak w przypadku pierwszego wyszukiwania, system plików DFS przechodzi przez podłączony element danego wykresu i definiuje drzewo opinające. Podstawową ideą pierwszego wyszukiwania w głąb jest metodyczne badanie każdej krawędzi. W razie potrzeby zaczynamy od różnych wierzchołków. Jak tylko odkryjemy wierzchołek, DFS zaczyna z niego eksplorować (w przeciwieństwie do BFS, który umieszcza wierzchołek w kolejce, aby później eksplorował z niego).

Spójrzmy na przykład. Przejdziemy przez ten wykres:

Przejdziemy przez wykres według następujących zasad:

• Zaczniemy od źródła.
• Żaden węzeł nie będzie odwiedzany dwukrotnie.
• Węzły, których jeszcze nie odwiedziliśmy, będą miały kolor biały.
• Węzeł, który odwiedziliśmy, ale nie odwiedziliśmy wszystkich jego węzłów potomnych, będzie miał kolor szary.
• Węzły całkowicie przemierzone będą w kolorze czarnym.

Spójrzmy na to krok po kroku:

Widzimy jedno ważne słowo kluczowe. To jest zabezpieczenie . Możesz zobaczyć. 5-1 nazywa się backedge. Jest tak, ponieważ jeszcze nie skończyliśmy z węzłem-1 , więc przejście z innego węzła do węzła-1 oznacza cykl na wykresie. W DFS, jeśli możemy przejść z jednego szarego węzła do drugiego, możemy być pewni, że wykres ma cykl. Jest to jeden ze sposobów wykrywania cyklu na wykresie. W zależności od węzła źródłowego i kolejności odwiedzanych węzłów możemy znaleźć dowolną krawędź w cyklu jako cofnięcie . Na przykład: jeśli najpierw zmienilibyśmy się na 5 z 1 , odkrylibyśmy 2-1 jako wsparcie.

Krawędź, którą bierzemy, aby przejść z szarego do białego węzła, nazywa się krawędzią drzewa . Jeśli zatrzymamy tylko krawędzie drzewa i usuniemy inne, otrzymamy drzewo DFS .

Na niekierowanym wykresie, jeśli możemy odwiedzić już odwiedzony węzeł, musi to być backedge . Ale w przypadku ukierunkowanych wykresów musimy sprawdzić kolory. Jeśli i tylko jeśli możemy przejść z jednego szarego węzła do drugiego szarego węzła, nazywa się to backedge .

W DFS możemy również przechowywać znaczniki czasu dla każdego węzła, których można używać na wiele sposobów (np .: Sortowanie topologiczne).

1. Gdy węzeł v zmienia się z białego na szary, czas jest zapisywany w d [v] .
2. Gdy węzeł v zmienia się z szarego na czarny, czas jest rejestrowany wf [v] .

Tutaj d [] oznacza czas odkrycia, a f [] oznacza czas zakończenia . Nasz kod pesudo będzie wyglądał następująco:

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

Złożoność:

Każdy węzeł i krawędź odwiedzane są raz. Zatem złożoność DFS wynosi O (V + E) , gdzie V oznacza liczbę węzłów, a E oznacza liczbę krawędzi.

Zastosowania głębokiego pierwszego wyszukiwania:

• Znajdowanie najkrótszej ścieżki dla wszystkich par na niekierowanym wykresie.
• Wykrywanie cyklu na wykresie.
• Znalezienie drogi.
• Sortowanie topologiczne.
• Testowanie, czy wykres jest dwustronny.
• Znajdowanie silnie połączonego komponentu.
• Rozwiązywanie zagadek za pomocą jednego rozwiązania.