@NaName444

Как определить длину кратчайшего цикла в неориентированном графе?

Здравствуйте. Имеется неориентированный граф, представленный в виде матрицы смежности. При помощи обхода в глубину необходимо найти длину кратчайшего цикла в нем. Обход в глубину я изучал, но вот как решить именно такую задачу я, к сожалению, без понятия. Прошу вашей помощи. Нагуглить ничего годного не смог. Реализация требуется на языке C/C++, желательно с использованием библиотеки vector
  • Вопрос задан
  • 968 просмотров
Решения вопроса 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Ну, раз обход в глубину нужен, то запускайте от каждой вершины полный перебор и ищите пути назад в эту же вершину.

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

Для ускорения можно: Не уходить рекурсивно глубже, чем текущий ответ. Помечать вершины не просто пометкой посещена/не посещена, а глубиной рекурсивного вызова. Тогда, если есть ребро в уже обойденную вершину - вы нашли какой-то цикл с какой-то длинной (текущая глубина - глубина второй вершины + 1). Его сразу же можно брать как возможный ответ. Если граф связный, то можно запускаться только от одной вершины, или можно запускаться от одной вершины в каждой компоненте связности.

Но это все равно будет работать за экспоненциальную сложность.

Другая задача - проверить, есть ли в графе любой цикл - решается обходом в глубину за линейную сложность.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы