У меня есть ориентированный граф i.e матрицы порядка n x n.
Мне нужно найти все присутствующие в нем циклы вместе с вершинами, участвующими в цикле.Найти все вершины в цикле в ориентированном графе
Вот пример:
A B C D
0 1 1 1
1 0 1 0
1 0 0 0
1 0 0 0
Результат должен быть похож на:
No.of cycles found : 4
A->B->A
A->B->C->A
A->C->A
A->D->A
Вы должны искать для элементарных циклов, в которых ни одна из вершин (кроме начинают/конец) появляется больше чем единожды. В этом случае существуют линейные алгоритмы времени (линейные по узлам + ребрам). См., Например, http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF. Это происходит из второго ответа на Finding all cycles in a directed graph, который лучше, чем первый IMHO.
Итак, что конкретно представляет собой ваш вопрос? – ChriPf
Я хочу, чтобы алгоритм или логика или код находили список вершин, которые задействованы в цикле – user3035457
Это невозможно в многопользовательском режиме, потому что если бы это было тогда, вы могли бы решить проблему пути Гамильтона в многократное время, и эта проблема NP-полной. Проще говоря, число возможных циклов огромно, поэтому это невозможно в полиномиальное время. Вы можете также скопировать его (попробуйте все пути рекурсивно) и запишите, которые возвращаются к источнику и печатают их. Подобно DFS, за исключением того, что вы можете посетить узел более одного раза. Это займет много времени для графиков даже немного разумного размера, хотя, и я не уверен, есть ли способ, который быстрее. – Jimmy