С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.89/18: Рейтинг темы: голосов - 18, средняя оценка - 4.89
0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
1

Поиск цикла указанной длины

29.05.2019, 22:13. Показов 3397. Ответов 8
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем привет! Столкнулся с проблемой в решении одной из задач
Есть Матрица Инцидентности с помощью которой задаётся ориентированный граф ( -1 -- начало ребра; 1 -- конец ребра )
Написал программу, которая проходит по вершинам графа в направлении рёбер, но как из этого сделать циклы не понимаю

В голове представляется поиск всех циклов в графе, а на вывод уже цикл определенной длины ( даже если их два одинаковых, вывести любой из )

Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <vector>
#include <string>
 
int nodes, sides, t;
 
//std::vector<bool> color(sides,false);
std::vector<std::vector<int>> graph;
std::vector<char> answer;
std::string names = "ABCDEFG";
std::vector <int> line;
 
void dfs_to_cycle(int v, std::vector<std::vector<int>>& graph, std::vector<bool>& color, std::vector <char>& answer) {
 
    //color[v] = true;
 
    for (int i = v; i < sides; i++) {
 
        for (int k = 0; k < nodes; k++) {
 
            if (graph[i][k] == -1 /*&& color[v] != true*/) {
 
                answer.push_back(names[k]);
 
                continue;
 
            }
 
            if (graph[i][k] == 1 && color[v] != true) {
 
                answer.push_back(names[k]);
 
                color[v] = true;
 
                v = k;
 
                if (color[v] == true) {
 
                    for (int k = 0; k < nodes; k++) {
 
                        if (graph[i][k] == -1) {
 
                            answer.push_back(names[k]);
 
                            continue;
 
                        }
                    }
 
                    return;
                }
                //dfs_to_cycle(v,graph,color,answer);
 
            }
 
        }
 
        dfs_to_cycle(v, graph, color, answer);
        return;
    }
 
}
 
int main() {
 
    std::cout << " Enter num of sides and num of nodes " << std::endl;
    std::cin >> sides >> nodes;
 
    std::vector<bool> color(nodes, false);
 
    for (int i = 0; i < sides; i++) {
 
        for (int k = 0; k < nodes; k++) {
 
            std::cin >> t;
            line.push_back(t);
 
        }
        graph.push_back(line);
        line.clear();
    }
 
    dfs_to_cycle(0, graph, color, answer);
 
    for (int i = 0; i < answer.size(); i++) {
 
        std::cout << answer[i];
 
    }
 
    return 0;
}
Прошу помочь, заранее спасибо!

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 ) в конце поменять местами нужно

Название: Безымянный.png
Просмотров: 65

Размер: 3.7 Кб
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
29.05.2019, 22:13
Ответы с готовыми решениями:

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

Поиск картинок в указанной директории. visual c++
Добрый день всем. в общем суть вопроса такая. Необходимо найти все картинки в каталоге который мы...

Подмножества указанной длины в множестве
Прошу помочь мне, задача состоит в том, чтобы вывести на экран все подмножества длиной k, множества...

Разбиение произвольного текста на строки указанной длины
Полное задание Вариант В22. Составить и отладить программу, реализующую разбиение произвольного...

8
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
29.05.2019, 22:55 2
Цитата Сообщение от N9wKa Посмотреть сообщение
Написал программу, которая проходит по вершинам графа в направлении рёбер, но как из этого сделать циклы не понимаю
При поиске пути помечай узлы, как посещённые. Если наткнулся на такую, значит петля.
0
0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
29.05.2019, 23:09  [ТС] 3
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
При поиске пути помечай узлы, как посещённые. Если наткнулся на такую, значит петля.
Специально для этого добавил vector <bool> color(nodes) , чтобы помечать, но проблема в том, что я не понимаю как сделать, чтобы программа могла понять, что вершина конечная и начальная должна быть одной и той же
Есть графы, где программа доходит до вершины, в которой она была и останавливается, хотя это не цикл
Например Название: Безымянный.png
Просмотров: 64

