Úvod : Popis aplikace : Aplikace : Tvořící algoritmy : Řešící algoritmy : S-ACO
## Algoritmy tvořící bludiště Prohledávání do hloubky - algoritmus probírá hrany grafu vycházející z naposled objeveného uzlu, který má ještě neprobrané hrany. Když probere všechny jeho hrany, vrátí se zpět k původnímu uzlu. Z něho zase pokračuje po další dosud neprobrané hraně. Algoritmus pracuje tak dlouho, dokud se neobjeví všechny uzly dosažitelné z prvního výchozího uzlu. Jestliže zbývá nějaký neobjevený uzel, volí se jako další výchozí uzel a algoritmus pokračuje z něho, dokud nejsou objeveny všechny uzly. Primův algoritmus - algoritmus vychází z libovolného uzlu grafu a udržuje si seznam již objevených uzlů a jejich vzdáleností od propojené části grafu. V každém svém kroku připojí ten z uzlů, mezi nímž a propojenou částí grafu je hrana nejnižší délky a označí sousedy nově připojeného uzlu za objevené, případně zkrátí vzdálenosti od již známých uzlů, pokud byla nalezena výhodnější hrana. Algoritmus končí v okamžiku, kdy jsou propojeny všechny uzly grafu. Kruskalův algoritmus - je vytvořen z původního grafu nový graf, který obsahuje stejné uzly jako původní graf, avšak žádné hrany. Poté jsou seřazeny hrany do neklesající posloupnosti podle cen hran mezi uzly a postupně jsou přidávány hrany do nového grafu. Pokud se po přidání hrany vytvoří v grafu kružnice, hranu se odebere. Přidávání hran se opakuje do doby, než je graf spojitý, nebo už není k dispozici žádná hrana pro přidání. Ellerův algoritmus - algoritmus generování bludiště vychází z toho, že každá buňka v řádku je zahrnuta v unikátním množině (setu). Následně se každá buňka řádku projde a náhodně se určí, bude-li sloučena do stejného setu s buňkou sousední. Pokud ano, zruší se mezi nimi zeď. Vertikální propojení, které musí v každém setu existovat minimálně jedno, je taktéž vytvářeno náhodně. Následující řádek si opět vytvoří unikátní množinu buňek, ale s tím, že převezme vlastnosti z předchozího řádku. Cyklus se opakuje a pro poslední řádek se nevytvářejí vertikální propojení. Půlení intervalů - algoritmus rozdělí plochu bludiště vertikální nebo horizontální hranou na dvě nové plochy. V nově vytvořené hraně se vytvoří jedna cesta (propojení) tak, aby byly plochy propojeny. Toto rozdělení se pak rekurzivně opakuje na nově vzniklé plochy a na jejich další rozdělení. Dělení ploch končí, jakmile výška nebo šířka dělené plochy je rovna požadované výšce nebo šířce buňky bludiště.
Vytvořil Jiří Večerka, 2015