Przechodzenie po grafie BFS i DFS

Co znaczy skrót BFS?

• Binary-First Search
• Backward-First Search
• Best-First Search
• Breadth-First Search

Gdzie może zostać wykorzystywany algorytm BFS?

• W sortowaniu tablicy
• Do znalezienia odległości między dwoma węzłami lub wyznaczenia najkrótszej ścieżki między węzłami w grafach

• W obliczeniach matematycznych
• Do znalezienia odległości między dwoma węzłami w grafie skierowanym

Na czym polega przeszukiwanie grafu w algorytmie BFS?

• Losowe odwiedzanie wierzchołków grafu
• Przechodzenie do sąsiadujących wierzchołków dopiero po odwiedzeniu wszystkich wierzchołków na danym poziomie
• Wybieranie wierzchołków do odwiedzenia na podstawie ich identyfikatorów
• Odwiedzanie wszystkich sąsiadujących wierzchołków danego wierzchołka przed przejściem do kolejnego poziomu grafu.

Jaka jest złożoność obliczeniowa algorytmu BFS?

• O(V * E)
• O(log(V))
• O(V + E)
• O(V - E)

Strukturą pomocniczą przeszukiwania wszerz - BFS jest?

• Kopiec
• Stos
• Drzewo
• Kolejka

Rozwiń skrót DFS - przeszukiwanie wgłąb?

• Directional First Search
• Depth First Search
• Detailed First Search
• Dynamic First Search

Na czym polega przeszukiwanie wgłąb?

• Przechodzenie poziomów grafu bez odwiedzania wszystkich wierzchołków
• Losowe wybieranie wierzchołków do odwiedzenia
• Odwiedzanie wszystkich wierzchołków w danym grafie przed przejściem do kolejnego poziomu
• Wybieranie tylko wierzchołków o najmniejszej wartości

Strukturą pomocniczą przeszukiwania wgłąb jest?

• Kolejka
• Kopiec
• Tablica
• Stos

Gdzie wykorzystuje się przeszukiwanie wgłąb - DFS?

• W drzewie genealogicznym - jeżeli potrzebujemy możliwie najszybciej poznać imiona żyjących osób, które są na końcu drzewa

• W systemach rekomendacji znajomych w sieciach społecznościowych

• Tworzenie interfejsów graficznych
• Algorytmy sortowania tablicy

Ile wynosi złożoność obliczeniowa przeszukiwania wgłąb - DFS?

• O(V + E)
• O(log(V))
• O(V * E)
• O(V - E)