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

C++

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

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

25.11.2016, 11:51. Просмотров 230. Ответов 1

Здравствуйте. Задача такова:
Есть граф кодовых пересечений ГКП (3,2,1) (на рисунке). Параметры n - длина кода, k - основание кода, r - мощность пересечения. На вход программе подается начальная и конечная вершина. На выходе должна получится кодовая запись каждого возможного пути от начальной вершины до конечной по отдельности с указанием длины пути. Кодовая запись формируется следующим образом (пример):
1. Определяем число символов в пересечении двух соседних кодовых комбинаций (n – r = 3 – 1 = 2).
2. Если существует непосредственный путь (путь длиной l = 1) из вершины 000 в вершину 010, то два последних символа кодовой последовательности 000 должны совпадать с двумя первыми символами кодовой последовательности 010. Если условие не выполняется, то такого пути не существует.
2. Выясняем, существует ли путь из узла 000 в узел 010, длина которого была бы равна 2. Для этого один последний символ кодовой комбинации 000 должен совпадать с одним первым символом кодовой комбинации 010. Если условие выполняется, то из узла 000 в узел 010 существует путь длиной l = 2. Для его определения составляем из номеров 000 и 010 последовательность 00010, совместив при этом совпадающие символы.
Нужно, чтобы программа выполняла подобное для любых введенных с клавиатуры начальной и конечой вершин. Граф задается из файла.
Каким образом это можно реализовать на с++? Пробовала через поиск в ширину/в глубину, получается не то, что надо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2016, 11:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск всех возможных путей в графе по отдельности (C++):

Обход всех путей в графе - C++ Builder
Помогите с алгоритмом поиска всех путей на графе.Обыскал весь инет робочего не нашол

Создание всех возможных комбинаций английского алфавита - C++ Builder
Подскажите пожалуйста код для создания всех возможных комбинаций английского алфавита. И чтобы эти комбинации выводились в Memo.

Поиск гамильтоновых циклов в графе - C++ Builder
Имеется программа. если нажимать СЛЕДУЮЩИЙ ШАГ то программа работает правильно и ищет гамильтоновый цикл. если же нажать на ДОБАВИТЬ...

поиск Эйлерова цикла в графе на c++ buider - C++ Builder
Здравствуйте.Не могли бы кто-нибудь помочь , и выложить исходник Эйлерова цикла на c++ builder.Реализовать интерфейс можно без чертежей и...

Переделать из консоли в VCL Forms (поиск оптимальных путей от точки А до точки Б) - C++ Builder
Ребята, помогите) Нужно запилить это в С++ билдер) В консоли без проблем) Однако в билдер, что бы на форме мы вводили все нужные...

Реализовать поиск в ширину в простом графе - Visual C++
Поиск в ширину--2 (вершины идентифицируются названиями) ограничение по времени на тест: 2 seconds ограничение по памяти на тест: 64...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
AngelWOmega
0 / 0 / 0
Регистрация: 25.11.2016
Сообщений: 2
25.11.2016, 12:10  [ТС] #2
Забыла рисунок:
0
Изображения
 
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2016, 12:10
Привет! Вот еще темы с ответами:

Нахождение всех возможных разрешений экрана - C++ WinAPI
Всем здрасьте , можно ли без всяких DirectX найти , какое разрешение на экране или какие возможно разрешение вообще?

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

Нахождение всех возможных путей - C++
дана матрица, нужно с 1,1(Start) обоити всеми возможными путями к А,А(Finish). здвигаться можно так если находимся в (х,у) : (х+1,у);...

Обход всех путей в графе - C++
Помогите с алгоритмом поиска всех путей на графе.Обыскал весь инет робочего не нашол


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

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

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