algorithm - 是否有一种有效的算法可以在邻接矩阵形式的无向和未加权图中找到 k 长度路径(不是行走)的数量？

Question

我知道可以通过查找邻接矩阵的 k 次方来找到两个顶点之间的 k 长度游走的数量，但是游走包括在计算中多次遍历单个边。

编辑:我只想计数而不是计算它们，最好使用矩阵代数。我可以做一个修改后的 DFS，但这比矩阵数学效率低。

Answer 1

一般来说，没有已知的方法来实现这一点。一种看待这一点的方法是，如果您选择 k 作为图中的节点数，那么您要求的是图中哈密顿路径的数量。然而，确定一个图是否包含哈密顿路径的问题是一个典型的 NP 完全问题，除非 P = NP 否则不存在多项式-时间算法。

换句话说 - 哈密顿路径问题在多项式时间内简化为您的问题。这使您的问题变得NP-hard，这意味着它没有已知的多项式时间算法。