给定一个有向图，什么是只访问图中每个顶点一次的算法。这与哈密顿循环不同，因为我不需要路径在同一顶点开始和结束。
回溯算法 我想到的一种算法是回溯，它使用递归实现，在每一步中，您都探索所有可能的连接/路径，并保留一个 bool 访问数组，以确保没有顶点被访问超过一次。向后回溯时，此 bool 值将设置为 false(回溯中必不可少的步骤)。基本情况是比较访问的顶点数，并查看它是否与图中的节点数相匹配，在这种情况下，它将返回 true。另一个基本情况是返回 false，如果尚未访问所有顶点，但不存在其他连接以继续递归。
但是，这样做的时间复杂度将是 O(n!)，这是不可取的。
有没有更好的算法来找到有向图的路径/遍历，它只覆盖图中的每个顶点一次。
最佳答案
根据算法导论一书，这个问题是 NP 完全问题。这个问题没有多项式算法，但也不能证明它不存在。所以在最坏的情况下，你会得到指数级的时间复杂度。
一些笔记。 如果图有一个叶子，那么这个叶子就是路径的开始或结束。如果图有两个叶子，则路径必须从其中一个开始并以另一个结束。 如果图有三个或更多叶子，则哈密顿路径不存在。但是对于一般的图，没有快速的算法。
关于algorithm - 查找访问有向图的所有顶点恰好一次的路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44481232/