Grafy i drzewa — modelowanie świata

🎯 Po co Ci to?

Oto struktura, która modeluje prawie wszystko: mapa dróg (miasta i połączenia), sieć społecznościowa (ludzie i znajomości), internet (strony i odnośniki), zależności zadań w projekcie, cząsteczki chemiczne, rozgrywki, labirynty. Wszystkie te niepodobne rzeczy to jeden byt matematyczny — graf. Nauczyć się widzieć graf pod powierzchnią problemu to jedna z najpotężniejszych umiejętności informatyka, bo problem sprowadzony do grafu dziedziczy dziesiątki gotowych, potężnych algorytmów. To zwieńczenie działu o strukturach i całej części o algorytmice — miejsce, gdzie „modelowanie" (etap 2 myślenia komputacyjnego z 1.1!) pokazuje pełnię mocy.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• opisać graf (wierzchołki, krawędzie) i jego odmiany oraz rozpoznać drzewo jako graf szczególny;
• modelować grafem realne sytuacje (mapa, sieć znajomości, zależności);
• opisać dwa podstawowe przeszukiwania grafu (wszerz i w głąb) i ich silniki (kolejka, stos).

🔁 Przypomnij sobie

Z 1.6: redukcja — sprowadź nowy problem do znanego; z 9.2/9.3: stos i kolejka; z 7.1: drzewo katalogów, rozgałęzienia.

📘 Wyjaśnienie

📐 DEFINICJA — graf: zbiór wierzchołków (obiektów) połączonych krawędziami (relacjami). Krawędzie mogą być skierowane (jednokierunkowe: „A obserwuje B") lub nieskierowane („A i B się znają"), a także ważone (z liczbą: długość drogi, koszt).

Po ludzku: kropki i łączące je linie — ale te kropki i linie mogą znaczyć cokolwiek. Czym NIE jest: rysunkiem. Graf to struktura relacji; jego rysunek to tylko jedna z reprezentacji. Ten sam graf można narysować na sto sposobów albo w ogóle nie rysować (trzymać jako listę połączeń).

Siła grafu leży w jego ogólności. Popatrz, jak jeden byt modeluje niepodobne światy:

Świat	Wierzchołki	Krawędzie	Rodzaj
mapa dróg	miasta	drogi	nieskierowany, ważony (km)
sieć społecznościowa	ludzie	znajomości	nieskierowany
„obserwuje" na portalu	konta	obserwacje	skierowany
strony WWW	strony	odnośniki	skierowany
zależności zadań	zadania	„musi być przed"	skierowany
cząsteczka	atomy	wiązania	nieskierowany

Gdy sprowadzisz swój problem do grafu, dziedziczysz gotowe algorytmy: najkrótsza droga (nawigacja — kopiec z 9.4!), wykrywanie cykli (czy w zależnościach zadań nie ma błędnego koła?), spójność (czy z każdego miasta dojedziesz do każdego?), kolorowanie (czy da się ułożyć plan lekcji bez konfliktów?). To jest redukcja z 1.6 w najpotężniejszym wydaniu: nie rozwiązujesz problemu od zera — rozpoznajesz w nim graf i sięgasz po znane.

Drzewo — graf szczególny. Drzewo (znasz je z 7.1: katalogi; z 6.6: scalanie; z 9.4: kopiec) to graf spójny bez cykli. Ma dokładnie jedną drogę między każdą parą wierzchołków — i dlatego nadaje się do hierarchii: system plików, struktura firmy, drzewo decyzyjne, drzewo wyszukiwań binarnych (uporządkowane drzewo, w którym szukanie to znane połowienie — 6.2!). Każde drzewo jest grafem, nie każdy graf jest drzewem: cykl (droga wracająca do startu) albo rozspójnienie odróżniają „zwykły" graf od drzewa.

Przeszukiwanie grafu. Podstawowe pytanie: „jak odwiedzić wszystkie wierzchołki osiągalne ze startu?". Dwie strategie, każda napędzana znaną strukturą:

