Grafy w praktyce: BFS, DFS, Dijkstra i A*, czyli jak wyznacza się trasę

Graf to najbardziej uniwersalna struktura z całej serii, bo prawie wszystko da się na niego przełożyć: mapa drogowa, zależności między pakietami, znajomości w serwisie społecznościowym, przepływ zadań, stany aplikacji. Wierzchołki i krawędzie – i nagle pytania „jak dojechać”, „czy da się to zainstalować”, „kogo znam przez znajomych” stają się tym samym pytaniem.

Ta część zamyka serię i jednocześnie łączy jej wątki: znajdzie się w niej kopiec jako kolejka priorytetowa, tablica mieszająca jako zbiór odwiedzonych i wyszukiwanie w wersji, która zamiast tablicy przeszukuje przestrzeń.

Jak zapisać graf

Dwie reprezentacje, jedna decyzja:

# Python
# Lista sąsiedztwa – pamięć O(V + E), naturalna dla grafów rzadkich (mapy, sieci)
graf = {
    "Jelenia Góra": [("Karpacz", 18), ("Szklarska Poręba", 25)],
    "Karpacz": [("Jelenia Góra", 18), ("Kowary", 9)],
    "Kowary": [("Karpacz", 9)],
}

# Macierz sąsiedztwa – pamięć O(V²), sensowna tylko dla gęstych grafów

Mapa drogowa jest grafem skrajnie rzadkim: z każdego skrzyżowania wychodzą 2–4 drogi, więc krawędzi jest rzędu liczby wierzchołków. Macierz sąsiedztwa dla miliona skrzyżowań miałaby bilion komórek – dlatego w praktyce zawsze widuje się listy sąsiedztwa.

Trzy algorytmy na jednej mapie

Poniżej ta sama siatka dla wszystkich trzech: start w lewym górnym rogu, meta w prawym dolnym, szare pola to ściany, a ciemniejsze – teren o koszcie 3 zamiast 1 (błoto, korek, stromizna).

Zwróć uwagę na trzy różne kształty zalewania mapy – i na liczby pod animacjami. Dla mapy, którą widzisz na starcie, wychodzi tak:

Trasa BFS-a jest krótsza w krokach, ale droższa – bo przeszła przez błoto, którego istnienia nie zauważyła. A* dał wynik identyczny z Dijkstrą, odwiedzając przy tym o 38% mniej pól. Przycisk Nowa mapa losuje inny układ; proporcje zostają.

BFS rozchodzi się równomiernie i znajduje trasę o najmniejszej liczbie kroków. Problem w tym, że kroki nie są równe: przejście przez błoto kosztuje trzy razy więcej. BFS o tym nie wie, bo w ogóle nie zna pojęcia wagi – dlatego jego trasa jest zwykle krótsza w krokach, ale droższa w koszcie.

# Python
from collections import deque

def bfs(graf, start, meta):
    """Najmniejsza LICZBA krawędzi. Kolejka FIFO – bez priorytetów, bez wag."""
    kolejka = deque([start])
    skad = {start: None}
    while kolejka:
        teraz = kolejka.popleft()
        if teraz == meta:
            return odtworz_trase(skad, meta)
        for sasiad, _waga in graf[teraz]:
            if sasiad not in skad:
                skad[sasiad] = teraz
                kolejka.append(sasiad)
    return None

Dijkstra (1959) zastępuje kolejkę FIFO kopcem: zawsze rozwija wierzchołek o najmniejszym znanym koszcie dojścia. Dzięki temu znajduje trasę najtańszą, a nie najkrótszą w krokach. Cena: rozlewa się we wszystkie strony jednakowo, bo nie ma pojęcia, gdzie jest meta.

# Python
import heapq

def dijkstra(graf, start, meta):
    """Najtańsza trasa. Wymaga wag nieujemnych – ujemna krawędź łamie założenie."""
    koszt = {start: 0}
    skad = {start: None}
    kopiec = [(0, start)]
    odwiedzone = set()
    while kopiec:
        dotad, teraz = heapq.heappop(kopiec)
        if teraz in odwiedzone:
            continue
        odwiedzone.add(teraz)
        if teraz == meta:
            return odtworz_trase(skad, meta), dotad
        for sasiad, waga in graf[teraz]:
            nowy = dotad + waga
            if nowy < koszt.get(sasiad, float("inf")):
                koszt[sasiad] = nowy
                skad[sasiad] = teraz
                heapq.heappush(kopiec, (nowy, sasiad))
    return None, None

A* (Hart, Nilsson i Raphael, 1968) to Dijkstra z jedną zmianą: z kopca zdejmujemy wierzchołek o najmniejszej sumie koszt dotychczasowy + oszacowanie pozostałej drogi. Wystarczy zamienić jedną linię:

# Python
heapq.heappush(kopiec, (nowy + heurystyka(sasiad, meta), sasiad))

