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

Question

给定一个无向图（未加权）和两个顶点u和v，我如何找到u和v之间长度可被 3 整除的路径？

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

我考虑了 DFS 的变体和存储路径（以及用于回溯）的堆栈，但不能完全理解如何跟踪非简单路径。

时间复杂度应该是 O(V+E)，所以我希望它必须是 BFS 或 DFS 的变体。

Answer 1

一种方法是计算图的修改版本并在该图上执行 BFS 或 DFS。

想象一下将图形堆叠三遍。每个节点现在出现 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 over这个图并找到从 u mod 0 到任何节点 v mod 0 的路径，你必须有一个长度必须是三的倍数的路径。

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

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

希望这可以帮助！

Answer 2

作弊方式：

只是从 A 到 B 的 DFS/BFS；如果长度 L % 3 == 0，则结​​束；L % 3 == 1，步行到邻居并返回；否则，走到邻居那里，然后再回来。

---

如果这不符合您的限制条件，那么：

您可以使用修改后的 BFS 来执行此操作。在进行搜索时，尝试标记您遇到的所有循环；您可以获得所有简单的循环以及长度。

之后，如果从 A 到 B 的路径长度为 L % 3 == 0，那么你就找到了。

如果不是，那么在所有循环的长度为 Lk % 3 == 0 的情况下，没有解决方案；

如果有一些长度为 K % 3 != 0 的循环，你可以先从 A 到这个循环，循环一到两次然后回到 A 再到 B。这样可以保证找到长度为 3 的路径。

Answer 3

这里是伪代码。它使用BFS和，简单的计数器和模测试。

1. 我：= 0
2. 将节点 u 加入队列
3. i++，将一个节点出列并检查它
4. 如果在该节点中找到元素 v 并且 i mod 3 == 0 ，则退出搜索并返回结果。否则，将尚未发现的任何后继节点（直接子节点）排入队列。
5. 如果队列为空，则图上的每个节点都已检查——退出搜索并返回“未找到”。
6. 如果队列不为空，请从步骤 2 开始重复。

注意：用堆栈替换队列也应该有效。那将是DFS。