计算通过图的路径数
我正在查看从特定节点开始的图表中唯一 x 长度路径的数量。
但是我有一个限制，即在任何路径上没有节点被访问一次以上。
例如，如下图所示：
如果我在从 5 开始的 3 长度路径的数量之后。
答案将是 9。
5 -> 2 -> 1 -> 3
5 -> 2 -> 4 -> 3
5 -> 2 -> 4 -> 7
5 -> 4 -> 2 -> 1
5 -> 4 -> 3 -> 1
5 -> 4 -> 7 -> 6
5 -> 6 -> 7 -> 4
5 -> 7 -> 4 -> 2
5 -> 7 -> 4 -> 3
注意 I我只同意答案（9）而不是具体路径。
我尝试使用 邻接矩阵 的 x 次方来给出路径的数量，但我无法弄清楚如何考虑唯一节点限制。
我也尝试过使用深度优先搜索，但是节点的数量和大小x 使这变得不可行。
编辑：将 DFS 与 BFS 混淆（谢谢 Nylon Smile 和 Nikita Rybak）。
I am looking the number of unique x length paths through a graph starting at a particular node.
However I have a restriction that no node is visited more than once on any path.
For example take the following graph:
If I am after the number of 3 length paths starting at 5.
The answer would be 9.
5 -> 2 -> 1 -> 3
5 -> 2 -> 4 -> 3
5 -> 2 -> 4 -> 7
5 -> 4 -> 2 -> 1
5 -> 4 -> 3 -> 1
5 -> 4 -> 7 -> 6
5 -> 6 -> 7 -> 4
5 -> 7 -> 4 -> 2
5 -> 7 -> 4 -> 3
Note I am only concerted with the answer (9) not the specific paths.
I have tried using an adjacency matrix to the power of x to give the number of paths, but I cannot work out how to account for unique node restriction.
I have also tried using a depth-first search but the amount of nodes and size of x makes this infeasible.
EDIT: Confused DFS with BFS (Thank you Nylon Smile & Nikita Rybak).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是 NP-Hard。
从哈密顿路径减少。
给定一个图，我们需要检查其哈密顿路径的存在...
为每个顶点运行算法，路径长度为 n-1。任何非零返回对应于哈密顿路径，反之亦然。
所以基本上，如果你找到一个多项式时间算法来解决你的问题，那么你就有一个多项式时间算法来解决哈密顿路径问题，有效地证明 P=NP！
注意：这假设 x 是输入。
如果 x 是固定的（即与图中顶点的数量无关），那么您就有 O(n^x) 时间算法，该算法在 P 中，但对于中等大小的 x 仍然相当不切实际。
This is NP-Hard.
Reduction from Hamiltonian Path.
Given a graph whose Hamiltonian Path existence we need to check...
Run your algorithm for each vertex, with a path length n-1. Any non-zero return corresponds to Hamiltonian path and vice versa.
So basically, if you find a polynomial time algorithm to solve your problem, then you have a polynomial time algorithm to solve the Hamiltonian Path problem, effectively proving P=NP!
Note: This assumes x is an input.
If you x was fixed (i.e. independent of the number of vertices in the graph), then you have O(n^x) time algorithms, which is in P, but still pretty impractical for medium sized x.
这个问题是#P（解的数量）中的计数问题，而不是NP（是或否）中的决策问题。
白痴的减少仍然可以证明问题是< a href="http://en.wikipedia.org/wiki/Sharp-P-complete" rel="nofollow noreferrer">#P-Complete 因为汉密尔顿路径也是#P-complete。
This problem is a counting problem in #P (number of solutions) instead of a decision problem in NP (yes or no).
Moron's reduction still works to prove the problem is #P-Complete because Hamilton Paths is also #P-complete.