| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > все пути между двумя вершинами |
| Автор: pablo 25.4.2007, 09:07 |
| Подскажите пожалуйста может есть какой нить алгоритм для нахождения всех путей между 2-мя вершинами в не ориентированном графе ? Заранее благодарен. |
| Автор: MBo 25.4.2007, 09:28 |
| запустить рекурсивный поиск в ширину, однако, в отличие от обычного случая, запоминать помеченность вершин не глобально, а в каждой рекурсивной ветви (чтобы избавиться от зацикливания) |
| Автор: esperant0 25.4.2007, 19:54 |
| Да, обычный перебор, то что вам нужно. |
| Автор: g1pn0z 1.5.2007, 21:44 |
| вот тоже думаю над графами, а все таки значит я не один такой, смотрите мою тему http://forum.vingrad.ru/forum/topic-148770/kw-карта-города.html там как раз задача с графами) |
| Автор: esperant0 1.5.2007, 22:53 |
| а вам нужно динамическое программирование |
| Автор: pablo 3.5.2007, 19:08 |
| Задача решается очень просто. необходимо провести поиск в глубину сохраняя в стеке посещенные вершины. Так обходим весь гряф, и имеем все пути. задача решена, вопросс закрыт. |
| Автор: goodspeed13 30.11.2011, 21:17 | ||
Не очень понятно, не могли бы поподробнее... Я сделал поиск в глубину в графе, он просто обходит все вершины, а как найти все пути между двумя вершинами не понятно... Вот код моей функции обхода в глубину: [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); } } } |