在有向图中只访问一次所有节点

Question

我有一个有向图，我想找到一条只访问每个节点一次的路径。我想以一种很好的复杂性来做到这一点。这可能吗？如果是，如何？

Answer 1

您正在搜索Hamiltonian path，这是一个简单的开放路径，其中每个节点只包含一次。

在给定图中找到哈密顿路径是NP-complete。事实上，确定给定（有向或无向）图是否包含哈密顿路径已经是 NP 完全的（通过减少例如顶点覆盖问题证明）。

如果你仍然想编码，这里是github 上的一个实现。如果你想要一个快速的解决方案，也许启发式就足够了（例如受 DNA 分子的启发，或者在图的子集上快速运行的解决方案。例如，如果你有一个 DAG，你可以做一个拓扑排序，然后检查如果连续的顶点相连。如果是，拓扑排序给出了一条哈密顿路径。