c++ - 如何在无向图中找到遍历最多节点的路径？

Question

给定一个无向图和图中的两个任意节点（A 和 B），我如何找到通过最多唯一节点的路径以便在节点 A 和 B 之间导航？

我知道您可以深度搜索它并比较所有长度，但是有更好的方法吗？

Answer 1

那是一个NP完全问题。你真正能做的就是尝试每一种可能性。

Answer 2

这个问题只有在我们谈论无环图时才有意义，所以我假设你是这个意思。

您将不得不暴力尝试所有可能的路径。

要了解原因，请想象一个图形，其中您知道两个节点的最长路径并添加一个节点。如果节点以某种方式连接到它们，您现在必须测试包含新节点的每条路径，包括您已经测试过的路径。