Podcast na Graf a prohledávání do šířky a do hloubky

Kapitoly

Neviditelná síť kolem nás

Jak se v grafu neztratit

Matice versus Seznam

Úvod a princip BFS

Jak funguje algoritmus

Příklad v praxi

Složitost a využití

Hlouběji, ne šířeji

Kouzlo zásobníku

Příklad z praxe

K čemu je to dobré?

Rekurzivní DFS pod lupou

BFS versus DFS

Hledání nejkratší cesty

Časté chyby a omyly

Závěrečné shrnutí a tipy

Přepis

Tomáš: Pokaždé, když otevřeš Instagram a podíváš se, kdo koho sleduje, koukáš se na obrovský, neviditelný graf. Každý profil je bod a každé to 'sledovat' je čára, která vás spojuje. A právě to, jak tohle všechno funguje, je tématem dnešní epizody. Posloucháte Studyfi Podcast.

Barbora: Přesně tak, Tomáši! Ahoj všem. Grafy jsou všude kolem nás, i když je nevidíme. Formálně je graf prostě dvojice — množina vrcholů, což jsou ty profily, a množina hran, tedy těch propojení.

Tomáš: Dobře, takže vrcholy jsou objekty a hrany vztahy mezi nimi. Ale vztah jako přátelství na Facebooku je jiný než třeba jednosměrná ulice, ne?

Barbora: Přesně. Proto rozlišujeme neorientované hrany, jako je to přátelství – je obousměrné. A pak orientované, jako ta jednosměrka nebo když na Instagramu ty někoho sleduješ, ale on tebe nemusí. To je šipka jen jedním směrem.

Tomáš: A co když chci autem z Prahy do Brna? Tam mě zajímá vzdálenost. To je taky hrana?

Barbora: Ano! To je takzvaná vážená hrana. Každé takové hraně přiřadíme číslo – váhu. Může to být vzdálenost, čas, nebo třeba cena letenky. Je to super užitečné.

Tomáš: Fajn, teď si to představuju jako mapu. Ale jak tohle pochopí počítač? Jak mu tu mapu popíšu?

Barbora: Skvělá otázka. Máme na to hlavně dva způsoby. První je matice sousednosti. Představ si tabulku, kde řádky i sloupce jsou všechny vrcholy tvého grafu. Když mezi vrcholem A a B vede hrana, napíšeš do buňky 1. Když ne, dáš 0.

Tomáš: To zní jednoduše. Ale co když mám miliony uživatelů jako na tom Instagramu? To by byla gigantická tabulka plná nul, ne?

Barbora: Přesně! Pro takové řídké grafy, kde je málo spojení, je matice plýtvání pamětí. Proto máme druhou, chytřejší metodu: seznam sousednosti.

Tomáš: A to je co?

Barbora: Jednoduše si pro každý vrchol uděláš seznam jeho přímých sousedů. Takže u tvého profilu bude jen seznam lidí, které sleduješ. Nic víc. Je to mnohem úspornější a pro většinu úkolů, jako je hledání cesty v GPS, i rychlejší.

Tomáš: Takže po tom, co jsme se ponořili do hloubky s DFS, je na čase se podívat na jeho sourozence, ne?

Barbora: Přesně tak! Teď se podíváme na prohledávání do šířky, známé jako BFS, neboli Breadth-First Search. Je to úplně jiný přístup.

Tomáš: Jak jiný? Místo co nejhlouběji jdeme... co nejšířeji?

Barbora: Přesně! Představ si, že hodíš kámen do rybníka. BFS prozkoumává graf přesně jako ty vlny, co se šíří. Nejdřív prozkoumá všechny přímé sousedy, pak sousedy těch sousedů, a tak dále, vrstvu po vrstvě.

Tomáš: To zní logicky. Jak to ale technicky zařídí? Jak si pamatuje, kdo je na řadě?

Barbora: K tomu používá datovou strukturu zvanou fronta, neboli queue. Funguje na principu FIFO – First-In, First-Out.

Tomáš: Takže jako fronta na oběd? Kdo si stoupne první, ten dostane jídlo první.

Barbora: Naprosto přesně! Vrcholy zpracováváme přesně v tom pořadí, v jakém jsme je objevili.

Tomáš: Dobře, takže mám frontu. Jak s ní ten algoritmus pracuje krok za krokem?

Barbora: Je to velmi systematické. Na začátku si všechny vrcholy označíme jako nenavštívené. Pak si vybereme startovní vrchol, třeba s.

Tomáš: A ten jde rovnou do fronty?

Barbora: Ano. Označíme ho jako navštívený, jeho vzdálenost nastavíme na nulu a šup s ním do fronty. A pak začíná smyčka.