• Wszerz (BFS): odwiedzaj najpierw sąsiadów, potem sąsiadów sąsiadów — kręgami coraz dalej od startu. Silnik: kolejka (9.3) — dokładasz nowo odkryte na koniec, obsługujesz od przodu. BFS znajduje najkrótszą drogę (w liczbie krawędzi): stąd „stopnie oddalenia" w sieci znajomości.
• W głąb (DFS): idź jak najdalej jednym korytarzem, przy ślepym zaułku cofnij się do ostatniego rozgałęzienia. Silnik: stos (9.2) — dosłownie jak przechodzenie labiryntu z 9.2. DFS jest naturalny rekurencyjnie (7.1) i świetny do wykrywania cykli czy przechodzenia całej struktury.

Ta sama rama (odwiedzaj, oznaczaj odwiedzone, dokładaj sąsiadów), dwie struktury pomocnicze, dwa zachowania — kolejka daje kręgi, stos daje głębokie nurkowanie. Wszystkie struktury tego działu spotykają się tutaj, w silniku przeszukiwania grafu.

💭 Pomyśl: „Sześć stopni oddzielenia" mówi, że dowolnych dwoje ludzi łączy łańcuch najwyżej sześciu znajomości. Które przeszukiwanie grafu znajduje najkrótszy taki łańcuch — i czemu nie to drugie?

Sprawdź odpowiedź

BFS (wszerz) — bo odwiedza wierzchołki w kolejności rosnącej odległości od startu: najpierw znajomi (1 stopień), potem znajomi znajomych (2 stopnie)… Pierwszy raz, gdy natrafi na szukaną osobę, jest na najkrótszej drodze. DFS (w głąb) mógłby dotrzeć do celu okrężną drogą przez pół sieci, zanim sprawdzi bliskich znajomych — znalazłby jakiś łańcuch, nie najkrótszy. Reguła: najkrótsza droga w liczbie krawędzi = BFS (kolejka); pełne zwiedzanie/wykrywanie cykli = DFS (stos). Wybór struktury pomocniczej zmienia to, co algorytm znajduje — piękna puenta całego działu.

⚠️ Uwaga, pułapka

W przeszukiwaniu grafu trzeba oznaczać odwiedzone wierzchołki — inaczej cykl (droga wracająca do startu) zapętli algorytm w nieskończoność (odwiedzasz A → B → A → B…). To rekurencyjny/kolejkowy odpowiednik pętli nieskończonej (3.3, 7.1): graf, w przeciwieństwie do drzewa, może mieć cykle, więc „byłem tu już" jest obowiązkowe. Drzewo (bez cykli) tego problemu nie ma — dlatego przechodzenie drzewa jest prostsze niż grafu. Zapomniany zbiór odwiedzonych to najczęstszy błąd w pierwszych implementacjach BFS/DFS.

🌍 Powiązania

Grafy to prawdopodobnie najczęściej stosowany model w całej informatyce stosowanej: nawigacja (najkrótsza droga), wyszukiwarki (ranking stron liczony z grafu odnośników — słynny PageRank), sieci społecznościowe (rekomendacje znajomych, wykrywanie społeczności), logistyka (trasy dostaw), kompilatory (graf zależności), biologia (sieci białek), a nawet sprawdzanie, czy plan lekcji da się ułożyć (kolorowanie grafu konfliktów). Umiejętność powiedzenia „to jest graf, w którym wierzchołki to…, a krawędzie to…" otwiera drzwi do całego arsenału gotowych rozwiązań — i jest jedną z najbardziej praktycznych rzeczy, jakie wynosisz z tej książki.

🛠️ Teraz Ty

Bez komputera: narysuj jako graf: (a) swoją klasę i kto z kim siedzi w ławce, (b) zależności „co przed czym" przy gotowaniu obiadu (obierz → pokrój → gotuj…). Który jest skierowany? Czy któryś ma cykl (i co by cykl oznaczał)? Wykonaj ręcznie BFS i DFS z wybranego wierzchołka małego grafu (5–6 wierzchołków), zapisując kolejność odwiedzin. Z komputerem: przedstaw graf jako słownik {wierzchołek: [sąsiedzi]} i zaimplementuj BFS (kolejka) znajdujący odległości od startu do wszystkich wierzchołków.

