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

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

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

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

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

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

Нужно составить алгоритм задачи! - C++
Дан двумерный массив m на n, заполненный случайным образом. Вставить между средними строками первую. Добавлено через 42 минуты В...

Нужно Составить алгоритм расчета по двум формулам - C++
Всем привет! Нужно написать код что бы пользователь мог ввести число переменной и программа всё должна посчитать и выдать результат Z1...

Нужно Составить алгоритм расчета по двум формулам - C++
Всем привет! Нужно написать код что бы пользователь мог ввести число переменной и программа всё должна посчитать и выдать результат Z1...

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

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

Графы. Алгоритм Прима - 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 Посмотреть сообщение
Думал об этом, но этот алгоритм не может учесть то, что из "А" в "С" можно прийти разными путями и возможно пройдя по одному пути, мы не сможем прийти в "В"...не совсем универсально получается..=(
Да , не учел этого. Может быть тогда найти путь из А в С, пометить ребра через которые прошли и для этого пути проверить все возможные пути из С в В не проходящие через помеченные ребра. Если не найдем путь перейдем к следующему варианту пути из А в С и опять проверим если путь из С в В. Продолжаем пока не найдем путь удовлетворяющий условию или не проверим все варианты. Алгоритм по времени получается очень затратным, возможно можно ускорить его работу, скажем сохранять вершины или ребра которые не приведут к нужной вершине.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2013, 01:46
Привет! Вот еще темы с ответами:

Графы, алгоритм Диница (реализовать граф списком смежности) - C++
У меня есть готовая программа по алгоритму Диница, но граф в матричном представлении. Очень нужно чтобы кто-нибудь помог реализовать граф...

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

Составить алгоритм - C++
Задана окружность с центром в точке О(x0,y0) и радиусом R0 и прямая y=ax+b. Определить, пересекаются ли прямая и окружность. При...

Составить алгоритм - C++
1. Составить алгоритм подсчета количества способов, которыми можно разменять рубль медными монетами(достоинством 1,2,3,4,5 копеек).


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
24.09.2013, 01:46
Ответ Создать тему
Опции темы

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