Цитата(warmonger_ @ 14.9.2007, 08:53  ) |
| где можно почитать про алгоритм Габова? |
гугл спрашивал?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > алгоритм Габова |
| Автор: warmonger_ 14.9.2007, 08:53 |
| Подскажите пожалуйста, где можно почитать про алгоритм Габова? или может кто-то объяснит? |
| Автор: JackYF 14.9.2007, 14:38 | ||
гугл спрашивал? |
| Автор: warmonger_ 14.9.2007, 16:46 | ||||
да, но что-то он не очень хочет отвечать... может не правильно спрашиваю) в основном нахожу материал, где алгоритм представлен с математ. точки зрения. а мне главное прицип понять. |
| Автор: JackYF 14.9.2007, 17:46 |
| гм. А что этот алгоритм должен делать? |
| Автор: warmonger_ 14.9.2007, 17:58 |
| вычислять сильные компоненты в ориентированном графе. тоесть если есть путь из вершины А в вершину В, то нужно узнать, есть ли путь из В в вершину А (сильная связность). наскольно я понимаю) |
| Автор: JackYF 14.9.2007, 20:38 |
ну тогда http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%B4%D0%BE%D1%81%D1%82%D0%B8%D0%B6%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8, по-моему неплохо описано  |
| Автор: sentry 14.9.2007, 21:29 |
| Скачай пятую часть Седжвика "Фундаментальные алгоритмы", там на с.869 есть описание алгоритма Габова и даже код к нему. На пальцах объяснить довольно сложно... |
| Автор: warmonger_ 14.9.2007, 21:34 | ||
лутше бы на пальцах... я понял, что нужно совершать обратный поиск в глубину(рекурсивно), но зачем еще два стэка, и как определить, что компонента сильная? |
| Автор: comp 2.10.2007, 17:08 |
| Вот мануал... http://slil.ru/24926502 Добавлено через 8 минут и 4 секунды Упс, я думал, что тут идёт речь о нахождении макс. паросочетания, сорри, я не тот ман. запостил... |
| Автор: comp 3.10.2007, 03:11 |
| Ну а вообще, обычно все пользуются следующим алгоритмом, незнаю уж, кому он принадлежит... 1.Идём в глубину, кладём вершины в стэк 2.Переворачиваем граф // т.е. если было ребро A -> B, то после переворота станет B -> A 3.Опять идем в глубину с вершины, которая в вершине стэка. Помечаем вершины... все достижимые виршины - одна сильно связная компонента... ну и так в цикле для всех вершин, которые лежат в стэке. |
| Автор: warmonger_ 3.10.2007, 18:23 | ||
это вроде алг. Касорайа или как-то там.... но я уже разобрался с алг. Габова. если посидеть часиков 5 подряд, то можно понять) |
| Автор: zver4ok 7.1.2008, 15:33 |
| А ни у кого нету реализации этого алгоритма? Никак не получается (( |