Eulerův graf
Eulerův graf

Cycle finding je algoritmus s asymptotickou složitostí O(\\vert U \\vert + \\vert H \\vert), 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)  







Doporučujeme