2. diel - Náhodný priechod grafom, priechod do hĺbky a do šírky

V minulej lekcii, Úvod do teórie grafov , sme sa zoznámili so základnými pojmami. Dnes sa pozrieme na 3 najzákladnejšie priechody grafom, sú to:

• náhodný priechod
• Priechod do hĺbky
• Priechod do šírky

Tento článok počíta s povedomím o:

• Fronte a zásobníka
• Úvodu do grafov

(Prípadne sa pozrite na dané články)

Príklad

Predstavme si, že máme napr. Mapu Európy. Vrcholy grafu budú jednotlivé štáty a hrana medzi dvoma vrcholmi povedie práve vtedy, keď budú štáty spolu susediť. Takýto graf bude celkom riedky, ale to vôbec nevadí. Povedzme, že plánujeme rodinnú dovolenku a manžel programátor si napíše program na priechod týmto grafom. Chce sa dostať napr. Z Čiech do Talianska. My síce vieme, že musíme ísť cez Rakúsko a sme tam, ale ako to povedať počítači?

Náhodný priechod

Prvému priechodu, ktorý si spomenieme, hovorme náhodný, aj keď pravdepodobne nemá ani žiadny názov. Jednoducho pôjdeme tam, ako nám to príde pod ruku. Tak sa môže stať, že rodinka pôjde do Nemecka, Poľska, Slovenska, cez Ukrajinu a Rusko sa pozrie späť na pobaltské štáty, potom opäť do Poľska a domov. Môže sa stať, že sa omylom táto cesta zacyklí a budú jazdiť stále dookola cez tieto štáty a dúfať, že nájdu Taliansku. V lepšom prípade to treba vezmú dole do Rakúska, až nakoniec Taliansku nájdu. Len o 10 medzizastávok navyše. Takto teda nie ... Ideálne totiž chceme "cestu", tj. Postupnosť hrán, ktoré sa neopakujú. Nechceme jednu hranicu štátu použiť viackrát.

Priechod do hĺbky - DFS (Depth-first search)

Tento priechod by som nazval splašeným býkom. Vyberieme smer a jednoducho pôjdeme. Znie to skoro ako minulá metóda, až na to, že tentoraz si pamätáme, kde sme boli a nezacyklíme sa.

Algoritmus DFS

V tomto prípade by sme mohli mať hromadu špendlíkov dvoch farieb, napríklad zelené a červené. Vždy, keď do nejakého štátu prídeme, pichneme doň zelený špendlík na znamenie, že sme tu už boli. Ak je ten štát Taliansko, máme vyhrané. Ak nie a máme okolo seba ešte nejaký štát, ktorý nemá na sebe žiadny špendlík, pokračujeme do tohto štátu.

Môže sa stať, že týmto algoritmom dôjdeme potrebné na Island, kde hranice Európy končia a musíme späť. Keď už nemôžeme ísť nikam, nahradíme zelený špendlík za červený a ideme späť, kým nemôžeme niekam pichnúť zelený špendlík, alebo kým neprejdeme celú Európu a nezistíme, že Taliansko neexistuje. (Treba sa premenovala, kto vie ...)

Ukážka priechodu

Využijeme teraz vedomosti nadobudnuté. Priechod do hĺbky sa implementuje pomocou zásobníka. Predstavme si, že si usporiadame mapu Európy do stromu takto:

Česká republika susedí s Poľskom, Slovenskom, Nemeckom a Rakúskom, Poľsko s Ukrajinou atď. Slovenská republika bude koreňový element, pretože z Čiech vyrážame. V tomto grafe si vezmeme zelenej pripináčiky a vyberieme si Česko, Poľsko, ďalej Ukrajinu, ďalej napr. Moldavsko, Rumunsko, Bulharsko, Srbsko, Chorvátsko, Slovinsko, Maďarsko, Rakúsko, Slovensko a koniec. Zelenú už použiť nemôžeme. Česká republika, Poľsko, Ukrajina, Rakúsko i Maďarsko majú všetci zelenú. Musíme vziať červenú a označiť Slovensko za konečnú vetvu. Vedľa Slovenska Taliansko jednoducho nie je. Vraciame sa do Rakúska, ideme do Švajčiarska a nakoniec narazíme na Taliansko.

Ako sa pozná poradí?

Poradie štátov je závislé na tom, ako ich vložíme do programu. Môžeme mať šťastie a ísť do Talianska rovno, alebo smolu a ... máme Roundtrip po Európe.

Alternatívne príklad

Ak je vám to stále nejasné, tak si predstavte, že bývate v paneláku v 1. poschodí a chcete nájsť cestu k susedom, ktorí bývajú o poschodie vyššie. Lenže vy najskôr skúsite prízemí, potom vedľajšie budovu, potom vedľajšie mesto, potom vedľajšie stať ... asi to nie je najvhodnejšie. Z týchto príkladov je zrejmá jedna vec:

NIKDY tento algoritmus nepoužívajte, keď hľadáte najkratšiu cestu odniekiaľ niekam.

Časová zložitosť

Musíme jednoducho prejsť každým vrcholom a každú hranou, tzn. O(|V| + |E|), kde |V| je počet vrcholov a |E| je počet hrán.

Zdrojový kód

Zdrojový kód algoritmu DFS by vyzeral nasledovne:

