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

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

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

  

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

  

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

  

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

  

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