在有向图中查找从 s 到长度可被 3 整除的 t 的步行
Finding walk from s to t of length divisible by 3 in directed graph
从图算法 Jeff Erickson's lecture notes 开始，有一个练习检查给定顶点 s 和 t 之间的行走是否可以在有向图中被 3 整除。
我想到的是在图上使用广度优先搜索得到从s到t的所有路径。如果简单路径的长度不能被 3 整除，运行 算法再次检查 s 和 t 之间是否存在循环长度不能被 3 整除的循环.不过，我觉得这个方法真的很低效
如果您对这个问题有什么好的建议，那就太好了。
这种题往往可以通过换图套用标准算法来解决，而不是换算法。
在这种情况下，我们可以创建一个新图，每个节点都有三个副本，例如如果u是原始图中的一个节点，那么新图有三个对应的节点(u, 0)、(u, 1)和(u, 2)。对于原始图中的每条边u → v，新图具有三个对应的边(u, 0) → (v, 1)、(u, 1) → (v, 2)和(u, 2) → (v, 0).
给定 (n_0, r_0) → ... → (n_k, r_k) 和 k 条边的行走，我们知道 r[i+1] = r[i] + 1 (modulo 3)，因为新图中的所有边都满足 属性。因此如果 r_0 = 0 那么 r_k = k (modulo 3).
因此，当且仅当 s 在原始图中使用3条边的倍数。因此，您可以在新图中应用 BFS 等标准寻路算法，看看 (t, 0) 是否可以从 (s, 0).
到达
请注意，如果您必须将其实际实现为代码，则没有必要将新图实际构建为数据结构；这是一个 implicit graph.
从图算法 Jeff Erickson's lecture notes 开始，有一个练习检查给定顶点 s 和 t 之间的行走是否可以在有向图中被 3 整除。
我想到的是在图上使用广度优先搜索得到从s到t的所有路径。如果简单路径的长度不能被 3 整除，运行 算法再次检查 s 和 t 之间是否存在循环长度不能被 3 整除的循环.不过，我觉得这个方法真的很低效
如果您对这个问题有什么好的建议，那就太好了。
这种题往往可以通过换图套用标准算法来解决，而不是换算法。
在这种情况下，我们可以创建一个新图，每个节点都有三个副本，例如如果u是原始图中的一个节点，那么新图有三个对应的节点(u, 0)、(u, 1)和(u, 2)。对于原始图中的每条边u → v，新图具有三个对应的边(u, 0) → (v, 1)、(u, 1) → (v, 2)和(u, 2) → (v, 0).
给定 (n_0, r_0) → ... → (n_k, r_k) 和 k 条边的行走，我们知道 r[i+1] = r[i] + 1 (modulo 3)，因为新图中的所有边都满足 属性。因此如果 r_0 = 0 那么 r_k = k (modulo 3).
因此，当且仅当 s 在原始图中使用3条边的倍数。因此，您可以在新图中应用 BFS 等标准寻路算法，看看 (t, 0) 是否可以从 (s, 0).
请注意，如果您必须将其实际实现为代码，则没有必要将新图实际构建为数据结构；这是一个 implicit graph.