偶数长度路径算法

Question

我被要求写一个高效的算法，找到有从给定顶点出发偶数长度路径的所有定向图中的顶点。

这是我的想法：

（它与DFS的“Visit”算法非常相似）

Visit(vertex u)

     color[u]<-gray
     for each v E adj[u]
       for each w E adj[v]
            if color[w] = white then
                     print w
                     Visit(w)

我认为它可以工作，但是当图形中有循环时，计算其效率非常困难。你能帮助我吗？

- Chen Saranga

---

请重构以下句子：“在有向图中，查找从给定顶点到所有其他顶点存在偶数长度路径的所有顶点”，这个句子对我来说不太通顺。 - Ivaylo Strandjev

只是为了明确 - 您不需要路径是最短路径吗？ - Deestan

不，它们只需要是偶数长度。 - Chen Saranga

如果给定的图是：（边） a->b a->c b->d e->b d->e如果给定的顶点是a，则答案应为：d，b，e。 - Chen Saranga

Answer 1

如果我可以提出一个替代方案 - 我会减小问题并使用DFS而不是修改DFS。

给定一个图G = (V，E)，创建一个图G' =（V，E'），其中E' = {(u，v) | 存在w在V中，使得(u，w)和(w，v)都在E中} 换句话说 - 我们正在创建一个图G'，如果u到v有长度为2的路径，则具有边缘(u，v)。

鉴于该图，我们可以推导出以下算法[高级伪代码]：

1.从G创建G' 2.从源s在G'上运行DFS，并标记相同的节点DFS标记。

正确性和解决方案的时间复杂度分析：

复杂性： 复杂性显然为O(min{|V|^2,|E|^2} + |V|)，因为第一部分最多有min{|E|^2,|V|^2}条边在G'中，因此步骤2上的DFS在O(|E'| + |V|) = O(min{|V|^2,|E|^2} + |V|)中运行。 正确性： 如果算法发现从v0到vk有路径，则由于DFS的正确性 - 在G'上则存在v0->v1->...->vk的路径，因此存在一个长度为偶数的路径v0->v0 '->v1->v1'->...-> vk 在 G 上。 如果在G上有v0到vk的偶数长度路径，则让它是v0->v1->...->vk。然后v0->v2->...->vk是G'上的路径，并且将被DFS发现 - 从DFS的正确性来看。

作为一个附注： 减少问题而不是修改算法通常比修改算法更不容易出错，更易于分析和证明正确性，因此在可能的情况下应首选这些方法。

编辑：关于您的解决方案：分析表明它们几乎完全相同 - 唯一的区别在于我是预处理生成 E'，而您是在每次迭代中动态生成它。
由于您的解决方案是动态生成边缘 - 它可能会做一些重复的工作。但是，它最多只能绑定到作业上 |V| 次，因为每个顶点最多被访问一次。
为简单起见，假设 |E|=O(|V|^2)，从而为我们提供了运行时间的总上限 O(|V|^3) 的解决方案。
这也是一个下限，看看团的例子，在任何节点的visit()期间，算法都将执行O(|V|^2)以生成所有可能性，并且visit()其中之一的可能性，因为我们仅访问|V|个节点，所以我们获得总运行时间Omega(|V|^3)
由于我们发现该解决方案既是O(|V|^3)又是Omega(|V|^3)，因此总共是Theta(O(|V|^3))

- amit

---

谢谢你的回答，Amit :) 但是他们要求算法尽可能高效，我想他们指的是线性效率... 我只是想知道我的算法是否符合要求... - Chen Saranga

@ChenSaranga：如果你认为 |E| = O(|V|^2) [通常是这样假设的]，这和深度优先搜索（DFS）一样好。深度优先搜索的时间复杂度为O(|V| + |E|) = O(|V|^2 + |V|) = O(|V|^2)。在这种情况下，由于这个假设成立，该算法的时间复杂度也是O(|V|^2)。因为在这个假设下，min{|E|^2,|V|^2} = |V|^2。 - amit

@ChenSaranga：顺便说一下，我认为你提出的解决方案具有相同的时间复杂度，我需要再考虑一下，当我找到答案时，我会编辑回答并加上解释。 - amit

谢谢！你认为我能否给出算法的运行时间的紧密界限（theta）？ - Chen Saranga

@ChenSaranga：我认为它们在最坏情况下都是Theta(|V|^2)，以团为例-它们都需要进行Omega(|V|^2)次操作。[你的算法将在嵌套双循环中执行，我的算法将在第（1）和（2）阶段都执行]，因此-两者的下限均为Omega(|V|^2)，上限为O(|V|^2)，这使它们成为Theta(|V|^2)，这与DFS相同，这并不令人惊讶。 - amit

Answer 2

对于每个无向图G(V,E)，当以下条件成立时，我们应该将提到的图重构为二分图G'(V',E')：

• V' = V1 ∪ V2
• E'={(u1,v2):(u,v)∈E, u1∈V1, v2∈V2}
• V1={v1: v∈V}
• V2={v2: v∈V}

例如，这个图：

变成

在这张二分图上，我们应该运行BFS算法 - BFS(G'，S1')。 在运行BFS(G'，S1')之后，我们应该返回包含最短偶路径δ(s1,u1)长度的数组d。

- Tiouliandine Maxim