0 / 0 / 0
Регистрация: 06.10.2018
Сообщений: 7
1

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

29.05.2019, 22:13. Показов 3122. Ответов 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
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.05.2019, 22:13
Ответы с готовыми решениями:

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

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

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

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

8
6579 / 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
6579 / 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
6579 / 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
6579 / 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.05.2019, 23:39
Помогаю со студенческими работами здесь

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru