짝수 길이의 경로 알고리즘

Question

주어진 그래프에서 길이를 가진 모든 정점을 찾은 효율적인 알고리즘을 숙제하도록 요청 받았습니다. 주어진 정점에서 길이가입니다.

나는 그것이 작동 생각

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의 알고리즘을 "방문"매우 유사)하지만 특히, 그것은 효율성의 계산 힘든 시간을 보내고 있습니다 :

이

내가 무슨 생각입니다 그래프에 사이클이있을 때. 당신이 나를 도울 수?

Answer 1

내가 대안을 제안 할 수도 있습니다 - DFS를 수정하는 대신 DFS를 사용하고 문제를 줄였습니다.. E'={(u,v) | there is w in V such that (u,w) and (w,v) are in E) 말하면
여기서 그래프 G = (V,E) 주어

, 그래프 G' = (V,E')을 cretae - 우리 에지를 갖는다 그래프 G '를 만드는 (U, V)에서 U 길이 (2)의 경로가 경우만 V에 그래프, 우리는 다음과 같은 알고리즘 [높은 수준의 의사 코드] 유도 할 수 있음을 감안할 때

:.의 S에서

1. 는 'G G에
2. 실행 DFS에서'G 만들기를 ource s 및 DFS로 표시된 동일한 노드를 표시하십시오.

---

정확성 용액의 시간 복잡도 분석 :

복잡성 : 복잡성 때문에 제 1 부의 분명 O(min{|V|^2,|E|^2} + |V|) 인 - G 가장 min{|E|^2,|V|^2} 에지에 있기 때문에 '이므로 O(|E'| + |V|) = O(min{|V|^2,|E|^2} + |V|)

정확성 단계에 DFS이 실행 :
알고리즘에 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에서 찾습니다. 보조 노트로

: 대신 수정 알고리즘의
감소 문제는 일반적 분석에 대한 정확성을 입증 할 적은 버그 vulnurable, 쉽게, 그래서 당신은 가능한 한 알고리즘을 수정을 통해이 선호 일반적으로해야한다. 솔루션에 대한 :

는

편집 글쎄, 그것을 분석하는 것은 그들이 모두 거의 동일 보여줍니다 - 나는 사전 처리로 E'를 생성 한을 제외하고 각 반복에서, 그것을 즉석에서 생성된다.
솔루션이 즉시 가장자리를 생성하므로 작업을 한 번 더 수행 할 수 있습니다.그러나 각 버텍스는 최대 한 번만 방문되기 때문에이 값은 최대 |V| 배 이상으로 제한됩니다.
단순화를 위해 |E| = O(|V|^2)을 가정하면 솔루션의 런타임에 대한 상한선은 O(|V|^3)입니다. 의 예를 살펴보면 모든 노드가 visit() 인 동안 알고리듬은 노드를 방문하기 때문에 모든 가능성을 생성하기 위해 O(|V|^2)을 수행하고 가능성을 생성하는 것은 visit() 일 수 있습니다. "모든 다른 주어진 정점에서 짝수 길이 경로로 모든 정점을 발견 : 우리가 솔루션이 모두 O(|V|^3) 및 Omega(|V|^3)입니다 발견 이후 Omega(|V|^3)
의 총 실행 시간, 그것은 Theta(O(|V|^3))