public void DFS(State state)
{
    bool found = false;
    Stack<State> stack = new Stack<State>();
    state.wasVisited = true;
    stack.Push(state);

    while (stack.Count > 0)
    {
        state = stack.Pop();
        if (state.Name == "Italy")
        {
            Console.WriteLine("Wohooooo");
            found = true;
            break;
        }
        foreach (State NewState in state.Neighbours)
        {
            if (!NewState.wasVisited)
            {
                NewState.wasVisited = true;
                stack.Push(NewState);
            }
        }
    }

    if (!found)
        Console.WriteLine("Italy not found");
}

Priechod do šírky - BFS (Breath-first search)

Zoberme to teda inak. Nebudeme strom prechádzať do hĺbky, čiže ako splašené býk, ale použijeme niečo, čomu sa hovorí algoritmus vlny, viď. článok Algoritmus šírenie do šírky (Vlna). Vlna preto, lebo všetky vrcholy, ktoré sú na jednej hladine, prejdem naraz. Využijeme na to front.

Algoritmus

Vždy, keď do nejakého štátu prídeme, pozrieme sa, či je to Taliansko. Keď nie, pozrieme na manželku a oznámime jej všetky štáty, ktoré navštívime ďalej.

Ukážka priechodu

Takže začíname v Čechách, do fronty vložíme ČR. Odoberieme z frontu SR a dáme do fronty Poľsko, Rakúsko, Slovensko a Nemecko. (Trochu som to poradí prehádzali, nech s tým nezabijeme celý deň ) Česko dáme do nejakého poľa už prejdených štátov. Pozrieme sa na Poľsko, odoberieme ho z frontu a do nej pridáme Rusko, Litvu, Bielorusko, Ukrajinu, Slovensko, (ČR už nie) Nemecko. Navštívime Rakúsko, odoberieme ho z frontu a pridáme Taliansku, Slovinsko, Maďarsko, Lichtenštajnsko, Švajčiarsko. Navštívime Slovensko a .... Navštívime Nemecko a ... Teraz sme navštívil všetky priame potomkov SR a vieme, že Česko nesusedí s Talianskom. Ideme teraz na potomkov Poľska, ktoré však tiež zlyhajú, tzn. Poľsko nesusedia s Talianskom. Idem na potomkov Rakúska a hele, Taliansko ... Našli sme ju + poznáme najkratšiu cestu. Cez Rakúsko.

Pozn. Áno, je to ľahko neefektívne v reálnom svete, ale uvedomme si, že by sme vôbec nemali mapu a žili by sme na planéte, kde má Európa 2000 štátov. Potom je toto riešenie predsa len najefektívnejšie aj v reálnom svete. (A počítač nemusí riešiť prechádzaní z miesta na miesto, skočí si tam).

Časová zložitosť

Musíme jednoducho prejsť každým vrcholom a každú hranou, tzn. O(|V| + |E|), kde |V| je počet vrcholov a |E| je počet hrán.

Ak sa vám zdá, že som u časovej zložitosti urobil Ctrl + C a Ctrl + V z minulého algoritmu, ... áno, urobil Tieto algoritmy totiž robia to isté. Nakoniec prejdú celý graf. Líšia sa len použitím na konkrétnu aplikáciu, viď ďalej.

Zdrojový kód

Algoritmus v C #:

void BFS(State  state)
{
    bool found = false;
    Queue<State> queue = new Queue<State>();
    // přidáme Českou republiku
    state.wasVisited = true;
    queue.Enqueue(state);

    while (queue.Count > 0)
    {
        state = queue.Dequeue();
        if (state.Name == "Italy")
        {
            Console.WriteLine("Wohoooooo");
            found = true;
            break;

        }

        foreach (State newState in state.Neighbours)
        {
            if (!newState.wasVisited)
            {
                newState.wasVisited = true;
                queue.Enqueue(newState);
            }
        }

    }

    if (!found)
        Console.WriteLine("Italy not found");
}

Kedy používať BFS a kedy DFS?

Kedy používať šírenie do šírky a kedy do hĺbky? Ako vždy ani tu nie je jednoznačná odpoveď a programátor sám musí zvážiť, akú povahu má daná úloha (napr. Či chceme najkratšiu cestu).

Výhody DFS

• Nevyžaduje tak veľkú pamäť ako BFS. Ak vieme, že sme ľavú vetvu už navštívili a nič tam nebolo, tak si ju už nemusíme pamätať. Stačí si pamätať len koreň tej vetvy. Ak vieme, že Taliansko nie je vedľa Slovenska a ani vedľa Ukrajiny a ani vedľa Poľska, stačí nám si pamätať, že nie je vedľa Slovenska. A máme o pamäť viac.
• Ak vieme, že je riešenie vo veľkej hĺbke, tak máme šancu nájsť riešenie oveľa rýchlejšie ako BFS. Môžeme ho však nájsť aj pomalšie, rýchlosť nie je zaručená.

Výhody BFS

• Nájde najkratšiu cestu - za predpokladu, že je graf Neohodnotené, tzn. vzdialenosť medzi hranami je všade rovnaká
• Vie hľadať riešenia aj v nekonečných či naozaj veľkých grafoch
• Ak je viac riešení a niektoré sú bližšie, niektoré ďalej - nájde najbližšie.

Obe metódy sú úplne esenciálne znalostí každého programátora. Preto na záver dávam ešte raz nákupný, nech nevznikne žiadna nejasnosť.