Przeszukiwanie wszerz (BFS)

Wprowadzenie

Przeszukiwanie wszerz (ang. Breadth-First Search, BFS) to fundamentalny algorytm przeszukiwania grafów, który odwiedza wierzchołki warstwa po warstwie, zaczynając od wierzchołka startowego.

BFS jest podstawą wielu algorytmów grafowych i ma szerokie zastosowanie: - Najkrótsza ścieżka w grafie nieważonym - Sprawdzanie spójności grafu - Znajdowanie składowych spójnych - Wykrywanie cykli w grafie nieskierowanym - Testowanie dwudzielności grafu - Crawlery internetowe - Systemy rekomendacji (znajomi znajomych)

Idea algorytmu BFS

Koncepcja "warstw"

BFS odwiedza wierzchołki w kolejności ich odległości od wierzchołka startowego:

Wierzchołek startowy: A

Warstwa 0: {A}              (odległość 0)
Warstwa 1: {B, C}           (odległość 1 od A)
Warstwa 2: {D, E, F}        (odległość 2 od A)
Warstwa 3: {G}              (odległość 3 od A)
...

Graf:
        A
       / \
      B   C
     / \   \
    D   E   F
         \ /
          G

Kolejność odwiedzania: A → B → C → D → E → F → G

Struktura danych: Kolejka (FIFO)

BFS wykorzystuje kolejkę (queue) do przechowywania wierzchołków do odwiedzenia:

  1. Dodaj wierzchołek startowy do kolejki
  2. Dopóki kolejka nie jest pusta:
  3. Pobierz wierzchołek z początku kolejki
  4. Odwiedź go (przetwórz)
  5. Dodaj wszystkich nieodwiedzonych sąsiadów na koniec kolejki

Kluczowa właściwość: FIFO (First In, First Out) gwarantuje odwiedzanie warstw po kolei.

Algorytm BFS - pseudokod

BFS(graf G, wierzchołek startowy s):
    1. Utwórz kolejkę Q
    2. Oznacz s jako odwiedzony
    3. Dodaj s do Q

    4. Dopóki Q nie jest pusta:
        a. u = Q.dequeue()  // Pobierz pierwszy element
        b. Dla każdego sąsiada v wierzchołka u:
            i.  Jeśli v nie jest odwiedzony:
                - Oznacz v jako odwiedzony
                - Ustaw parent[v] = u  // Opcjonalnie, do rekonstrukcji ścieżki
                - Q.enqueue(v)  // Dodaj na koniec kolejki

Złożoność: - Czasowa: O(V + E) - każdy wierzchołek i każda krawędź odwiedzane raz - Pamięciowa: O(V) - kolejka i tablica odwiedzonych

Implementacja BFS

Podstawowa implementacja

BFS z obliczaniem odległości

Wyjście:

Odległości od A:
  A: 0
  B: 1
  C: 1
  D: 2
  E: 2
  F: 2

BFS z rekonstrukcją ścieżki

BFS krok po kroku - wizualizacja

Wyjście:

=== BFS krok po kroku ===

Krok 0: Start z wierzchołka A
  Kolejka: ['A']
  Odwiedzone: {'A'}

Krok 1: Przetwarzam wierzchołek A
  Dodaję do kolejki: ['B', 'C']
  Kolejka: ['B', 'C']
  Odwiedzone: {'A', 'B', 'C'}

Krok 2: Przetwarzam wierzchołek B
  Dodaję do kolejki: ['D']
  Kolejka: ['C', 'D']
  Odwiedzone: {'A', 'B', 'C', 'D'}

Krok 3: Przetwarzam wierzchołek C
  Brak nowych sąsiadów (D już odwiedzony)
  Kolejka: ['D']
  Odwiedzone: {'A', 'B', 'C', 'D'}

Krok 4: Przetwarzam wierzchołek D
  Brak nowych sąsiadów
  Kolejka: []
  Odwiedzone: {'A', 'B', 'C', 'D'}

