查找恰好访问有向图所有顶点一次的路径
给定一个有向图，什么是只访问图的每个顶点一次的算法。这和哈密顿循环不同，我不要求路径在同一个顶点开始和结束。
回溯算法脑海中浮现的一种算法是回溯，使用递归实现，在每一步中，您都会探索所有可能的连接/路径，并保留一个布尔访问数组，以确保没有顶点被多次访问。当向后回溯时，该布尔值将设置为false（回溯中的关键步骤）。基本情况是比较访问的顶点数，并查看它是否与图中的节点数匹配，在这种情况下，它将返回true。另一种基本情况是，如果没有访问所有顶点，但不存在其他继续递归的连接，则返回false。
然而，这种方法的时间复杂度是O（n！）
这是不可取的。
有没有更好的算法来找到一个有向图的路径/遍历，它只覆盖图中的每个顶点一次。
共有1个答案
根据《算法导论》一书，这个问题是NP完全的。这个问题没有多项式算法，但没有证明它不存在。所以在最坏的情况下，你会得到指数时间复杂度。
一些注意事项。如果图有一个叶子，那么这个叶子就是路径的开始或结束。如果图有两个叶子，那么路径必须从其中一个叶子开始，在另一个叶子结束。如果图有三个或更多的叶子，那么哈密顿路径就不存在。但是对于一般的图没有快速的算法。
-
我有一个加权和无向图，有顶点。其中两个顶点是和。 我需要找到最短的路径，从开始，在结束，并通过G的所有顶点（以任何顺序）。 如何做到这一点？ 这不是旅行推销员问题：我不需要访问每个顶点一次，也不想回到第一个顶点。
-
我有一个无向图，我想从一个起始节点列出所有可能的路径。2个节点之间的每个连接在列出的路径中是唯一的，例如，给出以下图表示： 我无法使用现有的算法来完成它，我知道像DFS。任何帮助都将非常感谢。
-
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能存在指数数量的简单路径。但是如果我们只对两个endpoint顶点之间至少一条简单路径上的顶点感兴趣呢？ 也就是说：给定一个无向图和两个不同的顶点，是否有多项式时间算法可以找到两个顶点之间至少一条简单路径上的每个顶点？这与连通性不同；不包括死胡同和死胡同。然而，分支和连接路径是允许的。 我发现编写一个看起来可以解决这个问题的算法
-
我有一张室内地图上的无向位置图。当给定一组顶点时，我要找到覆盖所有这些顶点的最短路径。图形包含52个顶点和150-250条边。 我能用什么最好的算法来找到最短的路径。请不要混淆这是一个旅行推销员的问题。它不需要覆盖所有节点，只需要覆盖给定的节点集。
-
我怎样才能找到一个有向图中的所有顶点，这样每一个顶点都可以从这个顶点到达呢？现在我只能“发明”O(v^3)ALGO--从每个顶点得到一个DFS/BFS，但我确信，有一个更快的方法来解决这个问题。 谢谢你！
-
我有一个无向图，想计算两个顶点之间可能的最长路径，其中每个边只能访问一次，但每个顶点可以访问几次。 我用JTGraph找到的所有最长路径解决方案都是在每个顶点只访问一次的前提下运行的。