Test z Graf oraz przeszukiwanie wszerz i w głąb
Graf oraz Przeszukiwanie Wszerz i Wgłąb (BFS, DFS) – Poradnik
Test: Algorytmy przeszukiwania grafów
20 pytań
Pytanie 1: Mylenie złożoności O(V + E) dla grafu reprezentowanego listą sąsiedztwa ze złożonością O(V²) dla grafu reprezentowanego macierzą sąsiedztwa jest typowym błędem prowadzącym do nieefektywności algorytmu.
A. Tak
B. Nie
Wyjaśnienie: Niezrozumienie złożoności, polegające na myleniu złożoności O(V + E) dla listy sąsiedztwa ze złożonością O(V²) dla macierzy sąsiedztwa, jest wymienione jako typowy błąd i pułapka. Wybór odpowiedniej reprezentacji grafu jest kluczowy dla efektywności algorytmu.
Pytanie 2: Algorytm przeszukiwania w głąb (DFS) jest używany głównie do znajdowania najkrótszej ścieżki w grafach nieważonych, mierzonej liczbą krawędzi.
A. Tak
B. Nie
Wyjaśnienie: Zgodnie z materiałami, to algorytm przeszukiwania wszerz (BFS) jest najważniejszym zastosowaniem do znajdowania najkrótszej ścieżki w grafach nieważonych. DFS jest natomiast używany do wykrywania cykli, znajdowania spójnych składowych, sortowania topologicznego i rozwiązywania problemów z labiryntami, ale nie do znajdowania najkrótszych ścieżek w grafach nieważonych.
Pytanie 3: Algorytm przeszukiwania wszerz (BFS) eksploruje graf warstwami, odwiedzając najpierw wierzchołki bliższe wierzchołkowi początkowemu.
A. Tak
B. Nie
Wyjaśnienie: Zgodnie z materiałami, algorytm BFS "odwiedza wszystkie jego bezpośrednie sąsiady, następnie wszystkich sąsiadów tych sąsiadów i tak dalej, warstwa po warstwie" oraz "odwiedza wierzchołki w kolejności rosnącej odległości od wierzchołka startowego". W tabeli porównawczej wskazano również, że "Sposób przeszukiwania" dla BFS to "Warstwami, najpierw bliższe wierzchołki".
Pytanie 4: Algorytm BFS jest odpowiednim narzędziem do znajdowania najkrótszej ścieżki, mierzonej wagą krawędzi, w grafie ważonym, gdzie krawędzie mają zróżnicowane wartości.
A. Tak
B. Nie
Wyjaśnienie: Algorytm BFS znajduje najkrótszą ścieżkę tylko w grafach nieważonych (lub ważonych, gdzie wszystkie wagi są równe), mierzoną liczbą krawędzi. Dla grafów ważonych z zróżnicowanymi wagami krawędzi należy użyć innych algorytmów, takich jak algorytm Dijkstry lub Bellmana-Forda.
Pytanie 5: W celu znalezienia najkrótszej ścieżki w grafie nieważonym, BFS gwarantuje, że wszystkie wierzchołki na odległości k+1 od źródła zostaną odwiedzone przed wierzchołkami na odległości k.
A. Tak
B. Nie
Wyjaśnienie: BFS eksploruje graf warstwami, gwarantując, że wszystkie wierzchołki na odległości k od źródła zostaną odwiedzone przed wierzchołkami na odległości k+1. Stwierdzenie w pytaniu odwraca tę kolejność, co jest nieprawdziwe.