Critical Path

Здравейте,някой може ли да ви предложи читав алгоритъм ,на С++,за намиране на възможно най-дългия път в АЦИКЛИЧЕН,НЕОРИЕНТИРАН граф.Но наистина читам т.е. с възможно най-ниска сложност.

задачи като тая не се ли даваха за пример за липса на читави решения?




NE SUTOR ULTRA CREPIDAM

код няма да ти пиша, щот надали и ще успея да ти го напиша на Ц++ сега :)

иначе примерен алгоритъм: ацикличен неориентиран граф всъщност е дърво. избираш си произволен връх за корен и почваш да правиш ДФС (обхождане в дълбочина). Най-дългия път тръгва от някое листо на това дърво, изкачва се нагоре до някой връх (евентуално до корена, но не задължително) и започва да се спуска обратно към някое друго листо.

При ДФС-то при връщането назад за всеки връх отбелязваш височината на всяко от неговите поддървета (рекурсивно, започвайки от долу на горе). След като си обходил всички поддървета за даден връх - можеш да намериш най-дългия път за това поддърво, който минава през този връх - той е равен на сбора от височините на двете най-високи поддървета на върха. Така с линейна сложност ще си направиш ДФСто на цялото дърво, обаче ще си намерил и върха, през който минава търсения от теб най-дълъг път от първоначалния ацикличен неориентиран граф.

Дано ме разбираш, защото аз като си чета пак написаното не съм сигурен че се разбирам :) от чертежче се вижда веднага какво имам предвид, ама не ми се губят 10 минути да правя чертеж в компютърен формат, и ако съвсем не ме разбираш и никъде още не си намерил готово решение и искаш да си пишеш по предложения от мен алгоритъм - кажи да снимам рисунката с фотоапарата и да я кача :)

-------------
КЗЛ