Algorytmy na grafach — sieci społeczne i metro w Paryżu

Po co się tego uczymy?

Google Maps, Facebook, Netflix — wszystkie te usługi "myślą" grafami: siecią połączeń między elementami. Zrozumienie, jak reprezentować i przeszukiwać graf, to jedna z najważniejszych umiejętności na maturze rozszerzonej, łącząca stos i kolejkę (poprzednia lekcja) w konkretne, praktyczne zastosowanie.

Teoria

Graf to zbiór punktów (wierzchołków) i połączeń między nimi (krawędzi) — sposób przedstawiania połączeń, zależności lub dróg między elementami. Przykłady: mapa dróg (miasta = wierzchołki, drogi = krawędzie), sieć społeczna (ludzie = wierzchołki, znajomości = krawędzie), metro (stacje = wierzchołki, tory = krawędzie).

Rodzaje grafów:

Graf nieskierowany — połączenie działa w OBIE strony (jeśli Tomek zna Olę, to Ola zna Tomka) — linia bez strzałki. Tak działa większość przyjaźni.
Graf skierowany — kierunek MA znaczenie (np. Tomek obserwuje Olę na Instagramie, ale Ola nie obserwuje Tomka) — rysujemy strzałkę.
Graf ważony — połączenia mają swoją "wartość" (długość drogi, czas przejazdu, koszt biletu) — każda krawędź ma "wagę". Używane np. do planowania tras w GPS-ach.

Reprezentacja grafu w Pythonie — najwygodniej jako SŁOWNIK, gdzie kluczem jest wierzchołek, a wartością LISTA jego sąsiadów: {"Ty": ["Ola", "Kuba"], "Ola": ["Ty", "Marcin"], ...}. Dzięki temu program może policzyć np. kto ma najwięcej znajomych (len(graf[osoba])), albo znaleźć DROGĘ między dwiema osobami.

Znajdowanie ŚCIEŻKI (dowolnej) — DFS (przeszukiwanie w głąb) — rekurencyjnie idziemy JAK NAJGŁĘBIEJ, oznaczając odwiedzone wierzchołki (żeby nie krążyć w kółko), aż trafimy na cel albo wyczerpiemy możliwości. To naturalne zastosowanie REKURENCJI (i "pod maską" — stosu, z poprzedniej lekcji).

Znajdowanie NAJKRÓTSZEJ ścieżki — BFS (przeszukiwanie wszerz) — zamiast iść jak najgłębiej, sprawdzamy wierzchołki WARSTWAMI: najpierw wszystkich BEZPOŚREDNICH sąsiadów startu, potem sąsiadów sąsiadów, itd. Dzięki temu PIERWSZA znaleziona ścieżka do celu jest gwarantowanie NAJKRÓTSZA (licząc liczbę krawędzi). BFS naturalnie wykorzystuje KOLEJKĘ (poprzednia lekcja) — collections.deque.

Zastosowania grafów: Google Maps (najkrótsza trasa, graf ważony — algorytm Dijkstry), Facebook/Instagram (sugerowanie znajomych, graf społeczny), Netflix/Spotify (polecanie filmów/piosenek podobnych do Twoich, graf podobieństw), sztuczna inteligencja i gry (planowanie ruchu postaci, dróg, strategii).

Schemat

GRAF ZNAJOMOŚCI (nieskierowany):
Ty ─── Ola ─── Marcin ─── Kasia
 
  Kuba

reprezentacja: {"Ty": ["Ola","Kuba"], "Ola": ["Ty","Marcin"],
                "Kuba": ["Ty"], "Marcin": ["Ola","Kasia"], "Kasia": ["Marcin"]}

BFS - przeszukiwanie WARSTWAMI (metro: Les Halles -> Concorde):
Warstwa 0: [Les Halles]
Warstwa 1: [Châtelet, Bastille]           (sąsiedzi Les Halles)
Warstwa 2: [Concorde]                     (sąsiad Châtelet) ← ZNALEZIONE, najkrótsza
Wynik: Les Halles -> Châtelet -> Concorde  (2 przystanki, gwarantowanie najkrótsza)

Przykład z życia

Paryskie metro — niektóre stacje (jak Châtelet) są bardzo "popularne", bo można z nich pojechać w wiele miejsc naraz — to węzły o wielu krawędziach w grafie. Gdy planujesz trasę z Les Halles do Concorde w aplikacji typu Google Maps, program "pod maską" przeszukuje graf stacji metra dokładnie algorytmem podobnym do BFS, żeby znaleźć NAJKRÓTSZĄ możliwą trasę.

graf_dfs.py

# Reprezentacja grafu jako słownika - sieć znajomych
graf = {
    "Ty": ["Ola", "Kuba"],
    "Ola": ["Ty", "Marcin"],
    "Kuba": ["Ty"],
    "Marcin": ["Ola", "Kasia"],
    "Kasia": ["Marcin"]
}

# Policz ilu znajomych ma każda osoba
for osoba in graf:
    print(f"{osoba} ma {len(graf[osoba])} znajomych: {graf[osoba]}")

# DFS (przeszukiwanie w głąb) - znajdź DOWOLNĄ ścieżkę
def znajdz_sciezke(graf, start, cel, odwiedzone=None):
    if odwiedzone is None:
        odwiedzone = set()
    if start == cel:
        return [start]
    odwiedzone.add(start)
    for sasiad in graf[start]:
        if sasiad not in odwiedzone:
            sciezka = znajdz_sciezke(graf, sasiad, cel, odwiedzone)
            if sciezka:
                return [start] + sciezka
    return None

