这就是我的想法：
(它与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)
我认为它有效,但我很难计算它的效率,特别是当图表是循环时.你可以帮帮我吗？
如果我可以建议一个替代方案 – 我会减少问题并使用DFS而不是修改DFS.给定图G =(V,E),得到图G’=(V,E’),其中E’= {(u,v)|在V中有w,使得(u,w)和(w,v)在E中
换句话说 – 我们正在创建一个图G’,当且仅当存在从u到v的长度为2的路径时才具有边(u,v).
给定该图,我们可以推导出以下算法[高级伪代码]：
>从G创建G’
>从源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′ – > …-> G上的偶数长度的vk
如果在G上从v0到vk存在偶数长度的路径,则将其设为v0-> v1-> …-> vk.然后v0-> v2-> …-> vk是G’上的路径,并且将由DFS找到 – 来自DFS的正确性.
作为旁注：
减少问题而不是修改算法通常对错误不太敏感,并且更容易分析并证明正确性,因此您应该在可能的情况下优先考虑修改算法.
编辑：关于你的解决方案：嗯,分析它显示它们几乎完全相同 – 除了我生成E’作为预处理,并且你在每次迭代中动态生成它.
由于您的解决方案正在动态生成边缘 – 它可能会做一些工作多一次.但是,最多的工作是| V |因为每个顶点最多被访问一次,所以会更多.
假设| E | = O(| V | ^ 2)为简单起见,给出了总解决方案的O(| V | ^ 3)运行时间的上限.
它也是一个下界,看看clique的例子,在任何节点的每次访问()期间,算法都会做O(| V | ^ 2)来生成所有可能性,并访问()其中一种可能性,因为我们正好访问| V |节点,我们得到Omega的总运行时间(| V | ^ 3)由于我们发现解是O(| V | ^ 3)和Omega(| V | ^ 3),所以它是Theta的总和(O(| V | ^ 3))