 |
|
|
 
|
|
алгоритм Габова 
| warmonger_ |
|
|||
 Бывалый  Профиль Группа: Участник Сообщений: 155 Регистрация: 7.7.2007 Где: г. Киев Репутация: нет Всего: 3 |
Подскажите пожалуйста, где можно почитать про алгоритм Габова? или может кто-то объяснит?
--------------------
Make everything as simple as possible, but not simpler.Albert Einstein |
|||
|
||||
Загрузка ...
| JackYF |
|
|||
 полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: нет Всего: 162 |
гугл спрашивал? |
|||
|
||||
| warmonger_ |
|
||||
|
Бывалый Профиль Группа: Участник Сообщений: 155 Регистрация: 7.7.2007 Где: г. Киев Репутация: нет Всего: 3 |
да, но что-то он не очень хочет отвечать... может не правильно спрашиваю) в основном нахожу материал, где алгоритм представлен с математ. точки зрения. а мне главное прицип понять. --------------------
Make everything as simple as possible, but not simpler.Albert Einstein |
||||
|
|||||
| JackYF |
|
|||
|
полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: нет Всего: 162 |
гм. А что этот алгоритм должен делать?
|
|||
|
||||
| warmonger_ |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 155 Регистрация: 7.7.2007 Где: г. Киев Репутация: нет Всего: 3 |
вычислять сильные компоненты в ориентированном графе. тоесть если есть путь из вершины А в вершину В, то нужно узнать, есть ли путь из В в вершину А (сильная связность).
наскольно я понимаю) --------------------
Make everything as simple as possible, but not simpler.Albert Einstein |
|||
|
||||
| JackYF |
|
|||
|
полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: нет Всего: 162 |
||||
|
||||
| sentry |
|
|||
|
Code Monkey Профиль Группа: Участник Сообщений: 133 Регистрация: 29.1.2007 Где: Москва Репутация: нет Всего: 10 |
Скачай пятую часть Седжвика "Фундаментальные алгоритмы", там на с.869 есть описание алгоритма Габова и даже код к нему.
На пальцах объяснить довольно сложно... |
|||
|
||||
| warmonger_ |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 155 Регистрация: 7.7.2007 Где: г. Киев Репутация: нет Всего: 3 |
лутше бы на пальцах... я понял, что нужно совершать обратный поиск в глубину(рекурсивно), но зачем еще два стэка, и как определить, что компонента сильная? Это сообщение отредактировал(а) warmonger_ - 14.9.2007, 21:54 --------------------
Make everything as simple as possible, but not simpler.Albert Einstein |
|||
|
||||
| comp |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 61 Регистрация: 15.11.2006 Репутация: 1 Всего: 1 |
Вот мануал...
http://slil.ru/24926502 Добавлено через 8 минут и 4 секунды Упс, я думал, что тут идёт речь о нахождении макс. паросочетания, сорри, я не тот ман. запостил... |
|||
|
||||
| comp |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 61 Регистрация: 15.11.2006 Репутация: 1 Всего: 1 |
Ну а вообще, обычно все пользуются следующим алгоритмом, незнаю уж, кому он принадлежит...
1.Идём в глубину, кладём вершины в стэк 2.Переворачиваем граф // т.е. если было ребро A -> B, то после переворота станет B -> A 3.Опять идем в глубину с вершины, которая в вершине стэка. Помечаем вершины... все достижимые виршины - одна сильно связная компонента... ну и так в цикле для всех вершин, которые лежат в стэке. |
|||
|
||||
| warmonger_ |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 155 Регистрация: 7.7.2007 Где: г. Киев Репутация: нет Всего: 3 |
это вроде алг. Касорайа или как-то там.... но я уже разобрался с алг. Габова. если посидеть часиков 5 подряд, то можно понять) --------------------
Make everything as simple as possible, but not simpler.Albert Einstein |
|||
|
||||
| zver4ok |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 5 Регистрация: 20.11.2007 Репутация: нет Всего: нет |
А ни у кого нету реализации этого алгоритма? Никак не получается ((
|
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0800 ] [ Использовано запросов: 20 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |