Имеется односвязный направленный граф. Из каждой вершины можно попасть в другую гарантированно одним путём, но, как правило, несколькими. Аналогично, гарантировано, что выйдя из вершины, можно в неё вернуться, и сделать это можно, как правило, более чем одним способом.
Выбирается вершина (в моём случае не важно какая, граф самоподобен и выглядит одинаково из любой вершины). Требуется найти
все циклы, проходящие через выбранную вершину и через любое число других, но посещающую каждую
не более одного раза. Имеет ли эта задача устоявшееся название (типа задачи коммивояжера)?
На вскидку приходит поиск в глубину. На каждой итерации из текущей вершины просматриваем список выходящих рёбер, если очередное ребро ведёт в ещё не посещённую вершину, то сохраняем текущие вершину и ребро в стек, помечаем новую вершину посещённой и переходим к следующей итерации с новой вершиной в качестве текущей. Если новая вершина является исходной, то недеструктивно просматриваем стек, чтобы восстановить цикл и сохраняем найденный результат, переходим к следующему ребру. Если для текущей вершины все выходящие рёбра просмотрены, то снимаем с неё пометку "пройденности", достаём из стека предыдущую вершину и ребро, по которому попали в текущую, делаем предыдущую текущей и переходим к следующей итерации с новым ребром.
На первый взгляд такой алгоритм будет иметь экспоненциальную сложность:
где
m — число рёбер выходящих из каждой вершины и
N — размер графа. Конечно, не всякий рассматриваемый путь пройдёт все вершины, прежде чем упрётся в уже посещённую, но тем не менее, вопрос производительности (для меня во всяком случае) стоит.
Если я прав в моей оценке сложности, то есть ли какие-нибудь улучшения к алгоритму или что-нибудь принципиально более совершенное?
06.07.2024, 18:34 
