找到一次只访问一个有向图的所有顶点的路径

给定一个有向图，访问图的每个顶点的算法只有一次。这与哈密尔顿循环不同，因为我不需要在同一个顶点开始和结束的路径。找到一次只访问一个有向图的所有顶点的路径

回溯算法 想到的一种算法，是回溯，实现并采用递归，在此，每一个步骤，您探索所有可能的连接/路径，并保持一个布尔访问阵列，以确保没有顶点访问不止一次。当向后追溯时，这个布尔值将被设置为false（回溯中的基本步骤）。基本情况是比较访问顶点的数量，并查看它与图中的节点数相匹配，在这种情况下，它将返回true。另一个基本情况是返回false，如果所有顶点都没有被访问，但没有其他连接存在以继续递归。

然而，这样的时间复杂度将是O(n!)，这是不可取的。

有没有更好的算法来找到有向图的路径/遍历，它只覆盖一次图中的每个顶点。

来源

2017-06-11 saltmangotree

不确定这是否正常工作，但查看强连通的组件（https://en.wikipedia.org/wiki/Strongly_connected_component），并且该图的缩合可能有助于减少运行时间。但我的感觉是，在最坏的情况下你不会比O（n！）好。 – Henry

如果你有一个有效的算法来解决这个问题，你也可以有效地求解哈密尔顿循环（其中“有效”意思是“在多项式时间内”）：对于任何给定的哈密尔顿循环实例，通过删除一个顶点。使用高效的算法n次（每个实例一次）在其中找到一个HP（如果存在）。如果在这n个图中的任何一个中都有一个HP，并且可以通过添加该图中删除的特定顶点将其转换为HC，那么您已经找到了一个HC - 如果没有，就可以“没有任何HC。 –

@Henry，据我所知，强连通的组件是那些组件中的每个顶点都可以从同一个组件的另一个顶点到达的组件。虽然有像Tarjan这样的高效算法，但我觉得我的问题有点不同。我正在寻找只到达所有顶点。你仍然认为有一个比n更好的解决方案！解决这个问题？ – saltmangotree

根据书算法简介这个问题是NP完全的。这个问题没有多项式算法，但没有证明它不存在。所以在最坏的情况下，你会得到指数级的时间复杂度。

一些笔记。如果图有一个叶子，那么这个叶子是路径的开始或结束。如果图形有两个叶子，那么路径必须从其中一个开始并以另一个结束。如果图有三个或更多的叶子，那么哈密顿路径不存在。但对于一般图，没有快速算法。

来源

2017-06-11 13:33:34

谢谢你。当你说，“所以在最坏的情况下，你会得到指数级的时间复杂度。”，你的意思是n！或者是否有更好的算法是x^y，这比n更好！ – saltmangotree

对不起，我没有指定它。我的意思是n！ –

找到一次只访问一个有向图的所有顶点的路径

回答

相关问题