甚至长度路径算法

Question

我被要求编写一个有效的算法来查找有向图中的所有顶点,这些顶点具有从给定顶点到它们的路径的均匀长度.

这就是我的想法:

(它与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)当且仅当存在从u到v的长度为2的路径时.

给定该图,我们可以推导出以下算法[高级伪代码]:

1. 从G创建G'
2. 从源上运行G'上的DFS s,并标记标记的相同节点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)解决方案运行时间的上限.
这也是一个下界,看一个的例子集团,在每一个visit()任意节点,算法会做O(|V|^2)产生的所有可能性,visit()其中一种可能性,因为我们参观正好|V|节点,我们得到的总运行时间Omega(|V|^3)
因为我们发现解决方案是O(|V|^3)和Omega(|V|^3),它是总和Theta(O(|V|^3))