Самый длинный путь (краевой вес = 1) в решении без направленного графика?

Question

У меня есть неориентированный граф, вес каждого края которого равен 1. График может иметь циклы. Мне нужно найти самый длинный путь на графике (каждый узел появляется один раз). Длина пути - это количество узлов. Любое простое/эффективное решение? Благодаря!

Answer 1

Согласно http://en.wikipedia.org/wiki/Longest_path_problem, поиск самого длинного пути NP-hard. Таким образом, это считается трудной задачей для больших случаев, если только P = NP. В отличие от нахождения кратчайшего пути, где алгоритм BFS является линейным.