Lekce 2 - Náhodný průchod grafem, průchod do hloubky a do šířky

V minulé lekci, Úvod do teorie grafů, jsme si udělali úvod do teorie grafů.

Dnes se podíváme na 3 nejzákladnější průchody grafem, jsou to:

• Náhodný průchod
• Průchod do hloubky
• Průchod do šířky

Tento článek počítá s povědomím o:

• Frontě a zásobníku
• Úvodu do grafů

(případně se podívejte na dané články)

Příklad

Představme si, že máme např. mapu Evropy. Vrcholy grafu budou jednotlivé státy a hrana mezi dvěma vrcholy povede právě tehdy, když budou státy spolu sousedit. Takový graf bude docela řídký, ale to vůbec nevadí. Řekněme, že plánujeme rodinnou dovolenou a manžel programátor si napíše program na průchod tímto grafem. Chce se dostat např. z Čech do Itálie. My sice víme, že musíme jet přes Rakousko a jsme tam, ale jak to říci počítači?

Náhodný průchod

Prvnímu průchodu, který si zmíníme, říkejme náhodný, i když nejspíše nemá ani žádný název. Jednoduše pojedeme tam, jak nám to přijde pod ruku. Tak se může stát, že rodinka pojede do Německa, Polska, Slovenska, přes Ukrajinu a Rusko se podívá zpět na pobaltské státy, pak opět do Polska a domů. Může se stát, že se omylem tato cesta zacyklí a budou jezdit stále dokola přes tyto státy a doufat, že najdou Itálii. V lepším případě to třeba vezmou dolů do Rakouska, až nakonec Itálii najdou. Jen o 10 mezizastávek navíc. Takto tedy ne... Ideálně totiž chceme "cestu", tj. posloupnost hran, které se neopakují. Nechceme jednu hranici státu použít vícekrát.

Průchod do hloubky - DFS (Depth-first search)

Tento průchod bych nazval splašeným býkem. Vybereme směr a prostě pojedeme. Zní to skoro jako minulá metoda, až na to, že tentokrát si pamatujeme, kde jsme byli a nezacyklíme se.

Algoritmus DFS

V tomto případě bychom mohli mít hromadu špendlíků dvou barev, třeba zelené a červené. Vždy, když do nějakého státu přijedeme, píchneme do něj zelený špendlík na znamení, že jsme tu již byli. Pokud je ten stát Itálie, máme vyhráno. Pokud ne a máme kolem sebe ještě nějaký stát, který nemá na sobě žádný špendlík, pokračujeme do tohoto státu.

Může se stát, že tímto algoritmem dojdeme třeba na Island, kde hranice Evropy končí a musíme zpět. Když již nemůžeme jít nikam, nahradíme zelený špendlík za červený a jdeme zpátky, dokud nemůžeme někam píchnout zelený špendlík, nebo dokud neprojdeme celou Evropu a nezjistíme, že Itálie neexistuje. (Třeba se přejmenovala, kdo ví...)

Ukázka průchodu

Využijeme nyní znalosti nabyté. Průchod do hloubky se implementuje pomocí zásobníku. Představme si, že si uspořádáme mapu Evropy do stromu takto:

Česká republika sousedí s Polskem, Slovenskem, Německem a Rakouskem, Polsko s Ukrajinou atd. Česká republika bude kořenový element, protože z Čech vyjíždíme. V tomto grafu si vezmeme zelené připínáčky a vybereme si Česko, Polsko, dále Ukrajinu, dále např. Moldavsko, Rumunsko, Bulharsko, Srbsko, Chorvatsko, Slovinsko, Maďarsko, Rakousko, Slovensko a konec. Zelenou již použít nemůžeme. Česká republika, Polsko, Ukrajina, Rakousko i Maďarsko mají všichni zelenou. Musíme vzít červenou a označit Slovensko za konečnou větev. Vedle Slovenska Itálie prostě není. Vracíme se do Rakouska, jedeme do Švýcarska a nakonec narazíme na Itálii.

Jak se pozná pořadí?

Pořadí států je závislé na tom, jak je vložíme do programu. Můžeme mít štěstí a jet do Itálie rovnou, nebo smůlu a... máme roundtrip po Evropě.

Alternativní příklad

Pokud je vám to stále nejasné, tak si představte, že bydlíte v paneláku v 1. patře a chcete najít cestu k sousedům, kteří bydlí o patro výše. Jenže vy nejdříve zkusíte přízemí, pak vedlejší budovu, pak vedlejší město, pak vedlejší stát... asi to není nejvhodnější. Z těchto příkladů je patrná jedna věc:

