Streszczenie Graf oraz przeszukiwanie wszerz i w głąb
Graf oraz Przeszukiwanie Wszerz i Wgłąb (BFS, DFS) – Poradnik
Grafy i algorytmy przeszukiwania: BFS i DFS
Grafy są podstawową strukturą danych w informatyce, służącą do modelowania złożonych relacji między obiektami. Zrozumienie, jak je przeszukiwać, jest kluczowe dla rozwiązywania wielu problemów, od nawigacji po sieciach społecznościowych. W tym materiale skupimy się na dwóch fundamentalnych algorytmach przeszukiwania grafów: przeszukiwaniu wszerz (BFS) i przeszukiwaniu w głąb (DFS).
Wprowadzenie do grafów
Graf, w najprostszej definicji, składa się z wierzchołków (lub węzłów) i krawędzi (lub łuków), które reprezentują połączenia między nimi. Wierzchołki to obiekty, a krawędzie to relacje.
Wierzchołek
Podstawowy element grafu, reprezentujący obiekt lub punkt.
Krawędź
Połączenie między dwoma wierzchołkami, reprezentujące relację.
Istnieją różne typy grafów:
- Graf nieskierowany: Krawędzie nie mają określonego kierunku. Jeśli istnieje krawędź między $A$ i $B$, relacja działa w obie strony. Na przykład, krawędź $(A, B)$ jest taka sama jak $(B, A)$.
- Graf skierowany (digraf): Krawędzie mają określony kierunek. Relacja działa tylko w jedną stronę. Krawędź $(A, B)$ oznacza, że można przejść z $A$ do $B$, ale niekoniecznie z $B$ do $A$.
- Graf ważony: Krawędzie mają przypisane wartości liczbowe, zwane wagami. Wagi mogą reprezentować odległość, koszt, czas itp.
- Graf nieważony: Krawędzie nie mają przypisanych wag; wszystkie krawędzie są traktowane jednakowo.
Reprezentacja grafów
Grafy muszą być przechowywane w pamięci komputera, aby algorytmy mogły na nich pracować. Istnieją dwie główne metody:
-
Macierz sąsiedztwa (Adjacency Matrix):
- Jest to dwuwymiarowa tablica o rozmiarze $V \times V$, gdzie $V$ to liczba wierzchołków. Element $macierz[i][j]$ ma wartość $1$ (lub wagę krawędzi), jeśli istnieje krawędź z wierzchołka $i$ do $j$, i $0$ (lub nieskończoność), jeśli jej nie ma.
- Zalety: Szybkie sprawdzanie istnienia krawędzi (stały czas $O(1)$), łatwa implementacja, dobra dla grafów gęstych (wiele krawędzi).
- Wady: Zajmuje dużo pamięci ($O(V^2)$), nawet dla grafów rzadkich (mało krawędzi). Iterowanie po sąsiadach wierzchołka wymaga przeszukania całego wiersza ($O(V)$).
-
Lista sąsiedztwa (Adjacency List):
- Jest to tablica list, gdzie każdy indeks odpowiada wierzchołkowi. Na pozycji $i$ znajduje się lista wszystkich wierzchołków, do których prowadzi krawędź z wierzchołka $i$.
- Zalety: Efektywna pamięciowo dla grafów rzadkich ($O(V + E)$, gdzie $E$ to liczba krawędzi), łatwe iterowanie po sąsiadach wierzchołka (czas proporcjonalny do liczby sąsiadów).
- Wady: Sprawdzanie istnienia krawędzi wymaga przeszukania listy sąsiedztwa (czas $O(\text{stopień wierzchołka})$).
Przeszukiwanie grafów
Przeszukiwanie grafu to systematyczne odwiedzanie wszystkich wierzchołków i krawędzi. Jest to podstawowa operacja dla wielu innych algorytmów grafowych.
Algorytm przeszukiwania wszerz (BFS – Breadth-First Search)
BFS eksploruje graf warstwami, odwiedzając najpierw wszystkich bezpośrednich sąsiadów wierzchołka startowego, potem sąsiadów tych sąsiadów i tak dalej. Wykorzystuje kolejkę do przechowywania wierzchołków do odwiedzenia.
Kolejka (Queue)
Struktura danych działająca na zasadzie FIFO (First In, First Out) – pierwszy element dodany jest pierwszym usuwanym.
Kroki algorytmu BFS:
- Utwórz kolejkę i dodaj do niej wierzchołek początkowy $s$.
- Oznacz wierzchołek $s$ jako odwiedzony.
- Dopóki kolejka nie jest pusta: a. Pobierz wierzchołek $u$ z początku kolejki. b. Dla każdego nieodwiedzonego sąsiada $v$ wierzchołka $u$: i. Oznacz $v$ jako odwiedzony. ii. Dodaj $v$ do kolejki. iii. Jeśli celem jest znalezienie najkrótszej ścieżki, zapisz,
Zarejestruj się po pełne podsumowanieMasz już konto? Zaloguj się
BFS i DFS w Grafach
Klíčová slova: Algorytmy przeszukiwania grafów
Klíčové pojmy: Graf składa się z wierzchołków i krawędzi, reprezentujących obiekty i relacje., Grafy mogą być skierowane, nieskierowane, ważone lub nieważone., Macierz sąsiedztwa i lista sąsiedztwa to dwie główne reprezentacje grafów., BFS (Breadth-First Search) przeszukuje graf warstwami, używając kolejki (FIFO)., BFS jest optymalny do znajdowania najkrótszej ścieżki w grafach nieważonych., DFS (Depth-First Search) przeszukuje graf w głąb jednej gałęzi, używając stosu (LIFO) lub rekurencji., DFS jest używany do wykrywania cykli i znajdowania spójnych składowych., Złożoność czasowa obu algorytmów to $O(V+E)$ dla listy sąsiedztwa i $O(V^2)$ dla macierzy sąsiedztwa., Podczas znajdowania najkrótszych ścieżek z BFS, należy śledzić poprzedników każdego wierzchołka., Kluczowe jest prawidłowe oznaczanie odwiedzonych wierzchołków, aby uniknąć nieskończonych pętli.