Spousta počítačových úloh se dá popsat tak, že si představíme nějaký graf a projdeme postupně jeho vrcholy. Možná bychom stejně dobrý program napsali i beztak, ale většinou takhle budeme mít přehlednější kód a třeba nás napadne i nějaký zlepšovák, který by se jinak skryl v balastu.

Procházení stromu

Dostaneme graf, který má tvar stromu: jeden vrchol je kořen, a z něj se větví celý zbytek grafu. Máme za úkol projít všechny vrcholy jeden po druhém a případně v každém z nich něco spočítat. Nebudeme plýtvat časem, takže to celé bude trvat O(m), kde m je počet hran ve stromu – každou projdeme jednou dolů a jednou nahoru. Podle toho, jaké pořadí zvolíme, může takhle jednoduchá úloha řešit spoustu reálných problémů.

Pro názornost si představíme kořen namalovaný v grafu nahoře, jako bychom kreslili rodokmen. Přesněji, kreslíme z rodokmenu jenom muže, protože slovo „vrchol“ je rodu mužského. Každý vrchol kromě kořene má jednoho rodiče, a dále libovolný počet sourozenců a synů. Vrcholy, které nemají žádné syny, označujeme trochu zvráceně jako listy.

Průchod do hloubky

Jakmile navštívíme některý vrchol, pustíme se do procházení jeho synů. Teprve až se vrátíme z posledního syna (což zároveň znamená, že jsme prošli všechny potomky), vrátíme se z vrcholu zpátky nahoru a zkusíme prozkoumat sourozence vpravo od něj. Tenhle slovní popis se dá přímo napsat do počítače, když použijeme rekurzi (vyzkoušejte sami): řešení. function projdi(vrchol) { navstiv(vrchol); for (syn of vrchol.synove) { projdi(syn); } } projdi(koren);

Z různých důvodů může být užitečné se vyhnout rekurzi. V tom případě si zavedeme pole, které bude neustále obsahovat cestu z kořene do právě navštěvovaného vrcholu. U každého vrcholu v tomhle poli si navíc potřebujeme pamatovat číslo, kolik jeho synů už jsme navštívili.

Krok ve stromu směrem k některému synovi je jasný, prostě syna přidáme s číslem nula na konec cesty. U jeho rodiče si ale zároveň musíme přičíst jedničku, protože jednoho syna právě navštěvujeme. Cestou nahoru pak už stačí jen vymazat z cesty poslední vrchol.

Program už není o moc složitější: na začátku do cesty napíšeme kořen, s počtem navštívených synů nastaveným na nulu. Vždycky pracujeme s vrcholem na konci cesty. Pokud má nějakého nenavštíveného syna, navštívíme ho a přidáme do cesty, jinak se vrátíme k rodičům. Tenhle jediný krok se opakuje pořád dokola, až nakonec z cesty vyhodíme kořen a program skončí. Zkuste naprogramovat: řešení. koren.pocet_navstivenych = 0; navstiv(koren); var cesta = [koren]; while (cesta.length > 0) { var posledni = cesta[cesta.length - 1]; if (posledni.pocet_navstivenych < posledni.synove.length) { var syn = posledni.synove[posledni.pocet_navstivenych]; navstiv(syn); posledni.pocet_navstivenych += 1; syn.pocet_navstivenych = 0; cesta.push(syn); } else { cesta.pop() } }

Průchod do šířky

Nejdřív navštívíme všechny syny kořene, potom jejich syny a tak dál, generaci za generací. Program skončí ve chvíli, kdy žádný vrchol v právě navštívené generaci už nemá syny.

