3

頂点uから O(|V|+|E|) 時間の複雑さ (DFS に基づく) を持つ他の頂点までの有向グラフのエッジを見つけるアルゴリズムがあります。O(|V||E|) 内の任意の 2 つの頂点uとvの間のエッジを見つけるアルゴリズムを開発する必要があります。

これを達成するための提案やヒントはありますか?

すべての頂点に対して DFS-Visit を繰り返すと、最初に頂点が白くなり、次の呼び出しでは何も実行されません。その前に色をリセットすると、アルゴリズムは O(|V|^2 + |V||E|) になります。

よろしくお願いします！

4

1 に答える 1

3

次のように、アルゴリズムを使用して必要な複雑さを達成できるサブ問題に問題を分割します。

  • 構造グラフ (基になる無向グラフ) で DFS を使用し、その中のすべての連結要素を見つけます。それらを (V1,E1), (V2,E2), ...., (Vk,Ek) とする
  • そのようなコンポーネントごとに、アルゴリズムを実行します。異なるコンポーネントにある 2 つのノード間にブリッジがないことは明らかです。

複雑さは次のとおりです。
ステップ 1はO(V+E)- DFS です。
ステップ 2 :

  • 開発したアルゴリズムを各ノードから繰り返し使用して、各コンポーネントのブラック ボックスとして使用するため、コンポーネントiの複雑さは次のようになります。O(V_i^2 + V_i*E_i)
  • 各コンポーネントでi: E_i >= V_i -1(それ以外の場合は接続されていないため、ツリーには|V|-1エッジがあります) O(ViEi + Vi^2) = O(ViEi)。
  • したがって、このステップの複雑さは ですO(V1E1 + V2E2 + ... + VkEk)。

  • for each i E_i <= E、したがって複雑さは次の場合よりも悪くないことに注意してください。

    O(V1E + V2E + ... + VkE)  = O(E *(V1+V2+ ... + Vk)) = O(VE)

したがって、必要に応じて、全体の複雑さはO(VE)です。

于 2013-08-06T12:46:58.330 に答える