performance - 偶长路径算法

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)

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

Answer 1

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

给定一个图 G = (V,E)，创建一个图 G' = (V,E') 其中 E'={(u ,v) | V 中有 w 使得 (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|)，因为第 1 部分 - 因为最多 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) 的总运行时间上限。
也是一个下界，看例子a clique ，在任何节点的每次visit()期间，算法都会做O(|V|^2)来生成所有的可能性，而visit() 一种可能性，因为我们恰好访问了 |V| 个节点，所以我们得到了 Omega(|V|^3) 的总运行时间
因为我们发现解既是O(|V|^3)又是Omega(|V|^3)，所以它是的总和Theta(O(|V|^3))