graph - Longest path (edge weight = 1) in Un-directed graph solution?

Question

I have an un-directed graph that weight of each edge is 1. The graph may have cycles. I need to find a longest path in the graph (each node appear once). The length of the path is number of nodes. Any simple/effective solution? Thanks!

Answer 1

http://en.wikipedia.org/wiki/Longest_path_problemによると、最長パスを見つけることは NP 困難です。そのため、大きなインスタンスの問題を解決するのは難しいと考えられていますP = NP。BFSアルゴリズムが線形である最短経路を見つけるのとは対照的です。