Algoritmus pro vyhledávání souvislých (silně souvislých) komponent za použití Floydova algoritmu
Michal Radecký, L97085

Princip algoritmu
     Algoritmus je založen na zpracování výsledků Floydova algoritmu. Tj. z matice dosažitelnosti určí jednotlivé komponenty.
     Nejprve je tedy nutné na zadaný graf aplikovat Floydův algoritmus, který z matice cen, vytvoří matici dosažitelnosti. V našem případě, je zbytečné pracovat s kompletní maticí cen, a je postačující pracovat s maticí, kde jsou ceny nahrazeny jedničkou.
     Po vytvoření této matice pak aplikujeme algoritmus zařazování vrcholů do komponent. Tento algoritmus je založen na zjišťování dosažitelných vrcholů z výchozího vrcholu a naopak, dosažitelnost z dosažených vrcholů zpět do výchozího vrcholu. Je-li tato podmínka splněna, je dosažený vrchol zařazen do stejné komponenty, jako byl vrchol výchozí. Algoritmus končí, jakmile jsou všechny vrcholy zařazeny do některé z komponent.

Implementace algoritmu
     Vlastní implementace je v jedné funkci, která jako vstupní parametr dostává celou strukturu grafu a alokovane pole, a jak výsledek vrací ukazatel na pole, které k jednotlivým vrcholům přiřazuje číslo příslušné komponenty. Vzhledem k předávání dat, jsou vráceny čísla komponent postupně, nikoliv podle čísla vrcholů
     Jako první krok je vytvoření matice A, jako dvojrozměrného dynamického pole o rozměrech [počet vrcholů][počet vrcholů]. Dále je toto pole inicializováno na počáteční hodnotu (všechny prvky jsou X, hlavní diagonála pak 0). Nakonec je podle struktury grafu jednotlivým prvkům přiřazena hodnota (viz.výše).
     Dalším krokem je vytvoření matice dosažitelnosti, to je provedeno pomocí tří vnořených cyklů a trojůhelníkové nerovnosti.
     Poslední část algoritmu potřebuje ke své činnosti ještě vytvořené pole K o velikosti [počet vrcholů]. Prvky tohoto pole se inicializují na hodnotu X. Dále se vybere první prvek, jehož hodnota v K je X. Pak se prochází řádek matice odpovídající vybranému vrcholu a kontroluje se, jestli jsou vrcholy dosažitelné z vybraného vrcholu a zpět. Platí-li to, je zkoumaný vrchol v poli K označen číslem komponenty. Tato část algoritmu je uzavřena v cyklu, který probíhá tak dlouho, dokud počítadlo zařazených vrcholů není rovno počtu vrcholů.

     Funkce se tedy volá:
                                                           ukazatel = Funkce(Graf);
    , kde ukazatel je ty pointer na int a Graf je ukazatel na strujturu grafu (TGraf).
     Po provedení funkce je tedy ukazatel nastaven na první prvek dynamicky vytvořeného pole K a je nutné ho po zpracovácní dealokovat příkazem
                                                           delete [počet vrcholů]ukazatel;