|
Тема |
Re: Critical Path [re: Alykard] |
|
Автор |
Viper X (just a snake...) |
|
Публикувано | 07.05.09 18:37 |
|
|
код няма да ти пиша, щот надали и ще успея да ти го напиша на Ц++ сега :)
иначе примерен алгоритъм: ацикличен неориентиран граф всъщност е дърво. избираш си произволен връх за корен и почваш да правиш ДФС (обхождане в дълбочина). Най-дългия път тръгва от някое листо на това дърво, изкачва се нагоре до някой връх (евентуално до корена, но не задължително) и започва да се спуска обратно към някое друго листо.
При ДФС-то при връщането назад за всеки връх отбелязваш височината на всяко от неговите поддървета (рекурсивно, започвайки от долу на горе). След като си обходил всички поддървета за даден връх - можеш да намериш най-дългия път за това поддърво, който минава през този връх - той е равен на сбора от височините на двете най-високи поддървета на върха. Така с линейна сложност ще си направиш ДФСто на цялото дърво, обаче ще си намерил и върха, през който минава търсения от теб най-дълъг път от първоначалния ацикличен неориентиран граф.
Дано ме разбираш, защото аз като си чета пак написаното не съм сигурен че се разбирам :) от чертежче се вижда веднага какво имам предвид, ама не ми се губят 10 минути да правя чертеж в компютърен формат, и ако съвсем не ме разбираш и никъде още не си намерил готово решение и искаш да си пишеш по предложения от мен алгоритъм - кажи да снимам рисунката с фотоапарата и да я кача :)
-------------
КЗЛ
|
| |
|
|
|