Na siatce heurystyką jest odległość taksówkowa (suma różnic współrzędnych). Efekt widać w animacji gołym okiem: A* nie rozlewa się na boki, tylko celuje w metę, odwiedzając wyraźnie mniej pól niż Dijkstra – a trasę znajduje dokładnie tę samą, o tym samym koszcie.

Warunek, pod którym to działa, nazywa się dopuszczalnością heurystyki: oszacowanie nigdy nie może być większe niż rzeczywisty pozostały koszt. Odległość taksówkowa przy koszcie kroku co najmniej 1 spełnia to z zapasem. Gdy heurystyka zacznie przeszacowywać, A* zrobi się szybszy, ale przestanie gwarantować trasę optymalną – i to jest świadomy kompromis stosowany w grach.

DFS i jego zastosowania

Przeszukiwanie w głąb rzadko służy do szukania drogi – za to jest fundamentem kilku rzeczy, z których korzystasz codziennie:

• Wykrywanie cykli. Napotkanie wierzchołka, który jest jeszcze na stosie, oznacza cykl. Tak menedżer pakietów wykrywa zależności kołowe.
• Sortowanie topologiczne. Kolejność, w której można wykonać zadania z zależnościami: kompilacja modułów, migracje bazy, kolejność uruchamiania usług. To swoją drogą jedyny „sort”, którego nie było w serii o sortowaniu – bo nie porządkuje wartości, tylko zależności.
• Spójne składowe. Kto z kim jest połączony – w sieci, w grafie znajomości, w obrazie (wypełnianie obszaru).

Zbiory rozłączne: struktura, która prawie nic nie kosztuje

Na koniec struktura tak prosta, że mieści się w kilkunastu liniach, a odpowiada na pytanie „czy te dwa elementy są w tej samej grupie” praktycznie w czasie stałym:

# Python
class UnionFind:
    """Zbiory rozłączne z kompresją ścieżek i łączeniem według rangi."""

    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # kompresja ścieżki
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                   # już razem – to byłby cykl
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

Z kompresją ścieżek i łączeniem według rangi koszt operacji to O(α(n)), gdzie α to odwrotna funkcja Ackermanna – rosnąca tak wolno, że dla każdego n mieszczącego się we wszechświecie nie przekracza pięciu. W praktyce: stała.

Do czego to służy? Do wykrywania cykli przy budowaniu minimalnego drzewa rozpinającego (algorytm Kruskala), do grupowania elementów w jeden przebieg, do sprawdzania spójności sieci po awarii łącza.

Dlaczego nawigacja nie liczy Dijkstry na żywo

I tu dochodzimy do puenty całej serii. Mapa Polski to miliony wierzchołków. Dijkstra na takim grafie odwiedziłaby setki tysięcy skrzyżowań, zanim dotarłaby z Jeleniej Góry do Gdańska – zbyt wolno na aplikację, która ma odpowiedzieć w ułamku sekundy.

W Szlaku Jelonków trasy liczy OSRM, silnik routingu na danych OpenStreetMap. Jego sztuczka polega na tym, że całą ciężką pracę wykonuje wcześniej, podczas wstępnego przetwarzania mapy. Dokumentacja projektu wymienia dwa warianty: Contraction Hierarchies (osrm-contract) oraz Multi-Level Dijkstra (osrm-partition i osrm-customize), z zaleceniem, by domyślnie używać MLD, a CH zostawić do bardzo dużych macierzy odległości.

Idea CH jest elegancka: przed uruchomieniem serwera algorytm „skraca” mało istotne wierzchołki, dodając zamiast nich krawędzie skrótowe. Zapytanie o trasę przeszukuje potem hierarchię od dołu, dotykając ułamka oryginalnego grafu. MLD robi rzecz pokrewną, dzieląc mapę na regiony i licząc koszty przejścia między nimi – dzięki czemu przelicza się szybciej po zmianie danych o ruchu.

Wniosek jest ten sam, co przy indeksie w bazie z poprzedniej części: najtańsza praca to ta, którą wykonano wcześniej. Indeks płaci przy zapisie, żeby nie płacić przy odczycie. Contraction Hierarchies płaci przy imporcie mapy, żeby nie płacić przy każdym zapytaniu o trasę.

Koniec serii

Sześć części, jeden wątek przewodni: struktura danych to nie definicja do zapamiętania, tylko decyzja o tym, co ma być tanie. Tablica mieszająca robi tanim dostęp po kluczu i drogimi zakresy. Drzewo odwrotnie. Kopiec wybiera skrajność kosztem środka. B-drzewo poświęca prostotę, żeby zminimalizować liczbę odczytów z dysku. A wszystkie razem opierają się na tej samej obserwacji, od której zaczęła się seria o sortowaniu: to, ile coś kosztuje, zależy od tego, co wiesz o danych – i co zrobiłeś z tą wiedzą, zanim przyszło pierwsze zapytanie.