Tomáš: Dokud není fronta prázdná, předpokládám.

Barbora: Správně. Vyjmeš první vrchol z fronty, řekněme u, a podíváš se na všechny jeho sousedy. Pro každého souseda, kterého jsi ještě nenavštívil, uděláš tři věci.

Tomáš: Dobře, poslouchám... co to je?

Barbora: Označíš ho jako navštívený. Nastavíš mu vzdálenost jako vzdálenost u plus jedna. A přidáš ho na konec fronty. Tím zajistíš to prohledávání po vrstvách.

Tomáš: Pojďme si to ukázat na příkladu. Řekněme, že máme graf A až G a startujeme v A. Takže... A jde do fronty.

Barbora: Perfektní. Vyjmeme A. Jeho sousedi jsou B a C. Oba jsou nenavštívení.

Tomáš: Takže navštívíme B, jeho vzdálenost je 1, a dáme ho do fronty. Pak navštívíme C, vzdálenost taky 1, a taky ho dáme do fronty. Fronta je teď .

Barbora: Přesně tak. Teď je na řadě B. Vyjmeme B z fronty. Jeho soused je D. A už jsme navštívili.

Tomáš: Takže navštívíme D, jeho vzdálenost bude 2, protože jdeme z B, které mělo 1. A přidáme D do fronty. Fronta je .

Barbora: Vidíš, jak to jde? Teď vyjmeme C. Jeho soused je E. Navštívíme E, vzdálenost 2, a přidáme ho do fronty. Ta je teď .

Tomáš: A takhle pokračujeme, dokud fronta není prázdná. Chápu. Každý vrchol se do fronty dostane jen jednou.

Barbora: Přesně. A protože každý vrchol do fronty jednou vložíme a jednou vyjmeme a projdeme všechny jeho hrany, je časová složitost krásně efektivní: O(V + E).

Tomáš: Kde V je počet vrcholů a E počet hran. To je optimální, protože se na všechno musíme podívat alespoň jednou.

Barbora: Přesně tak. A to nejlepší na BFS je, že nám přirozeně najde nejkratší cestu v neváženém grafu. Právě díky tomu prohledávání po vrstvách.

Tomáš: Aha! Takže je to ideální pro věci jako hledání nejkratšího spojení na sociální síti nebo nejkratší trasy v mapách, kde každá ulice má stejnou „cenu“.

Barbora: Ano! Nebo pro web crawlery, které procházejí webové stránky odkaz po odkazu. Také s ním můžeme testovat, jestli je graf souvislý.

Tomáš: Super, takže BFS je skvělé pro nevážené grafy. Ale co když cesty mají různou délku nebo cenu? Třeba když hledám nejen nejkratší, ale i nejrychlejší cestu autem?

Tomáš: Takže minule jsme probrali BFS, které prozkoumává graf hezky po vrstvách, jako když se šíří vlny po vodě. Ale co když chci jít spíš... na průzkum do neznáma?

Barbora: Skvělá otázka! A přesně pro to máme druhý přístup. Jmenuje se Prohledávání do hloubky, neboli DFS – Depth-First Search.

Tomáš: Prohledávání do hloubky. To zní dobrodružně. Takže místo toho, abychom se rozhlíželi kolem sebe, jdeme rovnou za nosem?

Barbora: Přesně tak! Představ si, že jsi v bludišti. S DFS si vybereš jednu cestu a jdeš po ní tak dlouho, dokud nenarazíš na slepou uličku nebo na konec.

Tomáš: A teprve pak se vrátím a zkusím jinou cestu?

Barbora: Přesně. Vrátíš se k poslední křižovatce a zkusíš další neprozkoumanou chodbu. Jdeš do hloubky, ne do šířky.

Tomáš: Dobře, to dává smysl. Ale jak si algoritmus pamatuje, kam se má vrátit? BFS mělo tu svou frontu...

Barbora: Správně! A DFS má zase svého nejlepšího kamaráda, a tím je **zásobník**, anglicky Stack.

Tomáš: Zásobník... jako na talíře?

Barbora: Ano, to je perfektní přirovnání! Funguje na principu LIFO – Last-In, First-Out. Poslední talíř, který na hromadu položíš, si vezmeš jako první.

Tomáš: Takže vrchol, který jsem objevil naposledy, prozkoumám jako první?

Barbora: Přesně. Místo abychom objevovali sousedy a řadili je na konec fronty, tak nově objeveného souseda prostě položíme nahoru na zásobník a hned se mu věnujeme. Tím se zanořujeme hlouběji a hlouběji do grafu.

