偶数長のパスアルゴリズム

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を使用することになりました。グラフG = (V,E)を考える

、E'={(u,v) | there is w in V such that (u,w) and (w,v) are in E)
すなわちグラフG' = (V,E') cretae - Uから長さ2の経路が存在する場合にのみ（V、U）我々はエッジを有するグラフG」を作成しているが

Gを作成 '、G
1. からGの実行DFSさんから：グラフ、我々は以下のアルゴリズム[ハイレベルの擬似コード]を導くことができることを考えると、V

   へ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|)

正しさのステップ2の実行上のDFS 0アルゴリズムがv0からvkまでのパスがあることが分かったら、DFSの正当性から、G0にv0-> v1-> ...-> vkというパスがあるので、偶数のパスv0->v0'->v1->v1'->...->vk Gの長さ
Gに偶数長のパスがある場合は、v0からvkまでv0->v1->...->vkとします。 v0->v2->...->vkはG'のパスであり、DFSの正確性からDFSによって検出されます。サイドノートとして

：
問題を減らす代わりに、アルゴリズムを変更するには、通常のバグが少ないvulnurableあり、かつ容易に正確に分析し、証明するために、あなたは、通常時に可能なアルゴリズムを修正する上でこれらを好む必要があります。

EDIT：あなたのソリューションに関する：まあ、それを分析することは、彼らは両方ともほとんど同じです示して - 私は前処理としてE'を生成し、あなたが各繰り返しで、その場でそれを生成しているのを除いて。
あなたのソリューションはその場でエッジを生成しているので、何度か何らかの作業を行うことがあります。しかし、多くの場合、各頂点がたかだか1回しか訪問されていないため、ジョブには最大で|V|倍に制限されています。
簡略化のため|E| = O(|V|^2)とすると、あなたの解決方法の実行時間の上限はO(|V|^3)になります。
cliqueの例を参照してください。いずれのノードの各visit()の間に、アルゴリズムはというノードを正確に訪問するため、可能性をすべて生成するためにO(|V|^2)と可能性を生成するためにvisit()を実行します。 「他のすべてに、指定された頂点から偶数長のパスを持つすべての頂点を見つける：Omega(|V|^3)
の総実行時間、我々は解決策がO(|V|^3)とOmega(|V|^3)の両方で見つかったので、それはTheta(O(|V|^3))