Клубове Дир.бг
powered by diri.bg
търси в Клубове diri.bg Разширено търсене

Вход
Име
Парола

Клубове
Dir.bg
Взаимопомощ
Горещи теми
Компютри и Интернет
Контакти
Култура и изкуство
Мнения
Наука
Политика, Свят
Спорт
Техника
Градове
Религия и мистика
Фен клубове
Хоби, Развлечения
Общества
Я, архивите са живи
Клубове Дирене Регистрация Кой е тук Въпроси Списък Купувам / Продавам 11:36 28.09.20 
Клубове/ Компютри и Интернет / Програмисти Пълен преглед*
Информация за клуба
Тема Re: Critical Path [re: Alykard]
Автор Viper X (just a snake...)
Публикувано07.05.09 18:37  



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

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

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

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

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


Цялата тема
ТемаАвторПубликувано
* Critical Path Alykard   05.05.09 14:01
. * Re: Critical Path zaphod   06.05.09 08:25
. * Re: Critical Path Viper X   07.05.09 18:37
Клуб :  


Clubs.dir.bg е форум за дискусии. Dir.bg не носи отговорност за съдържанието и достоверността на публикуваните в дискусиите материали.

Никаква част от съдържанието на тази страница не може да бъде репродуцирана, записвана или предавана под каквато и да е форма или по какъвто и да е повод без писменото съгласие на Dir.bg
За Забележки, коментари и предложения ползвайте формата за Обратна връзка | Мобилна версия | Потребителско споразумение
© 2006-2020 Dir.bg Всички права запазени.