Форум программистов, компьютерный форум CyberForum.ru

Поиск цикла заданной длины в графе - C++

Восстановить пароль Регистрация
 
Nidwest
0 / 0 / 0
Регистрация: 05.08.2014
Сообщений: 7
16.11.2014, 20:51     Поиск цикла заданной длины в графе #1
Всем привет.

Есть задача: дана система двусторонних дорог между городами. Необходимо найти какой-либо замкнутый путь заданной длины (в моем случае не более 100 км), проходящий по каждой дороге в этом пути ровно один раз.

Я так понял, что задача сводится к поиску цикла заданной длины в неориентированном графе. Пытался использовать такой алгоритм, который нашел на этом форуме:

Применяем поиск в глубину. Если мы нашли смежную вершину, которая уже была обработана, но при этом это не вершина из которой мы пришли в последнюю обработанную, то мы нашли цикл. Затем производим проверку на расстояние. Если проверка пройдена, то выходим из поиска, иначе удаляем последнюю вершину и продолжаем поиск.

Проверял на бумаге, находятся не все циклы. Какой лучше использовать алгоритм для решения такой задачи? Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.11.2014, 20:51     Поиск цикла заданной длины в графе
Посмотрите здесь:

Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). C++
C++ Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
C++ Удаление цикла в ориентированном графе
Поиск на графе C++
Использование цикла do ( программа высчитывает вес, исходя из заданной длины и диаметра арматуры) C++
Поиск циклов в графе. Поиск центра взвешенного графа C++
C++ Поиск отрицательного цикла (контура) в графе
C++ Нахождение отрицательного цикла в графе и вывод цикла

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 16:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru