Mriežky - implementačné tipy a triky

Mriežkami v tomto článku myslíme grafy tvaru pravidelnej mriežky, napríklad takéto:

V tomto článku si ukážeme zopár trikov, ktoré nám pomôžu implementovať grafové algoritmy na mriežkach a vyhnúť sa pri tom väčšine chýb.

Reprezentácia v pamäti

Ako každý graf, aj mriežku si môžeme pamätať v zozname susedov, prípadne matici susednosti. To je však často zbytočne komplikované.

Pri štvorcových mriežkach $R \times S$ je každý vrchol určený svojimi súradnicami -- riadkom a stĺpcom. Je teda prirodzené každý vrchol označiť dvojicou $(x,y)$, kde $x$ je číslo jeho stĺpca a $y$ číslo jeho riadka. Ak si chceme pri každom vrchole pamätať nejakú informáciu (farbu, cenu, vzdialenosť od štartu...), môžeme to urobiť v dvojrozmernom poli typu $R \times S$. Informáciu pre vrchol $(x,y)$ si budeme pamätať v prvku poľa so súradnicami $x$ a $y$.

Hrany si nemusíme pamätať vôbec. Ak nás totiž zaujímajú susedia nejakého vrcholu $(x,y)$, vieme, že sú to $(x+1, y), (x, y+1), (x-1, y)$ a $(x, y-1)$ (prípadne ešte ďalší, ak má graf aj diagonálne hrany). Vynímkou sú vrcholy na kraji mriežky, ktoré niektorých z týchto susedov nemajú.

Iterovanie cez susedov

Pri grafových algoritmoch sa často stáva, že máme nejaký vrchol $(x,y)$ a potrebujeme niečo urobiť pre všetkých jeho susedov, prípadne pre všetkých jeho susedov spĺňajúcich určitú podmienku. Pri našej reprezentácii grafu by to mohlo vyzerať nasledovne:

if( /* TREBA SPRACOVAT VRCHOL (x+1, y) */ )
{
    /* SPRACUJ (x+1, y) */
}
if( /* TREBA SPRACOVAT VRCHOL (x, y+1) */ )
{
    /* SPRACUJ (x, y+1) */
}
if( /* TREBA SPRACOVAT VRCHOL (x-1, y) */ )
{
    /* SPRACUJ (x-1, y) */
}
if( /* TREBA SPRACOVAT VRCHOL (x, y-1) */ )
{
    /* SPRACUJ (x, y-1) */;
}

Takýto kód však nie je veľmi pekný a pri jeho písaní sa ľahko pomýlime. Ak pracujeme s mriežkou, kde má každý vrchol 8 susedov, je to ešte horšie.

Najčastejším zdrojom chýb pri tomto kuse kódu je, že sa pomýlime pri písaní +/- jednotiek. Tomuto sa dá elegantne vyhnúť tak, že tieto +/- jednotky vyextrahujeme do inej časti kódu. Vytvoríme si dve polia dX a dY, kde si budeme pamätať, čo potrebujeme pripočítať k súradniciam vrchola, aby sme dostali jeho susedov. Pri štvorcovej mriežke, kde má každý vrchol štyroch susedov, môžu vyzerať nasledovne:

int dX[4] = {1, 0, -1, 0};
int dY[4] = {0, 1, 0, -1};

Tieto dve polia majú nasledovný význam: prvý sused vrcholu (x,y) je vrchol (x+dX[0], y+dY[0]), druhý sused je (x+dX[1], y+dY[1]) atď.

Susedov teraz v programe nepotrebujeme vymenovať, ale môžeme ich spracúvať v cykle:

for(int smer=0; smer<4; smer++)
{
    int nx = x+dX[smer], ny = y+dY[smer];
    if( /* TREBA SPRACOVAT VRCHOL (nx, ny) */ )
    {
        /* SPRACUJ (nx, ny) */
    }
}

Tento kus kódu je omnoho menej náchylný na chyby. Ak je napríklad podmienka nejaký zložitý výraz, stačí ju napísať raz namiesto štyrikrát.

Hranice mriežky

Pri prechádzaní cez susedov vrchola si musíme dávať pozor, či nie je na kraji mriežky. V takom prípade nám totiž hrozí, že "vypadneme z mriežky", teda sa pokúsime spracovať vrchol, ktorý v našej mriežke nie je. Jedna možnosť je vždy pred spracovaním vrchola skontrolovať, či naozaj ide o vrchol mriežky (a ak nejde, preskočiť ho):

for(int smer=0; smer<4; smer++)
{
    int nx = x+dX[smer], ny = y+dY[smer];
    if(nx < 0 || nx >= S || ny < 0 || ny >= R) continue;
    if( /* TREBA SPRACOVAT VRCHOL (nx, ny) */ )
    {
        /* SPRACUJ (nx, ny) */
    }
}

Často sa to však dá aj pohodlnejšie: zarážkami. Príklad zo života:

Máme bludisko nakreslené v štvorcovej sieti. Každé políčko je buď priechodné (chodba) alebo nepriechodné (stena). Bludisko môžeme chápať ako graf: každé políčko je vrchol a medzi každými dvoma susednými políčkami je hrana (tento graf je teda mriežka). Ak našom bludisku spustíme nejaké prehľadávanie (napríklad do šírky), ktoré pôjde iba po priechodných políčkach, musíme si dávať pozor, aby nevypadlo cez okraj. Jednoduchý spôsob ako to docieliť je rozšíriť si našu mriežku o jeden riadok/stĺpec v každom smere a tieto nové riadky/stĺpce vyplniť stenami. Takto sa prehľadávanie nikdy nedostane na kraj mriežky (lebo cez steny nejde) a teda nemusíme ošetrovať vypadávanie.