Zastosowania BFS

1. Najkrótsza ścieżka w grafie nieważonym

BFS gwarantuje znalezienie najkrótszej ścieżki w grafie nieważonym (lub gdzie wszystkie wagi = 1).

2. Sprawdzanie spójności grafu

Wyjście:

Graf 1 spójny? True
Graf 2 spójny? False

3. Znajdowanie składowych spójnych

Wyjście:

Składowe spójne:
  Składowa 1: {'A', 'B'}
  Składowa 2: {'C', 'D', 'E'}
  Składowa 3: {'F'}

4. Testowanie dwudzielności grafu

Graf jest dwudzielny, jeśli można pokolorować wierzchołki 2 kolorami tak, że żadne dwa sąsiednie wierzchołki nie mają tego samego koloru.

Wyjście:

Graf 1 dwudzielny? True
Kolorowanie:
  A: kolor 0
  B: kolor 1
  C: kolor 1
  D: kolor 0

Graf 2 (trójkąt) dwudzielny? False

5. Poziomy grafu (warstwy BFS)

Wyjście:

Poziomy BFS od A:
  Poziom 0: ['A']
  Poziom 1: ['B', 'C']
  Poziom 2: ['D', 'E', 'F']

BFS dla grafu skierowanego

Praktyczne zastosowanie: Sieć społecznościowa

Wyjście:

=== Sieć społecznościowa ===
Stopień separacji Alice-Frank: 3

Sugestie przyjaciół dla Alice (odległość ≤2):
  Diana (odległość: 2)
  Eve (odległość: 2)

Porównanie BFS vs DFS

Cecha BFS DFS
Struktura danych Kolejka (FIFO) Stos (LIFO) lub rekurencja
Kolejność odwiedzania Warstwami (poziom po poziomie) W głąb (do końca ścieżki)
Najkrótsza ścieżka ✅ Tak (nieważony) ❌ Nie
Pamięć O(V) - szerokość O(V) - głębokość
Zastosowania Najkrótsza ścieżka, poziomy Sortowanie topologiczne, cykle

(DFS szczegółowo w następnej lekcji!)

Podsumowanie

Kluczowe cechy BFS

  • Kolejka FIFO - gwarancja odwiedzania warstwami
  • Najkrótsza ścieżka w grafie nieważonym
  • Złożoność O(V + E) - efektywny
  • Wszechstronny - wiele zastosowań

Kiedy używać BFS?

✅ Najkrótsza ścieżka (nieważony graf) ✅ Sprawdzanie spójności ✅ Znajdowanie poziomów ✅ Testowanie dwudzielności ✅ Crawling (WWW, social networks)

Co dalej?

Po opanowaniu BFS, następne kroki to:

  1. Lekcja 57: Przeszukiwanie w głąb (DFS)
  2. Algorytm DFS (iteracyjny i rekurencyjny)
  3. Wykrywanie cykli
  4. Sortowanie topologiczne

  5. Silnie spójne składowe

  6. Lekcja 58: Algorytm Dijkstry

  7. Najkrótsza ścieżka w grafie ważonym
  8. Kolejka priorytetowa
  9. Optymalizacje

Zadania praktyczne

Zadanie 1: Wszystkie najkrótsze ścieżki

Zmodyfikuj BFS aby zwracał wszystkie najkrótsze ścieżki (jeśli jest ich wiele).

Zadanie 2: BFS z ograniczeniem

Zaimplementuj BFS, który zatrzymuje się po osiągnięciu maksymalnej odległości max_dist.

Zadanie 3: Wykrywanie cyklu (BFS)

Użyj BFS do wykrycia cyklu w grafie nieskierowanym.

Zadanie 4: Labirynt

Użyj BFS do znalezienia najkrótszej drogi w labiryncie reprezentowanym jako siatka 2D.

Następna lekcja: Przeszukiwanie w głąb (DFS) - alternatywna strategia przeszukiwania grafów

Wróć do spisu lekcji