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

By stradja3: A jak řešíš to, abys předčasně nevlezl do koncového uzlu, který má výstupní stupeň v danou chvíli 0 (pokud měl třeba 1 a už jsme ho jednou prošli)? Já to udělal podle tebe - mám u každého uzlu seznam následovníků a ty procházím do hloubky. Ale udržuju si informaci o výstupním stupni toho koncového uzlu. Když na něj narazím a ten stupeň je 0, tak ho v tom seznamu následovníků přesunu úplně na konec. Tím zaručím, že do něj vlezu až na závěr. Vypadá to jednoduše a jasně, jenže mi to u poloviny testovacích dat na webu hází špatné řešení nebo segmentation fault, takže tam mám nějakou chybu a nemůžu na ni přijít..

By milanec: Máš teda 2 situace

• Buď sudé stupně u všeho - je jedno kde začneš
• 2 s lichým - musíš začít u toho, který má více výstupních vrcholů

Já to dělám tak, že při načítání u všech uzlů mám field stupeň. Pokud do něj vede hrana, přidám jedničku, pokud vychází hrana, odeberu 1. Tím pádem najdeš výchozí tím, že bude mít stupeň -1. Takže si pak projedeš všechny vrcholy a tím, že najdeš ten s -1, tak víš, že začneš prohledávat cestu od něj. Udržuji si i nějaký count, kolik jsem jich našel - když jich najdu víc, tak nemá řešení samozřejmě :) Pokud takový nemám, tak jedu klasicky odkud chci. A do toho druhého lichého to vleze samo :) — Milan Černil 2013/10/15 00:12