 |
|
|
 
|
|
все пути между двумя вершинами 
| pablo |
|
|||
 Опытный  Профиль Группа: Участник Сообщений: 320 Регистрация: 12.2.2005 Где: Вильнюс, Литва Репутация: нет Всего: 6 |
Подскажите пожалуйста может есть какой нить алгоритм для нахождения всех путей между 2-мя вершинами в не ориентированном графе ?
Заранее благодарен. -------------------- Первый блин всегда похож на сферу, иногда бывает и куб. |
|||
|
||||
Загрузка ...
| MBo |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 234 Регистрация: 10.6.2002 Репутация: 5 Всего: 18 |
запустить рекурсивный поиск в ширину, однако, в отличие от обычного случая, запоминать помеченность вершин не глобально, а в каждой рекурсивной ветви (чтобы избавиться от зацикливания)
|
|||
|
||||
| esperant0 |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
Да, обычный перебор, то что вам нужно.
-------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
| g1pn0z |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 29 Регистрация: 29.4.2007 Репутация: нет Всего: нет |
вот тоже думаю над графами, а все таки значит я не один такой,
смотрите мою тему http://forum.vingrad.ru/forum/topic-148770...рта-города.html там как раз задача с графами) |
|||
|
||||
| esperant0 |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
а вам нужно динамическое программирование
-------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
| pablo |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 320 Регистрация: 12.2.2005 Где: Вильнюс, Литва Репутация: нет Всего: 6 |
Задача решается очень просто. необходимо провести поиск в глубину сохраняя в стеке посещенные вершины. Так обходим весь гряф, и имеем все пути. задача решена, вопросс закрыт.
-------------------- Первый блин всегда похож на сферу, иногда бывает и куб. |
|||
|
||||
| goodspeed13 |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 1 Регистрация: 30.11.2011 Репутация: нет Всего: нет |
Не очень понятно, не могли бы поподробнее... Я сделал поиск в глубину в графе, он просто обходит все вершины, а как найти все пути между двумя вершинами не понятно... Вот код моей функции обхода в глубину: [code=cpp] void Graph::DSearch(int Versh1) { int i; visited[Versh1] = true; std::cout<<Versh1<<std::endl; for (i=0; i<SizeoftheGraph;i++) { if ((smezh[Versh1][i]==1) && (visited[i]==false)) { DSearch(i); } } } |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.1301 ] [ Использовано запросов: 20 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |