Free Printable Przechodzenie po grafie BFS i DFS

Worksheets

Przechodzenie po grafie BFS i DFS

Total questions: 10

Worksheet time: 8mins

Name

Class

Date

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

10.

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