0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
|
||||||
1 | ||||||
Поиск цикла указанной длины29.05.2019, 22:13. Показов 3397. Ответов 8
Метки нет (Все метки)
Всем привет! Столкнулся с проблемой в решении одной из задач
Есть Матрица Инцидентности с помощью которой задаётся ориентированный граф ( -1 -- начало ребра; 1 -- конец ребра ) Написал программу, которая проходит по вершинам графа в направлении рёбер, но как из этого сделать циклы не понимаю В голове представляется поиск всех циклов в графе, а на вывод уже цикл определенной длины ( даже если их два одинаковых, вывести любой из ) Вот код:
P.S. Пример МИ: A B C D E -1 1 0 0 0 ( 1 ребро ) 0 -1 1 0 0 ( 2 ребро ) 0 0 -1 1 0 0 0 -1 0 1 0 1 0 0 -1 ( 5 ребро ) Вывод: ABBCCDCEBE ( B и E ) в конце поменять местами нужно
0
|
29.05.2019, 22:13 | |
Ответы с готовыми решениями:
8
поиск Эйлерова цикла в графе на c++ buider Поиск картинок в указанной директории. visual c++ Подмножества указанной длины в множестве Разбиение произвольного текста на строки указанной длины |
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
|
|
29.05.2019, 22:55 | 2 |
При поиске пути помечай узлы, как посещённые. Если наткнулся на такую, значит петля.
0
|
0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
|
|
29.05.2019, 23:09 [ТС] | 3 |
Специально для этого добавил vector <bool> color(nodes) , чтобы помечать, но проблема в том, что я не понимаю как сделать, чтобы программа могла понять, что вершина конечная и начальная должна быть одной и той же
Есть графы, где программа доходит до вершины, в которой она была и останавливается, хотя это не цикл Например Тут будет порядок 1-2-3-4-2
0
|
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
|
|
29.05.2019, 23:17 | 4 |
Не надо вектор. Прямо в узлах графа добавь атрибут
А что такое тогда цикл? Добавлено через 1 минуту Ты имеешь ввиду, что поиск пути прекращается?
0
|
0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
|
|
29.05.2019, 23:20 [ТС] | 5 |
С одной вершины началось и с той же и закончилось
В прошлом примере цикл это 1-2-3-4-1 А есть еще варианты, кроме атрибутов?) Не умею их использовать
0
|
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
|
|
29.05.2019, 23:27 | 6 |
Ну да, похоже у тебя dfs_to_cycle кривая. Как минимум она должна возвращать bool и не выходить из рекурсии, пока не вернётся true - конечный узел найден
Добавлено через 2 минуты Ладно, массив тоже нормально. Добавлено через 4 минуты Нет, 1-2-3-4-2 - это тоже цикл.
0
|
0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
|
|
29.05.2019, 23:28 [ТС] | 7 |
0
|
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
|
|
29.05.2019, 23:32 | 8 |
У тебя ориентированный граф, там вроде других циклов не бывает.
Добавлено через 2 минуты Тебе нужно, кроме рекурсии, ещё и запоминать путь, в списке например, и когда наткнёшься на петлю - узел, где уже был, просто пробегаешься по списку назад до этого узла и считаешь длину петли
1
|
0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
|
|
29.05.2019, 23:39 [ТС] | 9 |
0
|
29.05.2019, 23:39 | |
29.05.2019, 23:39 | |
Помогаю со студенческими работами здесь
9
В тексте слова заданной длины заменить указанной подстрокой В тексте слова заданной длины заменить указанной подстрокой Реализовать поиск заданного файла в древе каталогов и поиск указанной информации в этом файле Написать программу ввода текста и нахождения слова указанной длины Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи | |||||
Как написать микросервис на Go/Golang с Kafka и GitHub CI/CD
InfoMaster 14.01.2025
Определение микросервиса, преимущества использования Go/ Golang
Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .
|
Как написать микросервис с нуля на C# с RabbitMQ, CQRS и CI/CD
InfoMaster 14.01.2025
В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .
|
Как создать интернет-магазин на PHP и JavaScript
InfoMaster 14.01.2025
В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .
|
Как написать Тетрис на Ассемблере
InfoMaster 14.01.2025
Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .
|
Как создать игру "Танчики" на Unity3d и C#
InfoMaster 14.01.2025
Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .
|
Организую платный онлайн микро-курс по доработке Android-клиента Telegram
_Ivana 14.01.2025
Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента!
4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве).
Первое вводное занятие. . .
|
Как создать приложение для фитнеса для iOS/iPhone на Kotlin
InfoMaster 14.01.2025
Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .
|
Как создать приложение магазина для iOS/iPhone на Swift
InfoMaster 14.01.2025
Введение в разработку iOS-приложений
Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .
|
Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь!
Hrethgir 13.01.2025
По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта в Gowin Eda. Восьмибитный счётчик из сумматора+ генератор сигнала. . .
|
UserScript для подсветки кнопок языков программирования в зависимости от текущего раздела
volvo 13.01.2025
В результате работы этого скрипта подсвечиваются нужные кнопки не только в форме быстрого ответа, но и при редактировании сообщения:
/ / ==UserScript==
/ / @name CF_DefaultLangSelect
/ / . . .
|
Введение в модели и алгоритмы машинного обучения
InfoMaster 12.01.2025
Машинное обучение представляет собой одну из наиболее динамично развивающихся областей искусственного интеллекта, которая фокусируется на разработке алгоритмов и методов, позволяющих компьютерам. . .
|
Как на Python создать нейросеть для решения задач
InfoMaster 12.01.2025
В контексте стремительного развития современных технологий особое внимание уделяется таким инструментам, как нейросети. Эти структуры, вдохновленные биологическими нейронными сетями, используются для. . .
|