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

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

Восстановить пароль Регистрация
 
AngelWOmega
0 / 0 / 0
Регистрация: 25.11.2016
Сообщений: 2
25.11.2016, 11:51     Поиск всех возможных путей в графе по отдельности #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, совместив при этом совпадающие символы.
Нужно, чтобы программа выполняла подобное для любых введенных с клавиатуры начальной и конечой вершин. Граф задается из файла.
Каким образом это можно реализовать на с++? Пробовала через поиск в ширину/в глубину, получается не то, что надо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2016, 11:51     Поиск всех возможных путей в графе по отдельности
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AngelWOmega
0 / 0 / 0
Регистрация: 25.11.2016
Сообщений: 2
25.11.2016, 12:10  [ТС]     Поиск всех возможных путей в графе по отдельности #2
Забыла рисунок:
Изображения
 
Yandex
Объявления
25.11.2016, 12:10     Поиск всех возможных путей в графе по отдельности
Ответ Создать тему

Метки
С++для начинающих
Опции темы

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