print("Droga z Ciebie do Kasi:", znajdz_sciezke(graf, "Ty", "Kasia"))
# Wynik: Droga z Ciebie do Kasi: ['Ty', 'Ola', 'Marcin', 'Kasia']

graf_bfs_metro.py

# BFS (przeszukiwanie wszerz) - znajdź NAJKRÓTSZĄ ścieżkę (metro w Paryżu)
from collections import deque

metro = {
    "Châtelet": ["Les Halles", "Bastille", "Concorde"],
    "Les Halles": ["Châtelet", "Bastille"],
    "Bastille": ["Châtelet", "Les Halles"],
    "Concorde": ["Châtelet"]
}

def najkrotsza_trasa(graf, start, cel):
    kolejka = deque([[start]])   # kolejka ŚCIEŻEK, nie samych wierzchołków
    odwiedzone = set()
    while kolejka:
        sciezka = kolejka.popleft()
        stacja = sciezka[-1]
        if stacja == cel:
            return sciezka
        if stacja not in odwiedzone:
            odwiedzone.add(stacja)
            for sasiad in graf.get(stacja, []):
                nowa = list(sciezka)
                nowa.append(sasiad)
                kolejka.append(nowa)
    return None

print("Najkrótsza trasa:", najkrotsza_trasa(metro, "Les Halles", "Concorde"))
# Wynik: Najkrótsza trasa: ['Les Halles', 'Châtelet', 'Concorde']

Komentarz i wyjaśnienie kodu

W znajdz_sciezke() (DFS) zbiór odwiedzone jest KLUCZOWY — bez niego program mógłby wpaść w NIESKOŃCZONĄ pętlę, wracając w kółko między wierzchołkami, które już odwiedził (np. Ty→Ola→Ty→Ola...).

W najkrotsza_trasa() (BFS) kolejka przechowuje CAŁE ścieżki (listy), nie pojedyncze wierzchołki — dzięki temu, gdy znajdziemy cel, MAMY już gotową pełną trasę, a nie tylko informację "dotarliśmy". Kluczowa własność BFS: ponieważ przetwarzamy wierzchołki WARSTWAMI (najpierw wszystkich sąsiadów, potem sąsiadów sąsiadów), PIERWSZA znaleziona ścieżka do celu jest GWARANTOWANIE najkrótsza (licząc liczbę krawędzi/przystanków).

Ćwiczenie samodzielne

Uruchom oba przykłady (DFS dla sieci znajomych, BFS dla metra) i sprawdź wyniki. Dodaj nową osobę do grafu znajomych i sprawdź, czy znajdz_sciezke() poprawnie ją znajduje (albo zwraca None, jeśli nie ma połączenia).

Zadania do pracy własnej

Rozbuduj graf znajomych o 2-3 nowe osoby i ich połączenia. Napisz kod wypisujący, KTO ma najwięcej znajomych (wskazówka: użyj funkcji znajdz_max z lekcji o liderze, zastosowanej do liczby sąsiadów każdej osoby).
Rozbuduj graf metra o 3 nowe stacje i sprawdź działanie najkrotsza_trasa() dla różnych par stacji, w tym takiej pary, między którą nie ma połączenia (funkcja powinna zwrócić None).
Zaimplementuj graf WAŻONY (każda krawędź ma przypisaną "wagę" — np. czas przejazdu w minutach) i napisz uproszczoną wersję algorytmu Dijkstry znajdującą NAJKRÓTSZĄ trasę pod względem SUMY wag (nie liczby przystanków). Porównaj wynik z prostym BFS dla przypadku, gdy najkrótsza LICZBOWO trasa (mniej przystanków) wcale nie jest najszybsza CZASOWO.

Typowe błędy

Brak zbioru odwiedzone w DFS — bez śledzenia odwiedzonych wierzchołków program może wpaść w nieskończoną pętlę, krążąc między połączonymi wierzchołkami w kółko.

Mylenie DFS z BFS przy szukaniu NAJKRÓTSZEJ trasy — DFS znajduje JAKĄKOLWIEK ścieżkę (niekoniecznie najkrótszą!), tylko BFS gwarantuje najkrótszą (pod względem liczby krawędzi). Do zadań wymagających "najkrótszej trasy" zawsze używaj BFS (albo Dijkstry dla grafów ważonych).

Zapominanie o sprawdzeniu, czy wierzchołek w ogóle istnieje w grafie (graf.get(stacja, []) zamiast graf[stacja]) — użycie samego [] rzuci błąd KeyError, jeśli wierzchołek nie ma zdefiniowanych sąsiadów.

Nawiązanie do egzaminu zawodowego

Grafy i algorytmy BFS/DFS to jeden z najbardziej praktycznych tematów całego działu — bezpośrednio wykorzystuje stos i kolejkę (poprzednia lekcja) oraz rekurencję. W ostatniej lekcji tego działu podsumujesz WSZYSTKIE poznane algorytmy przez pryzmat analizy złożoności obliczeniowej (notacja Big-O) — w tym properny formalny opis, dlaczego BFS jest "lepszy" niż DFS do szukania najkrótszej trasy.