Odwiedzone
Na stosie
Sprawdzone krawędzie

  • Bieżący
  • Na stosie
  • Przetworzone
  • Ścieżka
Kliknięcie wierzchołka ustawia

Więcej o przeszukiwaniu w głąb

Przeszukiwanie w głąb (DFS)

Przeszukiwanie w głąb bada graf jak ktoś, kto idzie przez labirynt z ręką na ścianie: podąża jedną ścieżką tak daleko, jak się da, i cofa się dopiero wtedy, gdy nie ma dokąd pójść dalej. Robi to za pomocą stosu. Kliknij wierzchołek, aby od niego zacząć, wybierz cel, jeśli chcesz, i przejdź przeszukiwanie krok po kroku: zobacz, jak stos rośnie i maleje, jak każdy wierzchołek dostaje numer odwiedzin i które krawędzie zamykają cykl. Naciśnij Odtwórz, aby obejrzeć przeszukiwanie, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Kliknij wierzchołek, aby uczynić go startem; przełącz kliknięcie na Cel i kliknij inny wierzchołek, aby szukać ścieżki do niego. Liczba na każdym wierzchołku to kolejność, w jakiej został odwiedzony, a rząd pod grafem to stos, od startu aż do wierzchołka na szczycie. Nowy graf tworzy inny graf; wybierz, ile ma mieć wierzchołków i krawędzi. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.

Jak to działa

  1. Kliknij wierzchołek, aby uczynić go startem. Aby szukać ścieżki, przełącz kliknięcie na Cel i kliknij inny wierzchołek.
  2. Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce przeszukiwania.
  3. Obserwuj stos pod grafem i numer odwiedzin na każdym wierzchołku. Nowy graf tworzy inny graf do wypróbowania.

Jak działa przeszukiwanie w głąb

Połóż wierzchołek startowy na stosie. Następnie powtarzaj: spójrz na kolejnego sąsiada wierzchołka na szczycie stosu. Sąsiad, którego jeszcze nie widziano, dostaje następny numer odwiedzin, zapamiętuje wierzchołek, z którego do niego dotarto, i trafia na szczyt stosu, więc przeszukiwanie idzie dalej od niego. Gdy wierzchołek na szczycie nie ma już sąsiadów do sprawdzenia, jest przetworzony i schodzi ze stosu, a przeszukiwanie cofa się do wierzchołka pod nim. Gdy stos jest pusty, każdy osiągalny wierzchołek został odwiedzony.

Co mówi stos

Ponieważ przeszukiwanie zawsze idzie dalej od najnowszego wierzchołka, stos jest zawsze ścieżką od startu do sprawdzanego wierzchołka. Gdy cel zostanie osiągnięty, stos jest ścieżką do niego, choć zwykle nie najkrótszą: tę znajduje przeszukiwanie wszerz. W grafie nieskierowanym krawędź do wierzchołka, który wciąż jest na stosie, a nie jest tym, z którego właśnie przyszło, zamyka cykl. Zapamiętane wierzchołki tworzą drzewo, drzewo przeszukiwania w głąb, a kolejność, w jakiej wierzchołki zostają przetworzone, jest kluczem do sortowania topologicznego.

Często zadawane pytania

Czym jest przeszukiwanie w głąb?

To sposób badania grafu od wierzchołka startowego: podąża się jedną ścieżką tak głęboko, jak się da, i cofa się, by spróbować innej gałęzi, dopiero wtedy, gdy nie ma dokąd pójść dalej. Do zapamiętania drogi powrotnej służy stos lub rekurencja.

Czy przeszukiwanie w głąb znajduje najkrótszą ścieżkę?

Nie. Znajduje ścieżkę do celu, jeśli istnieje, ale może być ona dużo dłuższa niż trzeba, bo DFS trzyma się pierwszej gałęzi, którą wybierze. Do najmniejszej liczby krawędzi użyj przeszukiwania wszerz, a gdy krawędzie mają długości – algorytmu Dijkstry.

Czym różni się DFS od BFS?

Przeszukiwanie w głąb używa stosu i idzie głęboko jedną ścieżką, zanim się cofnie. Przeszukiwanie wszerz używa kolejki i rozchodzi się równomiernie, pierścień po pierścieniu. Oba odwiedzają każdy osiągalny wierzchołek w czasie rosnącym z liczbą wierzchołków plus krawędzi; BFS znajduje najkrótsze ścieżki, a DFS to naturalny wybór do cykli, labiryntów i sortowania topologicznego.

Jak DFS znajduje cykl?

Jeśli w grafie nieskierowanym przeszukiwanie trafi na krawędź do wierzchołka, który wciąż jest na stosie, i nie jest to wierzchołek, z którego właśnie przyszło, ta krawędź zamyka pętlę. W aplikacji mówi o tym wiersz stanu.

Czy mój graf jest gdzieś wysyłany?

Nie. Graf powstaje i jest przeszukiwany w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora