5

与えられた頂点からそれらへのパスの長さが等しい、有向グラフ内のすべての頂点を見つける効率的なアルゴリズムを書くように宿題を求められました。

これは私が考えたことです：

(DFSの「Visit」アルゴリズムとよく似ています)

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)

うまくいくと思いますが、特にグラフにサイクルがある場合、効率を計算するのに苦労しています。私たちを手伝ってくれますか？

4

2 に答える 2

6

別の方法を提案できるとしたら、問題を減らして、 DFS を変更する代わりに DFS を使用したでしょう。

グラフが与えられた場合、グラフG = (V,E)を作成します。つまり、u から v までの長さ 2 のパスがある場合に限り、エッジ (u,v) を持つグラフ G' を作成します。G' = (V,E')E'={(u,v) | there is w in V such that (u,w) and (w,v) are in E)

そのグラフを考えると、次のアルゴリズム [高レベルの擬似コード]を導き出すことができます。

  1. GからG'を作る
  2. ソースから G' で DFS を実行しs、同じノードに DFS のマークを付けます。

ソリューションの正確性と時間の複雑さの分析:

複雑さ:O(min{|V|^2,|E|^2} + |V|)パート 1 のため、 複雑さは明らかmin{|E|^2,|V|^2}にO(|E'| + |V|) = O(min{|V|^2,|E|^2} + |V|)

正しさ:
アルゴリズムが v0 から vk へのパスがあることを検出した場合、DFS の正しさから - G' にパス v0->v1->...->vk があるためv0->v0'->v1->v1'->...->vk、偶数のパスがあります。 G 上の長さ。 からまで
の長さが偶数のパスがある場合、それを とする。thenは 上のパスであり、DFS の正しさから DFS によって検出されます。Gv0vkv0->v1->...->vkv0->v2->...->vkG'

補足として:
アルゴリズムを変更する代わりに問題を減らすことは、通常、バグに対する脆弱性が少なく、分析と正確性の証明が容易であるため、通常、可能であればアルゴリズムを変更するよりもこれらを優先する必要があります。

編集:あなたのソリューションについて:まあ、それを分析すると、それらは両方ともほとんど同じであることがわかります-私がE'前処理として生成していたことを除いて、あなたはそれを各反復でその場で生成しています.
あなたのソリューションはオンザフライでエッジを生成しているため、いくつかの作業を複数回行う必要がある場合があります。|V|ただし、各頂点は多くても 1 回しかアクセスされないため、多く の場合、ジョブにバインドされます。簡単にするために、ソリューションの実行時間の上限を合計
すると仮定します。 これは下限でもあります.クリークの例を見てください. 任意のノードのそれぞれの間に, アルゴリズムはすべての可能性を生成するために行います.|E| = O(|V|^2)O(|V|^3)
visit()O(|V|^2)visit()|V|可能性の 1 つです。正確にノードを訪問するのでOmega(|V|^3)
、総実行時間はO(|V|^3)Omega(|V|^3)Theta(O(|V|^3))

于 2012-04-17T12:16:39.390 に答える