Teoria Grafów (Matura z Informatyki)

Ostatnie lata to mocny skręt Matury Rozszerzonej z Informatyki w stronę tzw. Grafów. Choć sama nazwa brzmi akademicko, to w rzeczywistości nic innego jak... siatka połączonych miast z drogami.

W grafie "Miasto" to Wierzchołek (Node/Vertex), a ulica między nimi to Krawędź (Edge). Jeśli ulica jest jednokierunkowa, mamy do czynienia z Grafem Skierowanym. Jeśli ulica ma ograniczoną prędkość czy odległość (np. 15km), mówimy o Grafie Ważonym (bardzo popularne w poszukiwaniu najkrótszej drogi GPS).

1. Jak komputer pamięta miasta? (Macierz Sąsiedztwa)

My jako ludzie patrzymy na rysunek z kółkami i kreskami. Ale w C++ czy Pythonie wprowadzamy graf w postaci Excelowej tabeli (Tablica 2D)! To tzw. Macierz Sąsiedztwa.

Tabela ma tyle rzędów i kolumn, ile jest wierzchołków.

Wpisujemy 1 (lub wartość odległości), jeśli z węzła X da się przejechać do Y bezpośrednią krawędzią.
Wpisujemy 0, jeśli takiej ulicy nie ma.

Na maturze często musisz przetłumaczyć listę krawędzi (np. linijka w pliku: 1-3) na wpis do swojej tabeli tablica[1][3] = 1;.

2. Przeszukiwanie W Głąb (DFS - Depth-First Search)

Wyobraź sobie, że stoisz w gigantycznym labiryncie żywopłotowym. DFS to zasada: "Zawsze trzymaj się prawej ściany i idź tak głęboko, aż wpadniesz w ślepy zaułek. Gdy tam wpadniesz, wycofaj się tylko o jeden krok i spróbuj innej drogi".

W informatyce DFS realizuje się wprost za pomocą Rekurencji! (Widzisz, wszystko się łączy).

Komputer staje na węźle A. Zaznacza go jako "Odwiedzony".
Patrzy, czy jest droga do B. Jest! Odpala dla niego nową funkcję: dfs(B).
Wchodzi do węzła B (zamrażając punkt A!). Sprawdza drogi z B. Idzie do C.
Gdy węzeł nie ma już dróg, funkcja się kończy (warunek brzegowy), a sterowanie wraca do wywołania o poziom wyżej. DFS świetnie sprawdza się w szukaniu ścieżki w labiryntach czy rysowaniu tzw. spójnych składowych (czy w ogóle całe państwo ma połączenie drogowe do każdego miasta).

3. Przeszukiwanie Wszerz (BFS - Breadth-First Search) 🪤

Ten algorytm działa na innej zasadzie: fali uderzeniowej. Stoisz na węźle startowym i sprawdzasz w pierwszym kroku ABSOLUTNIE WSZYSTKICH swoich bezpośrednich, najbliższych sąsiadów naraz (Fala nr 1). Potem przesuwasz się na nich, i z nich znów sprawdzasz wszystkich pobliskich.

Do zbudowania BFS nie używasz rekurencji, a specjalnej struktury zwanej Kolejką (Queue) – działa jak kolejka do kasy w sklepie (Kto wchodzi pierwszy, wychodzi pierwszy - FIFO).

Cel nr 1 na egzaminie: BFS zawsze jako pierwszy odnajduje najkrótszą drogę w grafie bez wag (takim, gdzie każda krawędź "kosztuje" tyle samo). Gdy uczeń widzi pytanie: "Oblicz w ilu najmniej krokach skoczek dojdzie na to pole szachownicy" - z automatu odpala algorytm BFS z Kolejką.