无向图解决方案中最长路径（边权重= 1）？

Question

我有一个无向图，每条边的权重为1.该图可能有循环。我需要在图中找到最长的路径（每个节点出现一次）。路径的长度是节点的数量。任何简单/有效的解决方案谢谢！

Answer 1

根据http://en.wikipedia.org/wiki/Longest_path_problem，找到最长的路径是NP-hard。所以除非P = NP被认为是一个很难解决大案例的问题。与找到最短路径相反，BFS算法是线性的。