时间戳

首页 > 解决方案 > 在无向无权图中从第一个顶点返回到自身的长度为 K 的方式数

algorithm - 在无向无权图中从第一个顶点返回到自身的长度为 K 的方式数

问题描述

我有一个无向无权图，其中N个顶点从 1 到N编号。我需要找到从第一个顶点返回到自身的长度为K的方式的数量。在此过程中，允许多次重新访问第一个（或任何其他）顶点。一种可能的解决方案是采用邻接矩阵，找到该矩阵的K次方，然后结果矩阵的左上角元素将成为问题的答案。此方法的时间复杂度为O(N^3 * log(K))。但是有没有更快的方法来解决这个问题？

标签： algorithmmatrixgraph-theoryadjacency-matrix

解决方案

简短的回答：是的，你总是可以做得比O(N^3 log K).

长答案：最快方法的复杂性确实取决于 K 的大小，并且在较小程度上取决于图的当前表示形式和图中的边数。这个问题的具体术语是“计算封闭步行”。

小K

使用动态规划。对于给定的初始顶点 x，我们有一个二维 DP 状态。

令 DP[ y ][ i ] 为从我们的初始顶点到 y 的长度为 i 的游走数。如果 y 与我们的初始顶点相邻，则 DP[y][1] 为 1，否则为 0。i > 1 的递归关系是：DP[ y ][ i ] 是 (DP[ w ][ i - 1 ]) 的 y 的所有邻居 w 的总和

那么你的答案就是 DP[K][1]。

执行此操作的简短 Python 代码，假设 graph 是邻接表表示：

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 是边数。额外的空间复杂度是O(NK)，可以通过O(N)少量的努力降低到 。如果你的图很密集，它最坏的情况|E| = O(N^2)是O(K * N * N); 如果你的图是稀疏的，就像一棵树，这是O(K * N). 邻接矩阵和邻接列表之间的转换是 的一个加法因子O(N^2)。

大K

据我所知，对于大 K 的最佳答案（复杂性）是使用类似于您建议的邻接矩阵求幂的策略。这种方法是有效的，但我们可以更聪明一点。

回想一下，未加权无向图的邻接矩阵是实对称矩阵，因此它是可对角化的。设邻接矩阵为 A，谱分解为 A = P * D * (P^-1)，其中 D 是对角矩阵。然后我们找到 A^K = P * (D^K) * (P^-1) 的左上元素，这需要对单个特征值进行 N 次幂运算，然后是 2N 次乘法和加法。

由于特征值的大小受最大度数或 的限制O(N)，因此支配项由计算具有 O(log N) 位数的数字 x 的 x^K 的成本确定。确定这里的时间复杂度很复杂：我们必须开始讨论计算模型，以及整数乘法的成本。O(N^3 log K)如果我们谈论的是计算的词 RAM 模型，或者机器词足够大以处理输出的模型，那么您的界限就有效。如果您只想要以某个固定数字为模的答案，它也可以更普遍地工作。否则，如果 K 任意大，我们的 N 个特征值幂每个可以有 O(K) 位，所以最后一步可能需要O( K * N log log N)时间，这仍然比原始的全矩阵求幂更有效（至少O(N^2 * K^2)在这种情况下是这样）。

矩阵分解的复杂度与矩阵乘法的复杂度密切相关，这是一个开放性问题。它在 N^2 和 N^(2.373) 之间，但理论上最优复杂度的问题最好在像这样的数学 stackexchange 问题中解决，并且通常与实际问题无关。

推荐阅读