Grafy – BFS i DFS – definicje

Co to jest BFS?

BFS (Breadth-First Search) to algorytm przeszukiwania grafu, który eksploruje sąsiadów w szerszym zakresie, poziomami.

Czym jest DFS?

DFS (Depth-First Search) to algorytm przeszukiwania grafu, który eksploruje jak najgłębiej, przechodząc do najdalszych węzłów.

Różnica między BFS a DFS

BFS przeszukuje poziomo, natomiast DFS pionowo (głębiej).

Zastosowanie BFS

BFS jest często używany w znajdowaniu najkrótszej ścieżki w grafach nieskierowanych.

Zastosowanie DFS

DFS znajduje zastosowanie w algorytmach topologicznych oraz w rozwiązywaniu problemów z cyklami.

Etykieta w BFS

BFS często wykorzystuje etykiety węzłów do oznaczania odwiedzonych węzłów.

Etykieta w DFS

DFS stosuje typowy mechanizm znaczników do weryfikacji odwiedzonych węzłów.

Co to jest graf?

Graf to zbiór węzłów (wierzchołków) i krawędzi, które je łączą.

Porównaj złożoność czasową BFS i DFS

Obydwa algorytmy mają złożoność O(V + E), gdzie V to liczba węzłów, a E krawędzi.

Prawda czy fałsz: DFS używa kolejki

Fałsz, ponieważ DFS używa stosu.

Jakie struktury danych używa BFS?

BFS używa kolejki do przechowywania węzłów do odwiedzenia.

Jakie struktury danych używa DFS?

DFS używa stosu lub rekurencji.

Uzupełnij zdanie: BFS działa na grafach ___

nieskierowanych i skierowanych.

Uzupełnij zdanie: DFS jest szczególnie przydatny w ___

rozwiązywaniu problemów z grafami z cyklami.

Co to jest węzeł w grafie?

Węzeł to podstawowy element grafu, reprezentujący obiekt.

Czy BFS znajduje najkrótszą ścieżkę?

Tak, w przypadku grafów nieskierowanych o równych wagach.