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

Question

[NoName]

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

Comments

[Wataru]

Граф не взвешанный? Все ребра одинаковой длины? Можно ли ходить по ребру туда-обратно?

[NoName]

Wataru, не взвешанный, ребра одинаковой длины, граф неориентированный, значит ходить туда-обратно можно, если я не ошибаюсь и правильно понимаю определение

[longclaps]

Wataru, если в цикле можно ходить по ребру туда-сюда - любой граф с хоть одним ребром имеет цикл )

[NoName]

Wataru, кажется я не правильно понял, по ребру ходить туда обратно все-же нельзя

[Wataru]

NaName444, Если ходить туда-обратно можно, то у вас всегда есть или цикл длины 1 (если есть петли), или цикл длины 2 (любое ребро). Тут никакой обход не нужен.

Далее, вы уверены, что вам тут нужен обход в глубину? Обход в глубину не ищет кратчайшие расстояния. Только если его выродить в полный перебор.

[NoName]

Wataru, я понимаю, что обход в глубину не ищет кратчайшее расстояние, однако по моему заданию мне требуется
написать две программы, которые ищут кратчайшую длину цикла при помощи обхода в глубину и в ширину. Значит, как вы и сказали, обход нужно выродить в полный перебор

Answer 1

[Wataru]

Ну, раз обход в глубину нужен, то запускайте от каждой вершины полный перебор и ищите пути назад в эту же вершину.

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

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

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

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