从图算法中的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, 0)在原始图中使用3个边的倍数步行到(t, 0)时，s才在新图表中步行到t。因此，您只需在新图中应用诸如BFS之类的标准路径查找算法，以查看(t, 0)是否可从(s, 0)到达。
请注意，如果您必须将其实际实现为代码，则不必将新图形实际构建为数据结构；它是implicit graph。