📐 Definicje tej lekcji

• Graf — wierzchołki + krawędzie (skierowane/nieskierowane, ważone/nie); struktura relacji, nie rysunek.
• Drzewo — graf spójny bez cykli; dokładnie jedna droga między parą wierzchołków; nośnik hierarchii.
• BFS / DFS — przeszukiwanie wszerz (kolejka, najkrótsza droga) / w głąb (stos, pełne zwiedzanie, cykle).

📌 Najważniejsze w pigułce

• Graf modeluje niemal wszystko: mapy, sieci, zależności — a problem sprowadzony do grafu dziedziczy gotowe algorytmy (redukcja!).
• Drzewo to graf bez cykli; wszystkie hierarchie i uporządkowane wyszukiwania to drzewa.
• BFS (kolejka) daje kręgi i najkrótsze drogi; DFS (stos/rekurencja) daje głębokie nurkowanie; odwiedzone oznaczaj zawsze.

🎒 Zadania

1. Zamodeluj grafem: plan lekcji, w którym niektóre przedmioty nie mogą być w tej samej sali/godzinie (konflikt). Co jest wierzchołkiem, co krawędzią, i jakie pytanie o graf odpowiada „czy da się ułożyć plan"?

Wskazówka i odpowiedź

Wierzchołki = przedmioty (albo lekcje); krawędź = „te dwa są w konflikcie" (nie mogą naraz). Ułożenie planu to kolorowanie grafu: przypisz każdemu wierzchołkowi „kolor" (godzinę/salę) tak, by połączeni krawędzią mieli różne kolory. „Da się w $k$ godzinach?" = „da się pokolorować $k$ kolorami?". To jeden z klasycznych, trudnych problemów grafowych — a rozpoznanie, że plan lekcji TO jest, natychmiast łączy Twój problem z pół wiekiem badań. Redukcja w akcji.

2. Wykonaj BFS i DFS z wierzchołka A dla grafu: A–B, A–C, B–D, C–D, D–E (nieskierowany). Podaj kolejność odwiedzania dla obu i wyjaśnij różnicę.

Wskazówka i odpowiedź

BFS z A (kolejka): A, potem sąsiedzi B, C, potem ich nieodwiedzeni sąsiedzi D, potem E → A, B, C, D, E (kręgi: odległość 0, 1, 1, 2, 3). DFS z A (stos/rekurencja): A → B → D → C (albo E, zależnie od kolejności) → nurkuje w głąb, cofa przy zaułku → np. A, B, D, C, E albo A, B, D, E, C. BFS trzyma się blisko startu i rośnie kręgami; DFS ucieka daleko i wraca. Zauważ rolę „odwiedzonych": D ma dwóch sąsiadów prowadzących do A (przez B i przez C) — bez oznaczania wpadlibyśmy w pętlę.

3. Sieć „obserwuje" na portalu społecznościowym: A obserwuje B, B obserwuje C, C obserwuje A. Czym różni się ten graf od sieci wzajemnych znajomości i co oznacza cykl A→B→C→A?

Wskazówka i odpowiedź

„Obserwuje" jest skierowane (A→B nie znaczy B→A) — inaczej niż „znajomość", która jest wzajemna (nieskierowana). Cykl A→B→C→A oznacza, że idąc po strzałkach obserwacji, wracasz do startu — tu: zamknięty krąg wzajemnego (pośredniego) śledzenia. W grafie zależności zadań taki cykl byłby katastrofą (zadanie zależne pośrednio od samego siebie — nie da się zacząć!); w sieci społecznej jest niegroźny. Ten sam kształt (cykl skierowany) znaczy co innego zależnie od tego, co modeluje graf — dlatego zawsze pytaj najpierw: co tu jest wierzchołkiem, co krawędzią, i co znaczy droga.

🔍 Sprawdź, czy umiesz

• Zamodelować grafem realną sytuację, nazywając wierzchołki, krawędzie i ich rodzaj.
• Rozpoznać drzewo jako graf bez cykli i podać przykłady hierarchii.
• Wykonać BFS i DFS ręcznie, wskazać ich silniki (kolejka/stos) i różnicę w tym, co znajdują.