图形遍历n步

给出一个简单的无向图，如下所示：

从D，A，B或C（ V_start ）开始 – 我必须计算从n步骤的起始点（ V_start ）到起始点（ V_start ）有多少可能的路径，其中每个边和顶点都可以被访问无限次。

我正在考虑进行深度优先搜索，当steps > n || (steps == n && vertex != V_start)时停止 steps > n || (steps == n && vertex != V_start) ，但是，如果例如n = 1000000 ，则这变得相当昂贵。 我的下一个想法让我将DFS与动态编程相结合，然而，这就是我被困住的地方。

（这不是家庭作业，只是为了学习而被困在图形和算法中。）

如何在合理的时间内用大n解决这个问题？

Answer 1

该任务通过矩阵乘法求解。

创建包含0和1的矩阵n x n （如果存在从i到j路径，则为1 mat[i][j]单元格mat[i][j] ）。 将此矩阵乘以k倍（考虑使用快速矩阵求幂）。 然后在矩阵的单元格mat[i][j]您有从i开始并以j结尾的长度为k的路径数。

注意 ：快速矩阵取幂基本上与快速取幂相同，只是你将数乘以矩阵乘以数。

注2：假设n是图中顶点的数量。 那么我在这里提出的算法在时间复杂度O（log _k * n ³ ）中运行并且具有O（n ² ）的存储器复杂度。 如果您使用此处所述的优化矩阵乘法，您可以进一步改进它。 然后时间复杂度将变为O（log _k * n ^{log ₂ 7} ）。

---

编辑根据Antoine的要求，我解释了为什么这个算法实际有效：

我将通过归纳certificate该算法。 归纳的基础是显而易见的：最初我在矩阵中有长度为1的路径数。

让我们假设直到k的幂，如果我将矩阵提高到k的幂，我在mat[i][j]中具有i和j之间的长度k的路径的数量。

现在让我们考虑下一步k + 1 。 很明显，每个长度为k + 1路径由长度为k + 1的前缀和一个以上的边缘组成。 这基本上意味着长度k + 1的路径可以通过（这里我用mat_pow_k表示提升到k次幂的矩阵）来计算

num_paths（x，y，k + 1）= sum _{i = 0} ^{i mat_pow_k [x] [i] * mat [i] [y]}

再次： n是图中顶点的数量。 这可能需要一段时间才能理解，但基本上只有在x和y之间存在直接边缘时，初始矩阵在其mat[i][y]单元格中才有1。 并且我们计算这种边缘的所有可能前缀以形成长度为k + 1路径。

然而，我写的最后一件事实际上是计算mat第k + 1幂，这certificate了归纳的步骤和我的陈述。

Answer 2

这很像一个动态编程问题：

1. 将af [n] [m]定义为以m步开始从起点到点n的路径数
2. 从每个点n到其相邻的k，你有公式：f [k] [m + 1] = f [k] [m + 1] + f [n] [m]
3. 在初始化中，所有f [n] [m]将为0，但f [starting_point] [0] = 1
4. 所以你可以计算最终结果

伪代码：

 memset(f, 0, sizeof(f)); f[starting_point][0] = 1; for (int step = 0; step < n; ++step) { for (int point = 0; point < point_num; ++point) { for (int next_point = 0; next_point < point_num; ++ next_point) { if (adjacent[point][next_point]) { f[next_point][step+1] += f[point][step]; } } } } return f[starting_point][n]