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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Ошибка памяти при выполнении, при компиляции не выводит ошибки http://www.cyberforum.ru/cpp-beginners/thread1302420.html
ПОмогите плс программа вводит строку символов до точки, а после вычисляет процент согласных в этой строке и выводит их в обратном порядке. Но суть в том что какая-то проблема с памятью в первой части...
C++ Как создать блок-схему? Возможно есть какая то программа или сервис где автоматом рисуется? блок схема http://www.cyberforum.ru/cpp-beginners/thread1302373.html
Упорядочить строки матрицы по убыванию сумм элементов строк C++
Пожалуйста помогите сделать так, чтобы программа работала так, как требуется: Дана матрица n*m. Упорядочить (переставить) строки матрицы по убыванию сумм элементов строк. include <iostream>...
Реализовать три конструктора. Перегрузить функции ввода/вывода, как дружественные функции C++
Реализовать три конструктора: без аргументов, копирования и инициализации. Перегрузить функции ввода/вывода как дружественные функции. Задание было: определить входит ли значение в интервал....
C++ Массивы структур и массивы строк http://www.cyberforum.ru/cpp-beginners/thread1302347.html
Ребят, помогите. Не получается ничего. структура: struct student { char*name; int kurs; float rating }; Критерий для поиска в массиве структур:
C++ Перегрузка функций Задача такая: перегрузить * так чтобы время умножалось на число, и так чтобы число умножалось на время. Не могу понять как реализовать второй пункт. Помогите люди добрые. P.S. Как сделать... подробнее

Показать сообщение отдельно
Nidwest
0 / 0 / 0
Регистрация: 05.08.2014
Сообщений: 7

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

16.11.2014, 20:51. Просмотров 489. Ответов 0
Метки (Все метки)

Всем привет.

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

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

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

Проверял на бумаге, находятся не все циклы. Какой лучше использовать алгоритм для решения такой задачи? Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru