即使长路径算法 [英] Even length path algorithm
问题描述
有人问我，我的家庭作业写一个高效的算法，发现有向图所有顶点具有的甚至长度的路径，他们从给定的顶点。
I was asked for my homework to write an efficient algorithm that finds all the vertices in a directed graph which have even length of path to them from the given vertex.
这是我的想法的：
（这是非常相似的访问DFS算法）
(It's very similar to "Visit" algorithm of 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)
我觉得它的工作原理，但我有很难计算它的效率，尤其是在图形与周期。你能帮助我吗？
I think it works but I'm having hard time calculating it's efficiency, especially when the graph is with cycles. Could you help me?
推荐答案
如果我可以建议一个选择 - 我会减少的问题，并使用，而不是修改DFS DFS
If I may suggest an alternative - I would have reduced the problem and use DFS instead of modifying DFS.
给定图 G =（V，E），cretae图 G'=（V，E'）其中， E'= {（U，V）|还有为w的v的（U，W）和（W，V）是E）
换言之 - 我们创建了一个图G'，其具有边（u，v）的当且仅当有长度为2到v的路径从u
Given a graph G = (V,E), cretae a graph G' = (V,E') where E'={(u,v) | there is w in V such that (u,w) and (w,v) are in E)
In other words - we are creating a graph G', which has edge (u,v) if and only if there is a path of length 2 from u to v.
由于图中，我们可以得出以下的算法[高水平的伪code]
Given that graph, we can derive the following algorithm [high level pseudo-code]:
- 创建G'给G
- 从源头
取值运行DFS在G'，并标记相同的节点DFS显着。
- Create G' from G
- run DFS on G' from the source
s, and mark the same nodes DFS marked.
溶液的正确性和时间复杂度分析：
Correctness and time complexity analysis of the solution:
的复杂性：
复杂性显然是 0（分{| V | ^ 2，| E | ^ 2} + | V |）由于部分1， - 因为有最多分{| E | ^ 2，| V | ^ 2} G中边缘，所以DFS的步骤2运行在 O（| E'| + | V |）= 0（分{| V | ^ 2，| E | ^ 2} + | V |）
Complexity:
The complexity is obviously O(min{|V|^2,|E|^2} + |V|), because of part 1 - since there are at most min{|E|^2,|V|^2} edges in G', so DFS on step 2 runs in O(|E'| + |V|) = O(min{|V|^2,|E|^2} + |V|)
正确性：
如果算法发现有从V0到VK的路径，然后从DFS的正确性 - 有一个路径V0-> V1 - > ...-> VK上G'，所以有一个路径 V0-＆GT; V0' - ＆GT; V1-＆GT; V1 - ＆GT; ...-＆GT; VK G上甚长
如果有关于 V0 的路径 VK ，让它成为 V0-＆GT; V1-＆GT; ...-＆GT; VK 。那么 V0-＆GT; V2-＆GT; ...-＆GT; VK 是 G'，路径由DFS发现 - 从DFS的正确性
Correctness:
If the algorithm found that there is a path from v0 to vk, then from the correctness of DFS - there is a path v0->v1->...->vk on G', so there is a path v0->v0'->v1->v1'->...->vk of even length on G.
If there is a path of even length on G from v0 to vk, let it be v0->v1->...->vk. then v0->v2->...->vk is a path on G', and will be found by DFS - from the correctness of DFS.
作为一个方面说明：
减少问题，而不是修改算法通常较少vulnurable到错误，也更容易分析和证明的正确性，所以你通常应该preFER这些过修改算法，在可能的情况。
As a side note:
Reducing problems instead of modifying algorithms is usually less vulnurable to bugs, and easier to analyze and prove correctness on, so you should usually prefer these over modifying algorithms when possible.
编辑：关于您的解决方案：嗯，分析就说明它们都是pretty的很多相同的 - 除了我正在生成 E'为pre-处理，而你在飞行中产生的，在每次迭代中。
由于您的解决方案产生的飞边 - 这可能做了一些工作，曾多次。然而，它是有界到作业至多 | V | 倍以上，因为各顶点是被访问最多一次。
假设 | E | = O（| V | ^ 2）为简单起见，给我们总的上限 0的运行时间（| V | ^ 3）为您的解决方案。
这也是一个下限，看一个访问（）所有节点时，算法会做 O（| V | ^ 2）来生成所有的可能性，而访问（）之一的可能性，因为我们参观完全 | V | 节点，我们得到总执行时间欧米茄（| V | ^ 3）
因为我们找到了解决方案既 O（| V | ^ 3）和欧米茄（| V | ^ 3），这是总的
regarding your solution: Well, analysing it shows they are both pretty much identical - with the exception of I was generating E' as pre-processing, and you are generating it on the fly, in each iteration.
Since your solution is generating the edges on the fly - it might to doing some work more then once. However, it is bounded to the job at most |V| times more, since each vertex is being visited at most once.
Assuming |E| = O(|V|^2) for simplicity, giving us total an upper bound for the run time of O(|V|^3) for your solution.
It is also a lower bound, look at the example of a clique, During each visit() of any node, the algorithm will do O(|V|^2) to generate all possibilities, and visit() one of the possibilities, since we visit exactly |V| nodes, we get total run time of Omega(|V|^3)
Since we found the solution is both O(|V|^3) and Omega(|V|^3), it is total of Theta(O(|V|^3))
这篇关于即使长路径算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
