algorithm - 找到至少一次访问有向图中每个顶点的路径的算法

Question

我有一个有向图的 SCC。我想找到一条从顶点 s 开始至少访问此 SCC 中每个顶点一次的路径。我知道这可能是一个 NP 问题。无论如何，我该如何解决这个问题？

Answer 1

如果您需要任何路径（不需要简单），那么您可能会找到从 1 到 2 的一些路径，然后是从 2 到 3 的一些路径，依此类推（1、2、3，...是您的 SCC 中的顶点数）。如果您需要简单的路径，那么gilleain在评论中正确地注意到这是一个 NP 完全哈密顿路径问题。