在无向未加权图中从第一个顶点返回到自身的长度为 K 的方法数
Number of ways of length K to get from the first vertex back to itself in an undirected unweighted graph
我有一个无向未加权图，其中 N 个顶点编号从 1 到 N。我需要找到长度为 K 的方法数，以便从 first 顶点返回到本身。允许在此过程中多次重新访问第一个（或任何其他）顶点。
一种可能的解决方案是采用邻接矩阵，找到该矩阵的 K 次方，然后所得矩阵的左上角元素将成为问题的答案。该方法的时间复杂度为O(N^3 * log(K))。
但是有没有更快的方法来解决这个问题？
简短回答：是的，你总能比 O(N^3 log K) 做得更好。
长答案：最快方法的复杂性确实取决于 K 的大小，并且在较小程度上取决于图形的当前表示形式和图形中的边数。这个问题的具体术语是“计算闭合行走”。
小K
使用动态规划。对于给定的初始顶点 x，我们有一个二维 DP 状态。
Let DP[ y ][ i ] be the number of walks of length i from our initial
vertex to y. Then DP[ y ][ 1 ] is 1 if y is adjacent to our initial
vertex, or 0 otherwise. The recurrence relation for i >
1 is: DP[ y ][ i ] is the sum over all neighbors w of y of (DP[ w ][ i - 1 ])
那么你的答案就是DP[ K ][ 1 ].
执行此操作的简短 Python 代码，假设图形是邻接表表示：
dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)]
for neighbor in graph[1]:
dp[1][neighbor] = 1
for walk_length in range(2, K + 1):
for vertex in range(1, N + 1):
for neighbor in graph[vertex]:
dp[walk_length][neighbor] += dp[walk_length - 1][vertex]
print(dp[K][1])
时间复杂度为O(K * (N + E))，其中E为边数。额外的 space 复杂度是 O(NK)，可以通过少量的努力减少到 O(N)。如果你的图是密集的，它最多有 |E| = O(N^2)，所以这是 O(K * N * N)；如果你的图表是稀疏的，就像一棵树，这是 O(K * N)。邻接矩阵和邻接表之间的转换是O(N^2).
的附加因素
大K
据我所知，对于大 K 的最佳答案（复杂性）是使用类似于您建议的 adjacency matrix exponentiation 的策略。这种方法是有效的，但我们可以更聪明一点。
回想一下，无权无向图的邻接矩阵是实对称矩阵，因此diagonalizable.设邻接矩阵为A，谱分解为A = P * D * (P^-1)，其中 D 是对角矩阵。然后我们找到A^K = P * (D^K) * (P^-1)的左上角元素，这需要对单个特征值进行N次幂的K次方，然后进行2N次乘法和加法
由于特征值的大小受最大程度或 O(N) 的限制，因此主导项由计算具有 O(log N) 位数字 x 的 x^K 的成本决定。确定这里的时间复杂度很复杂：我们必须开始讨论计算模型，以及整数乘法的成本。如果我们谈论的是计算的字 RAM 模型，或者机器字足够大以处理输出的模型，那么您的 O(N^3 log K) 界限就有效。如果您只想要对某个固定数字取模的答案，它也可以更普遍地工作。否则，如果 K 任意大，我们的 N 个特征值幂每个可以有 O(K) 位，所以这最后一步可能需要 O( K * N log log N) 时间，这仍然比原始的全矩阵求幂更有效（至少O(N^2 * K^2) 在这种情况下）。
矩阵分解的复杂度与矩阵乘法的复杂度密切相关，是一个悬而未决的问题。它介于 N^2 和 N^(2.373) 之间，但理论上最优复杂度的问题是 best addressed in math stackexchange questions like this one，通常与实际问题无关。
我有一个无向未加权图，其中 N 个顶点编号从 1 到 N。我需要找到长度为 K 的方法数，以便从 first 顶点返回到本身。允许在此过程中多次重新访问第一个（或任何其他）顶点。 一种可能的解决方案是采用邻接矩阵，找到该矩阵的 K 次方，然后所得矩阵的左上角元素将成为问题的答案。该方法的时间复杂度为O(N^3 * log(K))。 但是有没有更快的方法来解决这个问题？
简短回答：是的，你总能比 O(N^3 log K) 做得更好。
长答案：最快方法的复杂性确实取决于 K 的大小，并且在较小程度上取决于图形的当前表示形式和图形中的边数。这个问题的具体术语是“计算闭合行走”。
小K
使用动态规划。对于给定的初始顶点 x，我们有一个二维 DP 状态。
Let DP[ y ][ i ] be the number of walks of length i from our initial vertex to y. Then DP[ y ][ 1 ] is 1 if y is adjacent to our initial vertex, or 0 otherwise. The recurrence relation for i > 1 is: DP[ y ][ i ] is the sum over all neighbors w of y of (DP[ w ][ i - 1 ])
那么你的答案就是DP[ K ][ 1 ].
执行此操作的简短 Python 代码，假设图形是邻接表表示：
dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)]
for neighbor in graph[1]:
dp[1][neighbor] = 1
for walk_length in range(2, K + 1):
for vertex in range(1, N + 1):
for neighbor in graph[vertex]:
dp[walk_length][neighbor] += dp[walk_length - 1][vertex]
print(dp[K][1])
时间复杂度为O(K * (N + E))，其中E为边数。额外的 space 复杂度是 O(NK)，可以通过少量的努力减少到 O(N)。如果你的图是密集的，它最多有 |E| = O(N^2)，所以这是 O(K * N * N)；如果你的图表是稀疏的，就像一棵树，这是 O(K * N)。邻接矩阵和邻接表之间的转换是O(N^2).
大K
据我所知，对于大 K 的最佳答案（复杂性）是使用类似于您建议的 adjacency matrix exponentiation 的策略。这种方法是有效的，但我们可以更聪明一点。
回想一下，无权无向图的邻接矩阵是实对称矩阵，因此diagonalizable.设邻接矩阵为A，谱分解为A = P * D * (P^-1)，其中 D 是对角矩阵。然后我们找到A^K = P * (D^K) * (P^-1)的左上角元素，这需要对单个特征值进行N次幂的K次方，然后进行2N次乘法和加法
由于特征值的大小受最大程度或 O(N) 的限制，因此主导项由计算具有 O(log N) 位数字 x 的 x^K 的成本决定。确定这里的时间复杂度很复杂：我们必须开始讨论计算模型，以及整数乘法的成本。如果我们谈论的是计算的字 RAM 模型，或者机器字足够大以处理输出的模型，那么您的 O(N^3 log K) 界限就有效。如果您只想要对某个固定数字取模的答案，它也可以更普遍地工作。否则，如果 K 任意大，我们的 N 个特征值幂每个可以有 O(K) 位，所以这最后一步可能需要 O( K * N log log N) 时间，这仍然比原始的全矩阵求幂更有效（至少O(N^2 * K^2) 在这种情况下）。
矩阵分解的复杂度与矩阵乘法的复杂度密切相关，是一个悬而未决的问题。它介于 N^2 和 N^(2.373) 之间，但理论上最优复杂度的问题是 best addressed in math stackexchange questions like this one，通常与实际问题无关。