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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Nidwest
0 / 0 / 0
Регистрация: 05.08.2014
Сообщений: 7
#1

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

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

Всем привет.

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

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

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

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

Поиск отрицательного цикла (контура) в графе - C++
Всем привет! Помоги пожалуйста с программой! :-mass), затем я её модифицирую: for (int i = 0; i < n; ++i) for (int j = 0; j <...

Использование цикла do ( программа высчитывает вес, исходя из заданной длины и диаметра арматуры) - C++
Данная программа высчитывает вес, исходя из заданной длины и диаметра арматуры. Диаметр арматуры расположен в промежутке четных чисел от 6...

Поиск слова заданной длины из текстового файла - C++
Доброго времени суток всем) Помогите написать код. Надо вывести на экран все слова из текстового файла заданной длины (задается в консоли)...

Нахождение отрицательного цикла в графе и вывод цикла - C++
Вот программа по нахождению отрицательного цикла в графе и вывод цикла void Floyd(int GR, int parents , int V) { int checking; int...

Удаление цикла в ориентированном графе - C++
Помогите реализовать такой вот алгоритм: Задан ориентированный граф. Необходимо найти и удалить из него все циклы. Пример графа: 1 2 ...

Поиск циклов в графе. Поиск центра взвешенного графа - C++
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.11.2014, 20:51
Привет! Вот еще темы с ответами:

Сформировать предложение из слов заданной длины, в которых нет перевернутой заданной подстроки, но есть сама - C++
Дан массив слов и подстрока. Сформировать предложение из слов заданной длины, в которых нет перевернутой заданной подстроки, но есть сама...

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

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной - C++
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов. Заданны такие...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru