偶数长度路径算法-DFS

Question

首先，我不会说谎。这是我的作业。我已经花了太多的时间来解决这个问题，但是我一点头绪都没有。

我需要编写一个高效的算法，从给定的顶点到所有其他顶点找到具有偶数长度路径的所有顶点。

我知道这可能与使用DFS有关......

请给我一些指导！

- Bobbbaa

---

你的问题不够清晰。你是在寻找一个子集U，其中U包含于V，以便对于U中的每个节点u，都存在一条路径/最短路径【长度相同】？并且路径需要延伸到哪里？是所有在U或者在V中的顶点吗？ - amit

我有一个顶点s。我需要找到所有可以通过偶数长度路径从s到达的顶点。 - Bobbbaa

这是针对有向图还是无向图？这是一个简单图吗？ - gcbenison

Answer 1

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

1. 如果您进行DFS并达到一定深度，而不维护visited集合，则所有“发现”的顶点都具有从源到当前深度的路径。
2. 如果您进行DFS并达到深度2|V|，则所有源自偶数长度路径的顶点将在某个偶数深度级别中被发现。【说服自己为什么：对于奇数长度循环会发生什么？对于偶数长度循环会发生什么？】

注意：运行时间与顶点数呈指数关系[加倍]。

- amit

---

你好Amit。谢谢你的答案，但对我来说并不是很清楚。"DFS up to depth 2|v|" 是什么意思？ - Bobbbaa

@AnatHershkovitz 继续使用深度优先搜索，直到达到深度为2|V|，其中|V|是图中顶点的数量。 - amit

还不是很清楚，但我会尝试弄清楚这个问题。无论如何，谢谢。 - Bobbbaa

你能不能像@cloudygoose那样给每个顶点添加一个“visited by even”属性来加快速度？ - gcbenison

@gcbenison：我不喜欢改变算法，我宁愿简化问题并使用现有的算法。这个问题与此处非常相似，但它还要求一个高效的算法。我在那里提出了一种解决方案来简化图形G，并使用DFS，因为它 - 在不改变它的情况下 - 使得分析和证明正确性更容易。 - amit

Answer 2

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

- cloudygoose

---

如果您到达一个状态为“偶数”的节点，并且步数为奇数，您不会想在那个点将其状态更改为“奇数”，对吗？（然而，您的规则似乎表明您会这样做） - gcbenison

Answer 3

你是否关注运行时间？这个问题已经讨论过了吗？你有没有谈到集合的有效数据结构？如果没有，那么阿米特的提示应该会帮到你。

如果是的话，那么你可能需要更聪明一些。你在讨论DFS时提到过维护先前访问过的顶点的集合，是吗？

你可以代替维护一个集合，而维护多个含义略有不同的集合。你可能想象你的访问集合是这些不同集合的并集，但至关重要的是，如果一个顶点首先出现在一个集合中，然后在之后又出现在另一个集合中，你可能需要重新访问它。

问问自己：我应该将哪些顶点放入集合中？如果一个顶点已经通过被访问而加入了某个集合，什么情况下可能需要重新访问它？要小心，你很容易犯错。

- Jeff Burdges