Serie Algoritmy

Tato serie ma za cil seznamit Vas s jednoduchymi algoritmy, ktere treba bezne pouzivate (nebo vyuzivate) a mozna o tom ani nevite. V nekolika dilech (+ bonusovka po kazdych ctyrech - na bonusovku nebudete potrebovat sbirat zadna cisla z vicek ani nic podobneho) se mimo jine dozvite, jak Vase GPS vyhledava nejkratsi trasu po silnicich, jak se elektrifikovala Morava, nebo treba jak projit tunel, kdyz dochazi baterky. Pokud Vas tohle vsechno zajima, pak je tahle serie urcena prave Vam!

S grafy a stromy jsme se seznamili minule a jelikoz je to obsahle tema (navic jedno z mych oblibenych), jeste u nich chvili zustaneme. Tentokrat se budeme trochu vic zabyvat "teorii" - podivame se jak se na graf divaji pocitace, a na ty, co to vydrzi, ceka jednoduchy algoritmus na zjistovani souvislosti grafu. Pokud nebudete rozumet nekterym terminum, doporucuji podivat se do listingu predchoziho dilu.

Reprezentace grafu

V tomto i dalsich dilech se podivame na problemy, ktere se bezne resi na pocitaci. Tomu pak odpovidaji i algoritmy, takze myslim, ze pro zacatek nebude na skodu vysvetlit, jak se takovy pocitac na graf diva.

Hned na zacatek musim zduraznit, ze pocitace (aspon pokud vim) si neumi vzit problem jako celek, coz je u jednoduchych prikladu na zavadu, ale u slozitejsich to muze byt vyhoda. Dam priklad: Mate graf s peti vrcholy a chcete zjistit, jestli je souvisly (viz dale). Clovek se podiva a vidi, ze je souvisly, zatimco pocitac bere vrchol po vrcholu a testuje je, coz je (na pocet operaci) mnohem pomalejsi. Jenze kdyz mate graf s milionem vrcholu, jste s metodou "kouknu a vidim" v koncich, zatimco pocitaci to "jeho" zpusobem trva stejne dlouho (relativne vzhledem k poctu vrcholu a hran).
Pocitac si umi vsehovsudy pamatovat realne cislo (to nepotrebujeme), cele cislo (integer, int - to je to, co chceme) a par dalsich veci, jako retezce a znaky, ktere taktez nepotrebujeme. Krom toho si tyto typy umi pamatovat v ruznych sestavach jako je napr. pole. Pro lidi absolutne nedotcene programovanim, ktere ovsem algoritmy zajimaji, vysvetlim, co to pole je. Je to usporadany seznam neceho (treba integeru). Hlavni vyhoda je v primem pristupu k ulozenym polozkam podle indexu; priklad: mame pole P, obsahujici cisla od 9 do 0, pak P[0] = 9, P[3] = 6 apod. Pole muzou byt i vicerozmerna.

A ted uz konecne k reprezentacim grafu. Nejpouzivanejsi jsou tyto dve:

1. Matice sousednosti : dvourozmerne pole integeru velikosti N x N indexovane vrcholy. Cislo GRAF[i,j] vyjadruje vahu hrany (popr. jestli hrana existuje). Timto zpusobem lze vyjadrit i orientovany graf (pak se GRAF[i,j] nemusi rovnat GRAF[j,i]). Bohuzel, pokud mame velky graf s malo hranami, pamatujeme si zbytecne moc cisel (vetsina cisel v poli je 0). Proto se tahle reprezentace tolik nepouziva.
2. Seznam nasledniku : Dve pole integeru: V (N prvku) a E (M prvku). V poli V jsou pod cisly vrcholu ulozeny indexy pole E, kde zacina seznam nasledniku daneho vrcholu. Ukazeme si to na prikladu:

Souvislost grafu

DEF.: Graf je souvisly prave kdyz z kazdeho jeho vrcholu existuje cesta do kazdeho jineho vrcholu. (cimz narazim na problem, ze jsem nezadefinoval cestu v grafu, takze hura na ni!)
DEF.: Cesta v grafu je posloupnost vrcholu a hran, kde se kazdy vrchol vyskytuje nejvys jednou:
(v₀, e₁, v₁, ... e_n, v_n), kde e_i = {v_i-1, v_i} (= je ohranicena vrcholy v zavorce) a nalezi mnozine hran grafu E.

Tak a ted k samotnemu problemu: chceme zjistit, jestli je nejaky graf souvisly (neni tezke nakreslit i pomerne jednoduchy graf tak, aby to nebylo videt) a pokud ne, kolik ma komponent souvislosti.
Jednotlive komponenty souvislosti si budeme "barvit" (napriklad znacit cisly od 1, at nakonec rovnou vime, kolik komponent mame). Na pomoc si vezmeme frontu (coz je v podstate pole, do ktereho zezadu pridavame prvky, ktere chceme zpracovat a zepredu je odebirame na zpracovani).

Algoritmus:
0) (pocitame s tim, ze graf obsahuje alespon jeden vrchol a ze ho mame jako seznam nasledniku)
1) vezmeme libovolny neobarveny bod grafu a pridame ho do fronty;
2) dokud neni fronta prazdna (tzn. dokud nedojdou body v tehle komponente), provadime krok 3):
3) z fronty odebereme bod, obarvime ho a do fronty pridame vsechny jeho neobarvene sousedy;
4) pokud existuje v grafu neobarveny vrchol, zvetsime barvu o 1 a vratime se na krok 1)
5) v promenne barva mame ulozeny pocet komponent a v reprezentaci grafu je mame hezky rozlisene -> ukol splnen;

Priklady

Priklad 1:

Na obrazku mate graf. Urcete, kolik ma komponent souvislosti.



(Rada: Jelikoz jste lidi a ne pocitace, doporucuji aplikovat algoritmus rovnou na graf a ne prevadet graf na seznam nasledniku.)

Priklad 2:

V nasledujicich tabulkach mate zapsany graf jako seznam nasledniku. Kolik ma komponent souvislosti?

POZOR! 27.2.2009 probehla zmena souradnic finalky!!!

Finalka

Jelikoz si uvedomuji, ze tenhle dil serie je (pro neprogramatory) poradna zabiracka, necham si dalsi algoritmy do pristich dilu a prejdu rovnou k umisteni kesky.

Krabicku najdete na souradnicich
N 49° A
E 014° B,
A = ([vysledek 1. prikladu] * 20 000 - [vysledek 2. prikladu] * 330 + 70) / 1 000
B = (([vysledek 1. prikladu] + [vysledek 2. prikladu]) * 5 040 + [vysledek 1. prikladu] * 30 + [vysledek 2. prikladu] + 87) / 1 000

K finalce se nejlepe dostanete pesky nebo na kole z Komoran (bus 205, 165), z Beranku (konecna pro bus 139, 253 - pozor, v ceste je rokle, ktera nejde prekonat vsude), nebo z Cholupic (bus 173, 341, 342). V Cholupicich nebo u blizkeho sportovniho letiste muzete nechat auto, jen upozornuji, ze cesta z Cholupic k letisti neni vzdy sjizdna a navrhovana byla spis pro traktor, nez pro osobni auto.

Provazej Vas Signal!