Поиск простых циклов в ориентированном графе

@RJEKICH · Регистрация: 16.11.2017

Author24 — интернет-сервис помощи студентам

Есть ориентированный граф(задан списком смежности, или матрицей смежности, не критично), необходимо найти простые циклы, точнее их длину. Выводить циклы нет необходимости, нужна только длина простых циклов.
Понимаю, что задача NP-сложная, но не совсем пойму, как корректно организовать поиск в глубину, пробовал удалять последнее ребро в пути, но это не корректно. А если не удалять, то программа не находит больше одного цикла.
Даже идейные ответы принимаются, я в тупике.
Длины циклов необходимы для определения существования ядра в графе.

@LegionK · 21.02.2021, 21:57

А вы гуглить пробовали?

@RJEKICH · 21.02.2021, 22:13 **[ТС]**

Да, пробовал. Нет ничего конкретного, что помогло бы. Всё найденные алгоритмы ищут или 1 цикл, или не работают.

@LegionK · 21.02.2021, 22:19

Даже всё отсюда? Всякие dfs, какие-то джонсоны

Кликните здесь для просмотра всего текста

https://qastack.ru/programming/546655/finding-all-cycles-in-a-directed-graph

@RJEKICH · 21.02.2021, 23:09 **[ТС]**

Джонсон же кратчайшие пути ищет. За ссылку спасибо, посмотрю. Странно, что на этот сайт не натыкался

@LegionK · 21.02.2021, 23:25

А очевидный перебор пробовали или он работать не будет? Или слишком медленно?

Типо такого :

void func(vector<int>path){

int beg = path[0];
int last = path.back();

перебираем все связанные с last вершины, текущая - num
если num = beg то нашли цикл, выводим path
если num нету в path, то заводим vector<int>t = path; t.push_back(num); func(t);

}

int main()

для всех вершин i запускаем func({i});

Вроде бы он должен перебрать все простые пути вообще, если я правильно понимаю, ну и определить из них циклы.

@RJEKICH · 22.02.2021, 08:05 **[ТС]**

Да, это переборная задача, я просто не совсем понимал, как корректно перебор организовать

@RJEKICH 0 / 0 / 0 Регистрация: 16.11.2017 Сообщений: 22
		1
	Поиск простых циклов в ориентированном графе 21.02.2021, 21:03. Показов 2924. Ответов 6 Метки dfs, граф, поиск в глубину (Все метки) Есть ориентированный граф(задан списком смежности, или матрицей смежности, не критично), необходимо найти простые циклы, точнее их длину. Выводить циклы нет необходимости, нужна только длина простых циклов. Понимаю, что задача NP-сложная, но не совсем пойму, как корректно организовать поиск в глубину, пробовал удалять последнее ребро в пути, но это не корректно. А если не удалять, то программа не находит больше одного цикла. Даже идейные ответы принимаются, я в тупике. Длины циклов необходимы для определения существования ядра в графе. 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	21.02.2021, 21:57	2
	А вы гуглить пробовали? 0

@RJEKICH 0 / 0 / 0 Регистрация: 16.11.2017 Сообщений: 22
	21.02.2021, 22:13 [ТС]	3
	Да, пробовал. Нет ничего конкретного, что помогло бы. Всё найденные алгоритмы ищут или 1 цикл, или не работают. 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	21.02.2021, 22:19	4
	Даже всё отсюда? Всякие dfs, какие-то джонсоны Кликните здесь для просмотра всего текста https://qastack.ru/programming/546655/finding-all-cycles-in-a-directed-graph 0

@RJEKICH 0 / 0 / 0 Регистрация: 16.11.2017 Сообщений: 22
	21.02.2021, 23:09 [ТС]	5
	Джонсон же кратчайшие пути ищет. За ссылку спасибо, посмотрю. Странно, что на этот сайт не натыкался 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	21.02.2021, 23:25	6
	А очевидный перебор пробовали или он работать не будет? Или слишком медленно? Типо такого : void func(vector<int>path){ int beg = path[0]; int last = path.back(); перебираем все связанные с last вершины, текущая - num если num = beg то нашли цикл, выводим path если num нету в path, то заводим vector<int>t = path; t.push_back(num); func(t); } int main() для всех вершин i запускаем func({i}); Вроде бы он должен перебрать все простые пути вообще, если я правильно понимаю, ну и определить из них циклы. 0

@RJEKICH 0 / 0 / 0 Регистрация: 16.11.2017 Сообщений: 22
	22.02.2021, 08:05 [ТС]	7
	Да, это переборная задача, я просто не совсем понимал, как корректно перебор организовать 0