Even length path algorithm

Question

[我被要求做我的作业来编写一种有效的算法，该算法可在有向图中找到从给定顶点到它们的路径具有[[even length的路径的所有顶点。

这是我的想法：

（与DFS的“访问”算法非常相似）

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)

我认为它可行，但是我很难计算出它的效率，尤其是当图形带有循环时。您能帮我吗？

Answer 1

如果我可能会建议替代方法-

我会减少问题并使用DFS而不是修改DFS。

给出图G = (V,E)，创建图G' = (V,E')，其中E'={(u,v) | there is w in V such that (u,w) and (w,v) are in E)换句话说-我们正在创建一个图形G'，当且仅当存在从u到v的长度为2的路径时，它才具有边（u，v）。

给出该图，我们可以得出以下

算法[高级伪代码]

：

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

---

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

复杂度：

显然，由于第1部分，复杂度为O(min{|V|^2,|E|^2} + |V|)-因为G'中最多有min{|E|^2,|V|^2}个边，所以步骤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的正确性对其进行查找。

作为旁注：

减少问题而不是修改算法通常对漏洞的危害较小，并且更易于分析和证明其正确性，因此，在可能的情况下，与修改算法相比，通常应优先考虑这些问题。

EDIT：

关于您的解决方案：嗯，分析发现它们几乎相同-除了我正在生成E'作为预处理，而您正在即时生成它时，迭代。由于您的解决方案是动态生成边缘的，因此可能需要做一些工作，然后再做一次。但是，由于每个顶点最多被访问一次，因此它最多与作业绑定|V|次。为简单起见，假设|E| = O(|V|^2)为您的解决方案提供了O(|V|^3)运行时间的上限。这也是一个下限，以clique的示例为例，在任何节点的每个visit()期间，算法都会执行O(|V|^2)来生成所有可能性，而visit()则是其中一种可能性，因为我们访问了确切地说是|V|个节点，我们得出的总运行时间为Omega(|V|^3)由于我们发现解既是O(|V|^3)又是Omega(|V|^3)，所以总共是Theta(O(|V|^3))

Answer 2

对于每个无向图G（V，E），当出现以下情况时，我们应将上述图重建为二分图G'（V'，E'）：