Cycle finding je algoritmus s asymptotickou složitostí , jenž slouží k nalezení Eulerovského tahu v zadaném grafu. Eulerovský tah je tah, který projde každou hranu právě jednou.
Aby mohl graf obsahovat Eulerovský tah, tak musí být souvislý a zároveň musí mít buď všechny vrcholy sudého stupně (algoritmus nalezne uzavřený tah) nebo právě 2 vrcholy lichého stupně (algoritmus nalezne otevřený tah).
Nejznámějším případem hledání Eulerovského tahu je problém sedmi mostů města Královce.
Princip
Cycle finding algoritmus je založený na jednoduché myšlence – pokud z Eulerova grafu odebereme libovolnou kružnici, tak je jeho zbytek stále Eulerův. Proto stačí graf organizovaně procházet a odebírat postupně všechny kružnice.
Toto lze zajistit procedurou, která začne v počátečním uzlu a postupně rekurzivně navštěvuje, analogicky s procházením do hloubky (DFS), všechny sousedy. Na rozdíl od DFS ale může navštívit každý uzel vícekrát, každou hranu však pouze jednou.
Procedura vypíše při každém návratu z rekurze identifikátor zdrojového uzlu hrany (aktuálního uzlu). Po terminaci algoritmu pak otočené pořadí identifikátorů odpovídá Eulerovskému tahu.
Kód
/**
* @param u vychozi uzel - pokud graf obsahuje 2 uzly licheho stupne, tak libovolny z nich. Pokud obsahuje pouze uzly sudeho stupne, tak libovolny uzel.
* @param G graf
* @param tour zasobnik, ktery agreguje Eulerovsky tah
*/
findTour(u, G, tour)
for each edge e=(u,v) in Edges(G) do
remove e from Edges(G)
findTour(v, G, tour)
tour.push(u)