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

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

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

Графы. Нужно составить алгоритм - C++

22.09.2013, 07:50. Просмотров 488. Ответов 3
Метки нет (Все метки)

Помогите алгоритмизировать задачу! Нужно написать программу способную определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не проезжать никакой дороги более одного раза.
Заранее спасибо =)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.09.2013, 07:50     Графы. Нужно составить алгоритм
Посмотрите здесь:

C++ Составить алгоритм и программу
C++ Нужно Составить алгоритм расчета по двум формулам
Нужно Составить алгоритм расчета по двум формулам C++
C++ составить алгоритм!!!
Составить алгоритм C++
Нужно составить алгоритм задачи! C++
Нужно Составить алгоритм расчета по двум формулам C++
Составить алгоритм C++
C++ Графы. Алгоритм Прима
Составить линейный алгоритм C++
C++ В магазине работает 5 человек, нужно составить график их работы, нужно что бы каждый день работало по 3 чел
C++ Графы. Алгоритм

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
D3fend0r
17 / 17 / 1
Регистрация: 14.09.2013
Сообщений: 37
22.09.2013, 10:17     Графы. Нужно составить алгоритм #2
Цитата Сообщение от Gennadiusisus Посмотреть сообщение
Помогите алгоритмизировать задачу! Нужно написать программу способную определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не проезжать никакой дороги более одного раза.
Заранее спасибо =)
Попробуйте использовать алгоритм поиска в ширину, сначала из вершины А, а потом из вершины С. Если алгоритм находит путь из вершины А в вершину С и из вершины С в вершину В, значит существует путь из А в В проходящий через С.
Gennadiusisus
0 / 0 / 0
Регистрация: 26.12.2012
Сообщений: 8
23.09.2013, 16:13  [ТС]     Графы. Нужно составить алгоритм #3
Цитата Сообщение от D3fend0r Посмотреть сообщение
Попробуйте использовать алгоритм поиска в ширину, сначала из вершины А, а потом из вершины С. Если алгоритм находит путь из вершины А в вершину С и из вершины С в вершину В, значит существует путь из А в В проходящий через С.
Думал об этом, но этот алгоритм не может учесть то, что из "А" в "С" можно прийти разными путями и возможно пройдя по одному пути, мы не сможем прийти в "В"...не совсем универсально получается..=(
D3fend0r
17 / 17 / 1
Регистрация: 14.09.2013
Сообщений: 37
24.09.2013, 01:46     Графы. Нужно составить алгоритм #4
Цитата Сообщение от Gennadiusisus Посмотреть сообщение
Думал об этом, но этот алгоритм не может учесть то, что из "А" в "С" можно прийти разными путями и возможно пройдя по одному пути, мы не сможем прийти в "В"...не совсем универсально получается..=(
Да , не учел этого. Может быть тогда найти путь из А в С, пометить ребра через которые прошли и для этого пути проверить все возможные пути из С в В не проходящие через помеченные ребра. Если не найдем путь перейдем к следующему варианту пути из А в С и опять проверим если путь из С в В. Продолжаем пока не найдем путь удовлетворяющий условию или не проверим все варианты. Алгоритм по времени получается очень затратным, возможно можно ускорить его работу, скажем сохранять вершины или ребра которые не приведут к нужной вершине.
Yandex
Объявления
24.09.2013, 01:46     Графы. Нужно составить алгоритм
Ответ Создать тему
Опции темы

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