Форум программистов, компьютерный форум 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> using namespace std; int main() { int i,n,m,k, a ,j,b,t,r,sum; cout<<""; cin>>n; cin>>m;
Реализовать три конструктора. Перегрузить функции ввода/вывода, как дружественные функции C++
Реализовать три конструктора: без аргументов, копирования и инициализации. Перегрузить функции ввода/вывода как дружественные функции. Задание было: определить входит ли значение в интервал. #include <iostream> using namespace std; class Field { private: float first; float second; public:
C++ Массивы структур и массивы строк http://www.cyberforum.ru/cpp-beginners/thread1302347.html
Ребят, помогите. Не получается ничего. структура: struct student { char*name; int kurs; float rating }; Критерий для поиска в массиве структур:
C++ Перегрузка функций Задача такая: перегрузить * так чтобы время умножалось на число, и так чтобы число умножалось на время. Не могу понять как реализовать второй пункт. Помогите люди добрые. P.S. Как сделать нормальный заголовок темы на этом сайте?) #include "stdafx.h" #include <iostream> #include <iomanip> #include <locale.h> using namespace std; class CTime { private: подробнее

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

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

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

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

Проверял на бумаге, находятся не все циклы. Какой лучше использовать алгоритм для решения такой задачи? Заранее спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 19:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru