Podcast o Graf oraz przeszukiwanie wszerz i w głąb

Kapitoly

Wprowadzenie

Jak reprezentować grafy?

Przeszukiwanie wszerz – BFS

Przeszukiwanie w głąb – DFS

BFS kontra DFS

Najczęstsze pułapki

Podsumowanie

Přepis

Natalia: Wyobraź sobie taką sytuację. Egzamin z informatyki, dostajesz zadanie z grafami i wiesz, że jest jeden błąd, który popełnia 80% studentów. Jeden mały błąd, który kosztuje masę punktów. A co, jeśli powiem ci, jak go unikać już na zawsze?

Szymon: Dokładnie o tym dzisiaj porozmawiamy. Ten jeden haczyk, który odróżnia tych, co zdają, od tych, co zdają na piątkę. To jest prostsze, niż myślisz.

Natalia: Słuchacie Studyfi Podcast. Ja jestem Natalia, a ze mną ekspert, Szymon. No dobrze, Szymon, zacznijmy od totalnych podstaw. Czym w ogóle jest graf?

Szymon: Dobre pytanie! To nie jest wykres z Excela. W informatyce graf to zbiór wierzchołków — czyli kropek — i krawędzi, które je łączą. Pomyśl o mapie miast. Miasta to wierzchołki, a drogi między nimi to krawędzie.

Natalia: Proste. Czyli sieci społecznościowe to też graf? Ja i ty jesteśmy wierzchołkami, a nasza znajomość to krawędź?

Szymon: Dokładnie tak! I te krawędzie mogą mieć kierunek. Jeśli ja mogę do ciebie napisać, a ty do mnie nie, to jest to graf skierowany. A jeśli znajomość działa w obie strony, to graf jest nieskierowany.

Natalia: Rozumiem. A co z tymi grafami ważonymi? Brzmi skomplikowanie.

Szymon: Nic bardziej mylnego. Krawędź ważona ma po prostu przypisaną liczbę, czyli wagę. Na naszej mapie miast wagą może być odległość w kilometrach. W grafie nieważonym wszystkie drogi są równe.

Natalia: Okej, czyli mamy te kropki i linie. Ale jak komputer ma to zrozumieć? Jak to zapisać w kodzie?

Szymon: Są dwa główne sposoby. Pierwszy to macierz sąsiedztwa. To taka duża tabela, gdzie zapisujemy jedynkę, jeśli między dwoma wierzchołkami jest krawędź, i zero, jeśli jej nie ma.

Natalia: Brzmi logicznie. Jakieś wady?

Szymon: Ogromne. Jeśli masz tysiąc miast, ale tylko kilka dróg, to większość tej tabeli będzie wypełniona zerami. To straszne marnotrawstwo pamięci. Dobre tylko dla gęstych grafów, gdzie prawie każdy jest połączony z każdym.

Natalia: A druga opcja? Ta lepsza?

Szymon: Zdecydowanie częściej używana — lista sąsiedztwa. Dla każdego wierzchołka tworzymy po prostu listę jego sąsiadów. To o wiele bardziej oszczędne dla grafów z małą liczbą krawędzi, czyli tak zwanych grafów rzadkich.

Natalia: Czyli dla sieci znajomych, gdzie nikt nie zna wszystkich, lista sąsiedztwa jest idealna. A dla macierzy... może dla małej, zamkniętej grupy, gdzie każdy zna każdego?

Szymon: Dokładnie. Wybór reprezentacji to kluczowa decyzja, która wpływa na wydajność algorytmów. Zapamiętajcie: macierz dla gęstych grafów, lista dla rzadkich.

Natalia: Dobra, mamy nasz graf w pamięci. Teraz chcemy go przeszukać, czyli odwiedzić wszystkie wierzchołki. Słyszałam o dwóch głównych metodach: BFS i DFS. Zacznijmy od BFS.

Szymon: Jasne. BFS, czyli Breadth-First Search, to przeszukiwanie wszerz. Wyobraź sobie, że wrzucasz kamień do wody. Fala rozchodzi się równomiernie we wszystkich kierunkach, warstwa po warstwie. Tak właśnie działa BFS.

Natalia: Czyli zaczynam od jednego wierzchołka, odwiedzam wszystkich jego bezpośrednich sąsiadów, potem sąsiadów tych sąsiadów i tak dalej?

Szymon: Precyzyjnie. BFS używa do tego specjalnej struktury danych, która nazywa się kolejką. Działa na zasadzie "kto pierwszy przyjdzie, ten pierwszy wychodzi". Jak kolejka w sklepie.

Natalia: Okej, czyli dodaję wierzchołek startowy do kolejki. Potem go wyciągam, sprawdzam jego sąsiadów, dodaję ich na koniec kolejki i oznaczam jako odwiedzonych. I tak w kółko, aż kolejka będzie pusta?

Szymon: Dokładnie! I tu jest najważniejsza właściwość BFS: zawsze znajduje najkrótszą ścieżkę w grafie nieważonym. Najkrótszą, czyli taką z najmniejszą liczbą krawędzi.

Natalia: To jest super przydatne! Czyli jeśli szukam najszybszego połączenia metrem, gdzie każdy przystanek to jedna krawędź, to BFS da mi odpowiedź?

Szymon: Tak! Ponieważ eksploruje graf warstwami, to gdy po raz pierwszy dociera do celu, mamy gwarancję, że to najkrótsza możliwa droga pod względem liczby przystanków.

Natalia: Zobaczmy na przykładzie. Graf A-B, A-C, B-D. Startujemy z A. Do kolejki wrzucamy A.

Szymon: Dobrze. Wyciągamy A. Jego sąsiedzi to B i C. Wrzucamy B i C do kolejki. Kolejka teraz to .

Natalia: Teraz wyciągamy B. Jego sąsiad to D. Wrzucamy D do kolejki. Kolejka to .

Szymon: I tak dalej. Kolejność odwiedzin będzie: A, potem B i C, a na końcu D. Warstwami.

Natalia: Okej, BFS jest jak fala. Systematyczny i szeroki. Czym w takim razie jest DFS, czyli Depth-First Search?

Szymon: DFS to zupełnie inna filozofia. To przeszukiwanie w głąb. Wyobraź sobie, że jesteś w labiryncie. Idziesz jedną ścieżką tak daleko, jak się da. Jak trafisz w ślepy zaułek, cofasz się do ostatniego rozwidlenia i próbujesz innej drogi.

Natalia: Czyli to taki uparty odkrywca? Zamiast rozglądać się na boki, pędzi przed siebie?

Szymon: Dokładnie! DFS nie używa kolejki, tylko stosu. Stos działa na zasadzie "kto ostatni wejdzie, ten pierwszy wychodzi". Jak stos talerzy — zdejmujesz ten z samej góry.

Natalia: To kompletnie zmienia kolejność odwiedzin! W naszym grafie A-B, A-C, B-D, startując z A, co zrobi DFS?

Szymon: Startujemy z A. Na stos wrzucamy A. Zdejmujemy A, oznaczamy jako odwiedzone. Jego sąsiedzi to B i C. Wrzucamy ich na stos, powiedzmy C, potem B. Stos to .

Natalia: Zdejmujemy B. Jego sąsiad to D. Wrzucamy D na stos. Stos to .

Szymon: Teraz zdejmujemy D. Nie ma już nowych sąsiadów. Zdejmujemy C. Też koniec. Kolejność odwiedzin to A, B, D, a dopiero potem wracamy i sprawdzamy C. Widzisz różnicę? DFS poszedł w głąb ścieżki A-B-D.

Natalia: Wow, zupełnie inna trasa. Do czego w takim razie przydaje się DFS, skoro nie znajduje najkrótszej ścieżki?

Szymon: O, ma mnóstwo zastosowań! Jest świetny do wykrywania cykli w grafie, czyli czy da się wrócić do punktu wyjścia inną drogą. Używa się go też do rozwiązywania labiryntów czy w sortowaniu topologicznym, które jest kluczowe np. przy zarządzaniu zależnościami w projektach.

Natalia: Dobrze, podsumujmy te różnice, bo to chyba klucz do zrozumienia obu algorytmów.

Szymon: Jasne. Po pierwsze, struktura danych. BFS to kolejka, zasada FIFO - First In, First Out. DFS to stos, zasada LIFO - Last In, First Out.

Natalia: Po drugie, sposób przeszukiwania. BFS idzie wszerz, warstwa po warstwie. Jest płytki i szeroki. DFS idzie w głąb, jedną ścieżką do końca. Jest wąski i głęboki.

Szymon: Dokładnie. I to prowadzi do najważniejszej różnicy w zastosowaniach. Chcesz najkrótszą ścieżkę w grafie bez wag? Tylko BFS. Chcesz sprawdzić, czy w grafie jest cykl, albo rozwiązać labirynt? DFS będzie twoim przyjacielem.

Natalia: A złożoność? Czy któryś jest szybszy?

Szymon: Tutaj niespodzianka — oba mają taką samą złożoność czasową! Dla grafu reprezentowanego przez listę sąsiedztwa, oba działają w czasie O(V + E), gdzie V to liczba wierzchołków, a E to liczba krawędzi.

Natalia: Czyli w praktyce są równie szybkie, ale dają zupełnie inne wyniki i służą do czego innego. Wybór zależy od problemu, który chcemy rozwiązać.

Szymon: To jest sedno sprawy. Nie ma "lepszego" algorytmu. Jest tylko "lepiej dopasowany" do konkretnego zadania.

Natalia: Wróćmy do tego, od czego zaczęliśmy. Ten błąd, który popełnia 80% studentów. Co to jest?

Szymon: To aż boli, jak często to widzę. To zapominanie o oznaczaniu wierzchołków jako odwiedzonych. A dokładniej, oznaczanie ich w złym momencie.

Natalia: Jak to w złym momencie? Myślałam, że po prostu trzeba oznaczyć i już.

Szymon: W BFS wierzchołek powinno się oznaczać jako odwiedzony w momencie dodawania go do kolejki, a nie dopiero po wyjęciu go z niej. Jeśli zrobisz to za późno, a graf ma cykle, to ten sam wierzchołek może trafić do kolejki wiele razy. Algorytm wpadnie w pętlę albo będzie działał bardzo nieefektywnie.

Natalia: Aaa, czyli jeśli wierzchołek A jest połączony z B, a B z A, to bez oznaczania od razu, będą się dodawać do kolejki w nieskończoność?

Szymon: Dokładnie tak! To prowadzi do nieskończonej pętli i zwiechy programu. Prosty błąd, a konsekwencje fatalne. To jest właśnie ta pułapka.

Natalia: Jakaś inna częsta pomyłka?

Szymon: Tak, używanie BFS do szukania najkrótszej ścieżki w grafie z wagami. Pamiętajcie, BFS liczy tylko liczbę krawędzi. Jeśli jedna droga ma 5 przystanków i zajmuje 10 minut, a druga ma 2 przystanki i zajmuje godzinę, BFS wybierze tę drugą! Do grafów ważonych potrzebujemy innych algorytmów, jak algorytm Dijkstry.

Natalia: Czyli nie można bezmyślnie stosować jednego narzędzia do wszystkiego. Trzeba zrozumieć, jak działa i jakie ma ograniczenia.

Szymon: Właśnie. I trzeci błąd: pomylenie struktur danych. Użycie stosu do BFS albo kolejki do DFS. To tak jakbyś próbował wkręcić śrubę młotkiem. Może się uda, ale efekt będzie... ciekawy.

Natalia: Dobra, to było naprawdę dużo wiedzy, ale świetnie to wyjaśniłeś. Spróbujmy zebrać najważniejsze punkty dla naszych słuchaczy.

Szymon: Po pierwsze, grafy to wierzchołki i krawędzie. Możemy je reprezentować macierzą lub, co częstsze i lepsze dla rzadkich grafów, listą sąsiedztwa.

Natalia: Po drugie, mamy dwa główne algorytmy przeszukiwania. BFS, czyli przeszukiwanie wszerz, używa kolejki, rozchodzi się jak fala i jest idealny do znajdowania najkrótszej ścieżki w grafach nieważonych.

Szymon: A DFS, czyli przeszukiwanie w głąb, używa stosu, eksploruje jedną ścieżkę do samego końca i świetnie nadaje się do wykrywania cykli czy rozwiązywania labiryntów.

Natalia: I najważniejsze, ten kluczowy błąd do uniknięcia: zawsze oznaczaj wierzchołki jako odwiedzone, najlepiej od razu przy dodawaniu ich do kolejki lub stosu, żeby nie wpaść w nieskończoną pętlę. I nie używaj BFS do grafów z wagami!

Szymon: Jeśli to zapamiętacie, te 80% was nie dotyczy. Jesteście w tych 20%, które naprawdę rozumieją, co robią. To jest ta przewaga na egzaminie.

Natalia: Dokładnie tak. Dzięki wielkie, Szymon, za tę dawkę wiedzy!

Szymon: Cała przyjemność po mojej stronie. Do usłyszenia!

Natalia: A wy słuchaliście Studyfi Podcast. Powodzenia na egzaminach i do następnego razu!