Toto je starší verze dokumentu!

Jedná se o úlohu hledání Eulerovského tahu v zadaném grafu. Nejdříve je potřeba ověřit zda-li je graf opravdu Eulerovský.

Potřebné info naleznete na stránce: http://www.algoritmy.net/article/33838/Cycle-finding

Pro reprezentaci dat jsou asi nejlepší spojové seznamy. Pak má algoritmus opravdu lineární asymptotickou složitost.

By stradja3: Udělal jsem to pomocí té rekurze s tím, že když je to orientovaný graf tak si neustále aktualizuju vstupní a výstupní stupně pro každý uzel, abych náhodou předčasně nevlezl do koncového uzlu (který má výstupní stupeň 0). A funguje to. Problém je, že mi to počítá pomalu - pouze 5/10. Jakým způsobem se to udělá přes ty spojové seznamy?

By milanec: Já mám vrchol - ten má nějaké číslo a linkedList čísel vrcholů, do kterých má orientovanout hranu (tzn. vedou-li z vrcholu 2 do vrcholu dvě hrany do 4, jedna do 1 a jedna do 0, má linked list hodnoty - 4,4,1,0. Find mám stejný jako v přednáškách. Namísto push(new edge(from,to)) mám push(new int[]{from,to})… když jsem tam měl objekt, tak jsem těžce nestíhal. — Milan Černil 2013/10/13 23:17