algorithm - 找到一条长度可以被 3 整除的路径

Question

给定一个无向图(未加权)和两个顶点 u 和 v，我怎样才能在 u 和 v 之间找到一条长度能被 3 整除的路径？

请注意，路径不一定是简单路径。

我考虑了 DFS 的变体和存储路径(以及用于回溯)的堆栈，但无法完全理解如何同时跟踪非简单路径。

时间复杂度应该是O(V+E)，所以我估计一定是BFS或者DFS的变体。

Answer 1

执行此操作的一种方法是计算图的修改版本并对该图执行 BFS 或 DFS。

想象一下，将图形在其自身顶部堆叠 3 次。每个节点现在出现 3 次。将第一个副本注释为“mod 0”，将第二个副本注释为“mod 1”，将第三个副本注释为“mod 2”。然后，改变边，使得从节点 u 到节点 v 的任何边总是从节点 u 到下一层图中的节点 v。因此，如果有一条从 u 到 v 的边，那么现在就有一条从 u mod 0 到 v mod 1、u mod 1 到 v mod 2 和 u mod 2 到 v mod 0 的边。如果你在上面进行 BFS 或 DFS这个图并找到从 u mod 0 到任何节点 v mod 0 的路径，你必然有一条路径，其长度必须是三的倍数。

您可以通过复制该图两次并适本地重新连接边来在时间 O(m + n) 内显式构建此图，从那里 BFS 或 DFS 将花费时间 O(m + n)。不过，这会使用内存 Θ(m + n)。

另一种解决方案是模拟在不实际构建新图的情况下执行此操作。执行 BFS，并为每个节点存储 三个 距离 - 模 0 距离、模 1 距离和模 2 距离。每当您从队列中出列一个节​​点时，将其后继者加入队列，但将它们标记为在下一个 mod 层(例如，如果您将一个节点从 mod 0 级出列，将其后继者加入 mod 1 等)，您可以独立跟踪是否您已到达距离为 mod 0、mod 1 和 mod 2 的节点，不应多次将节点入队给定的 mod 级别。这也需要时间 O(m + n)，但没有显式构造第二个图，因此只需要 O(n) 的存储空间。

希望这对您有所帮助!