Размер: 2.6 Кб
Тут будет порядок 1-2-3-4-2
0
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
29.05.2019, 23:17 4
Цитата Сообщение от N9wKa Посмотреть сообщение
Специально для этого добавил vector <bool> color(nodes) , чтобы помечать, но проблема в том, что я не понимаю как сделать, чтобы программа могла понять, что вершина конечная и начальная должна быть одной и той же
Не надо вектор. Прямо в узлах графа добавь атрибут
Цитата Сообщение от N9wKa Посмотреть сообщение
Есть графы, где программа доходит до вершины, в которой она была и останавливается, хотя это не цикл
Цитата Сообщение от N9wKa Посмотреть сообщение
Тут будет порядок 1-2-3-4-2
А что такое тогда цикл?

Добавлено через 1 минуту
Цитата Сообщение от N9wKa Посмотреть сообщение
Есть графы, где программа доходит до вершины, в которой она была и останавливается, хотя это не цикл
Ты имеешь ввиду, что поиск пути прекращается?
0
0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
29.05.2019, 23:20  [ТС] 5
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
А что такое тогда цикл?
С одной вершины началось и с той же и закончилось
В прошлом примере цикл это 1-2-3-4-1

Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Не надо вектор. Прямо в узлах графа добавь атрибут
А есть еще варианты, кроме атрибутов?) Не умею их использовать
0
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
29.05.2019, 23:27 6
Ну да, похоже у тебя dfs_to_cycle кривая. Как минимум она должна возвращать bool и не выходить из рекурсии, пока не вернётся true - конечный узел найден

Добавлено через 2 минуты
Цитата Сообщение от N9wKa Посмотреть сообщение
А есть еще варианты, кроме атрибутов?) Не умею их использовать
Ладно, массив тоже нормально.

Добавлено через 4 минуты
Цитата Сообщение от N9wKa Посмотреть сообщение
С одной вершины началось и с той же и закончилось
В прошлом примере цикл это 1-2-3-4-1
Нет, 1-2-3-4-2 - это тоже цикл.
0
0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
29.05.2019, 23:28  [ТС] 7
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Нет, 1-2-3-4-2 - это тоже цикл.
Тогда мне нужен Ориентированный цикл
0
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
29.05.2019, 23:32 8
Цитата Сообщение от N9wKa Посмотреть сообщение
Тогда мне нужен Ориентированный цикл
У тебя ориентированный граф, там вроде других циклов не бывает.

Добавлено через 2 минуты
Тебе нужно, кроме рекурсии, ещё и запоминать путь, в списке например, и когда наткнёшься на петлю - узел, где уже был, просто пробегаешься по списку назад до этого узла и считаешь длину петли
1
0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
29.05.2019, 23:39  [ТС] 9
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Тебе нужно, кроме рекурсии, ещё и запоминать путь, в списке например, и когда наткнёшься на петлю - узел, где уже был, просто пробегаешься по списку назад до этого узла и считаешь длину петли
Спасибо за идею, буду пробовать!
0
29.05.2019, 23:39
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
29.05.2019, 23:39
Помогаю со студенческими работами здесь

В тексте слова заданной длины заменить указанной подстрокой
Задание: В тексте слова заданной длины заменить указанной подстрокой, длина которой может не...

В тексте слова заданной длины заменить указанной подстрокой
В тексте слова заданной длины заменить указанной подстрокой, длина которой может не совпадать с...

Реализовать поиск заданного файла в древе каталогов и поиск указанной информации в этом файле
Имеется много папок в каждой папке есть файл proc.txt, как можно по всем этим папкам пройтись и из...

Написать программу ввода текста и нахождения слова указанной длины
Разработать программу, которая вводит текст и находит в нем все слова указанной длины n (n...


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

Или воспользуйтесь поиском по форуму:
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
В контексте стремительного развития современных технологий особое внимание уделяется таким инструментам, как нейросети. Эти структуры, вдохновленные биологическими нейронными сетями, используются для. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru