algorithm - 偶数路径算法-DFS

Question

首先，我不会撒谎。这是我的作业。我试图解决这个问题太多小时，但我不知道。

我需要编写算法（高效）来找到从给定顶点到所有其他顶点的具有均匀长度路径的所有顶点。

我知道它可能与 DFS 用途有关...

请给我一些指导！

Answer 1

由于是作业，我只提供一些提示：

1. 如果您在不维护集合的情况下执行 DFS 达到一定深度visited- 您“发现”的所有顶点都有来自源的路径，长度等于当前深度。
2. 如果你做一个 DFS 到 depth 2|V|，那么所有从源头开始的路径长度相等的顶点都将在某个均匀的深度级别上被发现。[说服自己为什么：奇数周期会发生什么？偶数循环会发生什么？]

注意：运行时间是顶点数的指数[加倍]。

Answer 2

对于每个节点 i，创建 3 个布尔状态
(i,0)：未
达到 (i,1)：可以通过奇数长度达到
(i,2)：可以通过偶数长度达到，
最初它们都是零
，然后，您执行dfs，
如果您发现不会更改节点的状态，则可以在 dfs 内更改您访问的节点的状态，然后停止该线程。
因为总共有 3*n 个状态可以改变，所以你需要的最长时间是
O(m)，其中边的数量是多少~

Answer 3

您是否担心运行时间？已经讨论过了吗？您是否讨论过有效的集合数据结构？如果不是，那么阿米特的提示应该对您有所帮助。

如果是，那么您可能应该更聪明。当您讨论 DFS 时，您谈到了维护一组先前访问过的顶点，是吗？

相反，您可以维护多个集合，每个集合的含义略有不同。您可能会设想您访问的集合是这些单独集合的并集，但至关重要的是，如果某个顶点出现在一个顶点中，然后稍后又出现在另一个顶点中，您可能需要重新访问它。

问问自己：我可以将顶点放入哪些集合中？如果一个顶点已经通过被访问加入了某个集合，我什么时候需要重新访问它？小心，你很容易在这里犯错。