Tomáš: Dobře, zkusme si to na našem starém známém grafu s vrcholy A, B, C a tak dále. Začneme zase v A.

Barbora: Jasně. Takže: začneme v A. Dáme A na zásobník a označíme ho jako navštívený. Hned ho zase vyndáme a podíváme se na jeho sousedy, B a C. Řekněme, že jako první narazíme na B.

Tomáš: A protože B je nový objev, jde na vrchol zásobníku a hned se na něj vrhneme. Na C zatím kašleme.

Barbora: Přesně tak, C musí počkat. Takže vezmeme B ze zásobníku, podíváme se na jeho sousedy... a tam je D. Takže hop s D na zásobník a jdeme ho prozkoumat.

Tomáš: Chápu! Takže trasa bude A, pak B, pak D... a pak D má souseda F, takže jdeme na F. Co když F už dál nevede?

Barbora: Výborně! Když F nemá žádné nenavštívené sousedy, ocitli jsme se ve slepé uličce. Algoritmus se tedy 'vrátí' – v podstatě se podívá zpátky na zásobník, co tam zbylo, a pokračuje odtamtud.

Tomáš: Takže je to trochu jako ten kamarád, co musí dovyprávět jeden příběh až do konce, než vůbec začne poslouchat ostatní.

Barbora: Jo, tak nějak. Je velmi soustředěný. Mimochodem, časová složitost je stejná jako u BFS, tedy O(V + E), protože i tady se podíváme na každý vrchol a každou hranu jen jednou.

Tomáš: Dobře, takže je to jiný způsob procházení. Ale k čemu je tenhle 'hloubkový' přístup v reálu dobrý?

Barbora: Oh, má spoustu skvělých využití! Protože jde až na konec cesty, je geniální pro řešení bludišť nebo hledání cesty ven.

Tomáš: To dává smysl. Najde nějakou cestu, i když nemusí být nejkratší.

Barbora: Přesně. Dále je skvělý na hledání cyklů v grafu. Snadno zjistí, jestli ses při tom zkoumání nezamotal do kruhu. A taky se používá pro takzvané topologické řazení.

Tomáš: Topo... cože?

Barbora: Zní to složitě, ale představ si to jako plánování. Máš úkoly, kde některé musíš udělat před jinými. Třeba si nejdřív musíš zapsat předmět, než můžeš jít na zkoušku. DFS ti pomůže seřadit ty úkoly do správného pořadí.

Tomáš: Aha! Takže je to vlastně docela praktické. Nejen na bloudění v bludištích.

Barbora: Rozhodně. A od toho se můžeme posunout k dalšímu zajímavému problému, a to je hledání nejkratší cesty, kde nám tyhle základní algoritmy už stačit nebudou.

Tomáš: Páni, to bylo hodně informací. Ale dává to smysl. A myslím, že nás to skvěle připravilo na naše poslední velké téma pro dnešek, že?

Barbora: Přesně tak. Po všem tom povídání o datových strukturách se konečně podíváme na dva naprosto zásadní algoritmy pro prohledávání grafů: BFS a DFS.

Tomáš: Super. Už jsme je zmínili. Začneme s DFS, prohledáváním do hloubky? Slyšel jsem, že jeho rekurzivní verze může být trochu... matoucí.

Barbora: Může, ale když si to projdeme krok za krokem, uvidíš, že je to vlastně elegantní. Představ si, že začínáme na vrcholu A. Označíme ho jako navštívený.

Tomáš: Dobře, jsme v A. Co dál?

Barbora: Podíváme se na jeho sousedy, řekněme B a C. Abecedně první je B, takže rekurzivně zavoláme DFS na B. Teď jsme v B, označíme ho a podíváme se na jeho sousedy: A a D.

Tomáš: A je už navštívené, takže to ignorujeme a jdeme na D?

Barbora: Přesně! Zavoláme DFS na D. Tam zjistíme, že jeho soused B je navštívený, takže pokračujeme k F. Z F se už nemáme kam dál zanořit, protože jeho jediný soused D je navštívený.

Tomáš: Takže co teď? Narazili jsme na slepou uličku.

Barbora: Teď se začne kouzlo rekurze projevovat. Funkce se začnou vracet. Vrátíme se z F do D, z D do B a z B zpátky do A. Tím jsme prozkoumali celou tuhle větev.

Tomáš: Aha! A protože jsme v A měli ještě jednoho neprozkoumaného souseda, C, tak algoritmus pokračuje tam?

Barbora: Bingo! Teď zavoláme DFS na C, z něj na E a z něj na G. Pak se zase postupně vrátíme zpět až do A. A je hotovo.

