Эта проблема для меня выглядит очень интересной. Он собирался найти простой цикл (то есть цикл, где нет повторяющихся узлов) в ориентированном графе.
Мое решение идет следующим образом, то есть этот график является проблемой случая:
Я знаю, что в графике есть цикл, когда вы можете найти «задние края» в поиске по глубине (пунктирная на моей картинке в DFSTree), и на мгновение я могу быть уверен в нескольких циклах, но не в все, простые циклы. Потому что направленные egdes так важны для цикла, т. Е. (0123)! = (0321)
Я думаю сделать make для каждого узла с back-edge, но я не уверен, и это не ясно. Итак, я прошу вас, если вы ведете меня. Благодарность!.
Вот мой список простых циклов для моей задачи.
algorithms
graphs
enumeration
jonaprieto
источник
источник
Ответы:
Этот вопрос кажется очень Googleable. Например, вас может заинтересовать алгоритм, представленный в этой статье:
Нахождение всех элементарных цепей ориентированного графа . Дональд Б. Джонсон. СИАМ Ж. КОМПЬЮТ. Том 4, № 1, март 1975 г.
Статья содержит полный алгоритм.
источник