NIKDY tento algoritmus nepoužívejte, když hledáte nejkratší cestu odněkud někam.

Časová složitost

Musíme prostě projít každým vrcholem a každou hranou, tzn. O(|V| + |E|), kde |V| je počet vrcholů a |E| je počet hran.

Zdrojový kód

Zdrojový kód algoritmu DFS by vypadal následovně:

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");
}

Průchod do šířky - BFS (Breath-first search)

Vezměme to tedy jinak. Nebudeme strom procházet do hloubky, neboli jak splašený býk, ale použijeme něco, čemu se říká algoritmus vlny, viz. článek Algoritmus šíření do šířky (Vlna). Vlna proto, protože všechny vrcholy, které jsou na jedné hladině, projdu najednou. Využijeme k tomu frontu.

Algoritmus

Vždy, když do nějakého státu přijedeme, podíváme se, jestli je to Itálie. Když ne, koukneme na manželku a oznámíme jí všechny státy, které navštívíme dále.

Ukázka průchodu

Takže začínáme v Čechách, do fronty vložíme ČR. Odebereme z fronty ČR a dáme do fronty Polsko, Rakousko, Slovensko a Německo. (Trochu jsem to pořadí přeházel, ať s tím nezabijeme celý den ) Česko dáme do nějakého pole již prošlých států. Koukneme se na Polsko, odebereme ho z fronty a do ní přidáme Rusko, Litvu, Bělorusko, Ukrajinu, Slovensko, (ČR už ne) Německo. Navštívíme Rakousko, odebereme ho z fronty a přidáme Itálii, Slovinsko, Maďarsko, Lichtenštejnsko, Švýcarsko. Navštívíme Slovensko a ... . Navštívíme Německo a... Nyní jsme navštívil všechny přímé potomky ČR a víme, že Česko nesousedí s Itálií. Jdeme nyní na potomky Polska, které však také selžou, tzn. Polsko nesousedí s Itálií. Jdu na potomky Rakouska a hele, Itálie... Našli jsme ji + známe nejkratší cestu. Přes Rakousko.

Pozn. Ano, je to lehce neefektivní v reálném světě, ale uvědomme si, že bychom vůbec neměli mapu a žili bychom na planetě, kde má Evropa 2000 států. Pak je toto řešení přeci jen nejefektivnější i v reálném světě. (A počítač nemusí řešit přejíždění z místa na místo, skočí si tam).

Časová složitost

Musíme prostě projít každým vrcholem a každou hranou, tzn. O(|V| + |E|), kde |V| je počet vrcholů a |E| je počet hran.

Pokud se vám zdá, že jsem u časové složitosti udělal Ctrl + C a Ctrl + V z minulého algoritmu, ... ano, udělal Tyto algoritmy totiž dělají to samé. Nakonec projdou celý graf. Liší se jen použitím na konkrétní aplikaci, viz dále.

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");
}

Kdy používat BFS a kdy DFS?

Kdy používat šíření do šířky a kdy do hloubky? Jako vždy ani zde není jednoznačná odpověď a programátor sám musí zvážit, jakou povahu má daná úloha (např. zda chceme nejkratší cestu).

Výhody DFS

• Nevyžaduje tak velkou paměť jako BFS. Pokud víme, že jsme levou větev již navštívili a nic tam nebylo, tak si ji již nemusíme pamatovat. Stačí si pamatovat jen kořen té větve. Pokud víme, že Itálie není vedle Slovenska a ani vedle Ukrajiny a ani vedle Polska, stačí nám si pamatovat, že není vedle Slovenska. A máme o paměť více.
• Pokud víme, že je řešení ve velké hloubce, tak máme šanci najít řešení mnohem rychleji než BFS. Můžeme ho však najít i pomaleji, rychlost není zaručena.

Výhody BFS

• Najde nejkratší cestu - za předpokladu, že je graf neohodnocený, tzn. vzdálenost mezi hranami je všude stejná
• Umí hledat řešení i v nekonečných či opravdu velkých grafech
• Je-li více řešení a některá jsou blíž, některá dál – najde nejbližší.

Obě metody jsou naprosto esenciální znalostí každého programátora. Proto na závěr dávám ještě jednou porovnání, ať nevznikne žádná nejasnost.

V další lekci, Hledání nejkratší cesty v grafu, budeme hledat nejkratší cestu v orientovaném i neorientovaném grafu pomocí algoritmů Dijkstra a Floyd-Warshall.