Graf: BFS i DFS
Graf: BFS i DFS to interaktywny eksperyment z aplikacji Struktury danych – darmowej symulacji ze StudyFi Lab, która działa bezpośrednio w przeglądarce.
Przeszukiwanie wszerz (BFS) pobiera węzły z kolejki, więc najpierw odwiedza wszystkich sąsiadów startu, potem ich sąsiadów — warstwa po warstwie, dzięki czemu znajduje najkrótszą ścieżkę pod względem liczby krawędzi. Przeszukiwanie w głąb (DFS) pobiera węzły ze stosu i idzie jak najdalej, zanim się cofnie. Oba odwiedzają każdy węzeł i krawędź raz: O(V + E). BFS wykorzystują nawigacje i „znajomi znajomych”, DFS — labirynty i wykrywanie cykli.
Spróbuj: Przechodź krok po kroku od węzła 0 i porównuj kolejkę ze stosem. Potem zmień start na węzeł 7 — kolejność odwiedzin zmieni się całkowicie.
Najczęstsze pytania
Co pokazuje eksperyment „Graf: BFS i DFS”?
Przeszukiwanie wszerz (BFS) pobiera węzły z kolejki, więc najpierw odwiedza wszystkich sąsiadów startu, potem ich sąsiadów — warstwa po warstwie, dzięki czemu znajduje najkrótszą ścieżkę pod względem liczby krawędzi. Przeszukiwanie w głąb (DFS) pobiera węzły ze stosu i idzie jak najdalej, zanim się cofnie. Oba odwiedzają każdy węzeł i krawędź raz: O(V + E). BFS wykorzystują nawigacje i „znajomi znajomych”, DFS — labirynty i wykrywanie cykli.
Jak wypróbować „Graf: BFS i DFS”?
Przechodź krok po kroku od węzła 0 i porównuj kolejkę ze stosem. Potem zmień start na węzeł 7 — kolejność odwiedzin zmieni się całkowicie.
Uczysz się do sprawdzianu?
Wgraj swoje notatki, a StudyFi zrobi z nich fiszki, testy i podcasty.