Geek asks and answers

Even the length path algorithm

I was offered my homework to write an efficient algorithm that finds all the vertices in a directed graph that even have a path length to them from a given vertex.

This is what I was thinking:

(It is very similar to the DFS "Visit" algorithm)

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 this works, but it's hard for me to determine its effectiveness, especially when the schedule is with cycles. could you help me?

+3
source share
1 answer

If I can offer an alternative - I would reduce the problem and use DFS instead of modifying DFS .

G = (V,E), cretae 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
  • DFS G ' s , DFS.

:

: , , O(min{|V|^2,|E|^2} + |V|), - 1 - G ' min{|E|^2,|V|^2}, DFS 2 O(|E'| + |V|) = O(min{|V|^2,|E|^2} + |V|)

:
, v0 vk, DFS - v0- > v1 → ...- > vk G ', 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) .
, clique. visit() node O(|V|^2) visit() , |V|, Omega(|V|^3) O(|V|^3), Omega(|V|^3), Theta(O(|V|^3))

+4

More articles:


All Articles