Fiszki do Graf oraz przeszukiwanie wszerz i w głąb
Graf oraz Przeszukiwanie Wszerz i Wgłąb (BFS, DFS) – Poradnik
Dotknij, aby odwrócić · Przesuń, aby nawigować
Algorytmy przeszukiwania grafów
57 fiszek
Fiszka 1
Pytanie: Czym jest graf i z jakich dwóch podstawowych elementów się składa?
Odpowiedź: Graf to fundamentalna struktura danych służąca do modelowania relacji, składająca się z wierzchołków (węzłów) i krawędzi (łuków lub połączeń).
Fiszka 2
Pytanie: Jakie są zastosowania grafów?
Odpowiedź: Grafy mogą być używane do modelowania sieci społecznościowych, map drogowych, zależności między zadaniami w projekcie.
Fiszka 3
Pytanie: Czym charakteryzuje się graf nieskierowany?
Odpowiedź: W grafie nieskierowanym krawędzie nie mają określonego kierunku, co oznacza, że relacja działa w obie strony (np. znajomość między dwiema osobami).
Fiszka 4
Pytanie: Czym różni się graf skierowany od nieskierowanego?
Odpowiedź: W grafie skierowanym (digrafie) krawędzie mają określony kierunek, co oznacza, że relacja działa tylko w jedną stronę (np. jednokierunkowa ulica), w p
Fiszka 5
Pytanie: Co to jest graf ważony i do czego służą wagi?
Odpowiedź: Graf ważony to graf, w którym krawędzie mają przypisane wartości liczbowe zwane wagami. Wagi mogą reprezentować odległość, koszt, czas lub przepustowo
Fiszka 6
Pytanie: Czym jest graf nieważony?
Odpowiedź: Graf nieważony to graf, w którym krawędzie nie mają przypisanych wag, a wszystkie krawędzie są traktowane jednakowo.
Fiszka 7
Pytanie: Jakie są dwie główne metody reprezentacji grafów w pamięci komputera?
Odpowiedź: Dwiema głównymi metodami reprezentacji grafów są macierz sąsiedztwa i lista sąsiedztwa.
Fiszka 8
Pytanie: Jak działa macierz sąsiedztwa jako reprezentacja grafu?
Odpowiedź: Macierz sąsiedztwa to dwuwymiarowa tablica V × V, gdzie element macierz[i][j] ma wartość 1 (lub wagę), jeśli istnieje krawędź z wierzchołka i do j, i
Fiszka 9
Pytanie: Wymień zalety macierzy sąsiedztwa.
Odpowiedź: Zalety macierzy sąsiedztwa to szybkie sprawdzanie istnienia krawędzi (O(1)), łatwość implementacji i dobra efektywność dla grafów gęstych.
Fiszka 10
Pytanie: Wymień wady macierzy sąsiedztwa.
Odpowiedź: Wady macierzy sąsiedztwa to duże zużycie pamięci (O(V²)), nawet dla grafów rzadkich, oraz konieczność przeszukania całego wiersza (O(V)) do iterowania