Pro jednoduchost se bude hodit mít dvě pole: v jednom si uložíme současnou generaci, do druhého budeme skládat její syny. Průchod jednou generací tedy znamená, navštívit postupně všechny vrcholy v prvním poli a všechny syny přitom vložit na konec druhého pole. Potom první pole zahodíme a vyrobíme si místo něj nové prázdné pole na další generaci. Zkuste to naprogramovat: řešení. var soucasna = [koren]; while (soucasna.length > 0) { var pristi = []; for (vrchol of soucasna) { navstiv(vrchol); for (syn of vrchol.synove) { pristi.push(syn); } } soucasna = pristi; }

Všimněte si, že cestu z kořene do vrcholu v tomhle případě není kde vyčíst. Navíc utrácíme spoustu paměti, protože si opravdu musíme pamatovat jednu celou generaci. Obojí je to daň za to, že budeme vrcholy navštěvovat v poněkud přehlednějším pořadí.

Procházení grafu

Tentokrát už nedostaneme strom, ale obecně jakýkoliv graf, spousta vrcholů nějak pospojovaných hranami. Přirozeně se může stát, že některé vrcholy při průchodu nenavštívíme, protože se do nich prostě nejde z kořene dostat. To je v pořádku. Musíme ale dát pozor, abychom každý vrchol navštívili jen jednou – algoritmy popsané výše by se snadno mohly zaseknout v kruhu.

Které vrcholy jsme navštívili a které ne, si prostě musíme u každého z nich pamatovat. Abychom se v tom zbytečně nemotali, pojďme si představit, že funkce navstiv(vrchol) se o tuhle paměť bude starat sama. Ta funkce tedy vrátí true, pokud vrchol viděla poprvé, a false pokud ho navštívila už dřív a tentokrát ho proto ignorovala. Kód díky tomu zůstane docela přehledný. Uvědomte si zároveň, že v obecném grafu nemáme označeného rodiče a syny – všechno jsou pro nás jenom sousedi. Aspoň jeden vrchol tedy při procházení sousedů vyignorujeme vždycky, a to ten, ze kterého jsme původně přišli.

Zkuste si podle tohohle návodu přepsat průchod do hloubky bez rekurze (řešení) koren.pocet_navstivenych = 0; navstiv(koren); var cesta = [koren]; while (cesta.length > 0) { var posledni = cesta[cesta.length - 1]; if (posledni.pocet_navstivenych < posledni.sousedi.length) { var syn = posledni.sousedi[posledni.pocet_navstivenych]; posledni.pocet_navstivenych += 1; if (navstiv(syn)) { syn.pocet_navstivenych = 0; cesta.push(syn); } } else { cesta.pop() } } a průchod do šířky (řešení). var soucasna = [koren]; while (soucasna.length > 0) { var pristi = []; for (vrchol of soucasna) { if (navstiv(vrchol)) { for (syn of vrchol.sousedi) { pristi.push(syn); } } } soucasna = pristi; }

Algoritmus, který zvládne všechno

Průchod grafu do hloubky a do šířky mají hodně společných rysů. Pojďme je zdůraznit tak, že napíšeme jediný program, který bude podle potřeby dělat obojí: var struktura = [koren]; while (struktura.length > 0) { var vrchol = pop(struktura); if (navstiv(vrchol)) { for (soused of vrchol.sousedi) { push(struktura, soused); } } }

Stručnost nade vše! Pořadí průchodu grafem nám určí funkce push(struktura, vrchol) a pop(struktura). V proměnné struktura máme obyčejné pole, ale můžeme s ním zacházet jako s některou z následujících datových struktur, a tím získat různé způsoby průchodu grafem:

Zásobník

Náboje se do zásobníku vkládají na stejném konci, jakým budou pak vycházet ven, a navrchu je tedy vždycky ten, který jsme vložili jako poslední. Funkce push a pop jsou už v Javascriptu připravené, stačí je napsat jako struktura.push(vrchol) a struktura.pop(). Vrcholy se budou přidávat na konec pole, potažmo z něj vyndávat.

