Задача нахождения самого длинного цикла в графе: NP-hard , поскольку решение этой задачи позволяет ответить на вопрос " Является ли этот граф гамильтонианом? " (обладает ли онгамильтоновым циклом), который сам по себе является NP-полной задачей.
Таким образом, действительно, ни один эффективный алгоритм не может этого сделать.
Существуют методы, основанные на умножении матриц, чтобы найти цикл длины k в графе.,Вы можете найти объяснения о нахождении циклов с использованием умножения матриц в этом вопросе .Но будьте осторожны, методы умножения матриц позволяют обнаруживать walks заданной длины между двумя вершинами, и повторение вершин допускается при прогулке.