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

Question

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

Answer 1

根据http://en.wikipedia.org/wiki/Longest_path_problem，找到最长的路径是 NP 难的。因此，除非P = NP. 与寻找最短路径相反，BFS算法是线性的。

Answer 2

我有一个类似的案例，但我的节点有限，数量少于 50。

我在一个 SQL 数据库表（从、到和长度列）中对其进行建模，并试图找到两个给定节点之间的每条路径，并计算路径的长度以识别最长的路径。

在 SQL Server 上，我构建了一个 SQL 递归 CTE 查询来定义最长路径。请参阅参考文档中查找最长路径的文章

请注意，即使有 50 个节点，查询也计算了从开始节点到结束节点的 70m 多条可能路径，而没有两次传递相同的节点，并且我的开发计算机上的 SQL Server 引擎需要大约 2 个小时才能完成此查询的执行。