Při použití zásobníku navštívíme vrcholy v pořadí, jako při procházení do hloubky. Oproti programu napsanému výše (procházení do hloubky bez rekurze) bude tenhle výrazně kratší a elegantnější. Bude ale mít jednu podstatnou vadu na kráse: v poli struktura jsou krom cesty z kořene naházené ještě další vrcholy, na které se chceme později podívat. Kdybychom cestu z kořene v programu vážně potřebovali, museli bychom si ji s trochou námahy obstarat – můžete si rozmyslet, jak přesně.

Fronta

Ve frontě platí, kdo dřív přijde, ten dřív mele. Proto se jí často říká také FIFO, čili first-in-first-out. Funkci struktura.push(vrchol) můžeme použít i tentokrát, protože opravdu přidává na konec fronty. Funkci pop(struktura, vrchol), která z pole vytrhne prvek na jeho začátku a přehází ostatní o jedno místo dopředu můžeme napsat pomocí cyklu (řešení), function pop(struktura, vrchol) { var vysledek = struktura[0]; for (var i=1; i<struktura.length; i++) { struktura[i-1] = struktura[i]; } struktura.pop(); return vysledek; } anebo se podívat do manuálu a zjistit, že přesně tohle dělá funkce struktura.shift().

Můžete si rozmyslet, že program s frontou navštíví vrcholy ve stejném pořadí jako procházení do hloubky. V prve napsaném programu jsme používali dvě pole, která jsou tady prostě slepená za sebe, a vrcholy ze zoučasné generace rovnou po použití zahazujeme. Přináší to ale ošklivou bolístku v časové složitosti: při každém odtrhnutí vrcholu musíme celou frontu projít a posunout, takže celkově by algoritmus běžel v čase O(n2).

Naprogramovat rychlou frontu by znamenalo, že vrcholy ze začátku nebudeme hned mazat. Funkce pop(struktura) si tak musí pamatovat, kolik mrtvolek má překročit na začátku fronty. Má vrátit první živý vrchol za nimi a poznamenat si, že i ten už je odepsaný. Takhle vzniklý hřbitov smažeme až ve chvíli, kdy bude zabírat půlku fronty. Půlka je totiž dobrý kompromis mezi rychlostí a šetřením pamětí – můžete si odvodit, že v tomhle případě celý průchod do šířky poběží zase v čase O(m), jak se patří.

Halda

Ze zvědavosti zkusme použít funkce heappush(struktura, prvek, cmp) a heappop(struktura, cmp), jak jsme s nimi pracovali dříve. Aby bylo vrcholy podle čeho porovnávat, pojďme jim nastavit každému nějakou vzdálenost: vrchol.vzdalenost bude prostě číslo, které určíme každému vrcholu nejpozději ve chvíli, kdy ho vkládáme do haldy. Funkce cmp(a, b) pak prostě vrací, jestli a.vzdalenost < b.vzdalenost.

Jako rozcvičku si můžeme rozmyslet případ, kdy vzdálenost budeme nastavovat postupně na 1, 2, 3 atd. v pořadí, jak vrcholy navštěvujeme. Půjde o procházení do hloubky, nebo do šířky? Jaké číslování bychom mohli použít, abychom získali ten druhý způsob procházení?

Zajímavější je spočítat každému vrcholu vzdálenost, po které jsme se do něj dostali. To znamená, že při vkládání sousedů do haldy je nastavíme na vzdálenost vrcholu, ve kterém právě jsme, a přičteme délku příslušné hrany. (Pokud je vzdálenost už nastavená, necháme ji být a vrchol do haldy ani nebudeme dávat – zjevně tam už je.) Tímhle získáme Dijkstrův algoritmus, velmi stručně a elegantně napsaný.

Kdybychom vrcholy řadili jen podle délky hrany, po které jsme přišli, a vzdálenosti nijak nesčítali, tak bychom je prošli ve stejném pořadí jako v Jarníkově algoritmu. Minimální kostru grafu získáme prostě tak, že vypíšeme všechny použité hrany.