algorithm - 小度数小图中的最长路径

Question

这是我在类里面遇到的问题(我向你保证这不是家庭作业)。到现在我还在琢磨。您将收到最多包含 25 个节点和 25 条边的图形。此外，每个节点的度数最多为 3。任务是在该图中找到最长的路径。但是，您不仅会收到 1 张图表，还会收到 15,000 张图表，您需要在 1 秒内找到所有图表中最长的路径。谁能给我一个解决这个问题的方法(或者更好的是，只是一个提示)？非常感谢!

信息:
- 可以重新访问节点，唯一的约束是边。
- 图形由边给出。所以第一行说明有多少节点和边，之后的几行代表边，每条边由一对整数组成。
- 边未加权。
- 唯一需要的答案是路径的长度，而不是路径本身。
- 这可能很重要:图形不一定是连通的。

Answer 1

在我看到“节点可以重访”之后，我意识到这在某些方面是一个技巧问题。为了满足那些看似难以置信的时间限制，您在这里真正需要的不是构造这样一条路径的算法(顺便说一句，如果顶点可以重用，通常称为 trail)，而是对于每个连接的图的组成部分，一种快速检测该组成部分中的所有或几乎所有边是否可以包含在一条路径中的方法。

所以这是我的提示:你知道柯尼斯堡有七座桥吗？ ;-)

这可能看起来很神秘，但我认为一些快速搜索将为您指明正确的方向，您很快就会找到一种方法来快速检测组件中的所有边是否可以构成同一条路。 (当上述问题的答案为“否”时，您需要做更多的思考来计算可以包含多少条边。)