Tomáš: Takže finální pořadí navštívených vrcholů by bylo... A, B, D, F, a pak C, E, G. Chápu. Ta rekurze je vlastně jako sledování jedné cesty až na její konec a pak postupné vracení se.

Barbora: Přesně tak! A to nás přivádí k zásadnímu rozdílu mezi DFS a BFS, prohledáváním do šířky.

Tomáš: Dobře, jaký je tedy ten hlavní rozdíl v principu?

Barbora: Představ si to takhle: DFS je jako prozkoumávání jeskyně tak, že jdeš jednou chodbou co nejdál, a teprve když narazíš na konec, vrátíš se a zkusíš jinou. BFS je spíš jako bys stál u vchodu a nejdřív se podíval do všech chodeb, které jsou hned u tebe, pak do všech, které jsou o krok dál, a tak dále, po vrstvách.

Tomáš: To je dobrá analogie. A technicky to souvisí s těmi datovými strukturami, že? Fronta a zásobník.

Barbora: Ano. BFS používá frontu – FIFO, neboli „první dovnitř, první ven“. To zajišťuje to prohledávání po vrstvách. DFS, pokud není rekurzivní, používá zásobník – LIFO, „poslední dovnitř, první ven“. Proto se vždy zanoří co nejhlouběji.

Tomáš: Takže BFS je jako spořádaná fronta na oběd, zatímco DFS je spíš jako hromada palačinek, kde vždycky bereš tu nejvrchnější.

Barbora: To je naprosto dokonalé přirovnání! A přesně kvůli těmto rozdílům se hodí na úplně jiné typy úloh.

Tomáš: Zmínila jsi úlohy. V tabulce máme, že BFS umí najít nejkratší cestu, ale DFS ne. Jak je to možné?

Barbora: Je to právě díky tomu prohledávání po vrstvách. Protože BFS nejdřív navštíví všechny sousedy ve vzdálenosti 1, pak všechny ve vzdálenosti 2 a tak dále, je zaručeno, že když poprvé narazí na nějaký cíl, je to tou nejkratší možnou cestou.

Tomáš: Nejkratší ve smyslu počtu hran, ne nějaké váhy, že?

Barbora: Přesně. Mluvíme o nevážených grafech. U DFS nic takového neplatí. DFS se může zanořit do nějaké extrémně dlouhé, klikaté cesty, i když k cíli existuje zkratka hned vedle startu.

Tomáš: Takže pro hledání nejkratší cesty v bludišti je BFS jasná volba.

Barbora: Jednoznačně. Během toho si navíc můžeš ukládat předchůdce každého vrcholu a pak si tu cestu zpětně zrekonstruovat od cíle k startu.

Tomáš: Dobře, to zní celkem jasně. Ale kde studenti nejčastěji chybují, když se s tímhle setkají poprvé?

Barbora: Ach, klasika. Číslo jedna je záměna fronty a zásobníku. Použiješ špatnou strukturu a algoritmus se chová úplně jinak.

Tomáš: To si dokážu představit. Co dál?

Barbora: Další velký problém je zapomenout si označovat navštívené vrcholy. Pokud má graf cykly, algoritmus se v nich může zacyklit a běžet donekonečna. Doslova chodí v kruhu.

Tomáš: To by asi neprošlo. A co ten předpoklad o nejkratší cestě u DFS?

Barbora: Ano, to je třetí častý omyl. Studenti se naučí o hledání cesty a pak se snaží použít DFS. Ne, DFS nenajde nejkratší cestu. Pro to je tu BFS. A ani jeden z nich mimochodem nefunguje správně pro vážené grafy – na to máme třeba Dijkstrův algoritmus.

Tomáš: Takže když to shrnu, oba algoritmy mají své místo. BFS je skvělé na nejkratší cesty v nevážených grafech, DFS zase na jiné věci jako detekce cyklů.

Barbora: Přesně tak. A můj největší tip pro všechny, kteří s tím bojují: najděte si na internetu interaktivní vizualizaci. Není nic lepšího, než když si můžete algoritmus sami odkrokovat, sledovat, jak se plní fronta nebo zásobník, a zkoušet různé grafy.

Tomáš: To je skvělá rada. Vidět to v akci je k nezaplacení. Barboro, mockrát ti děkuju. Nejen za tohle téma, ale za celou dnešní epizodu. Probrali jsme toho opravdu hodně.

Barbora: Já děkuju za pozvání, Tomáši. Byla to radost. Doufám, že to našim posluchačům pomůže.

Tomáš: O tom nepochybuji. Takže to je pro dnešek od nás vše. Děkujeme, že jste poslouchali Studyfi Podcast. Učte se chytře, ne tvrdě, a uslyšíme se příště.