1

グラフG =(V, E)、V に属するサブセットS 、およびSに属さないGのすべての頂点を含むサブセットS'が与えられた場合、 SとSのノード間のエッジの総数をカウントしたい' .

この問題を O(n^2) よりも複雑に解決できるアルゴリズム。

4

1 に答える 1

3

「O(n^2) より低い」とは、O(|E|) のようなものを意味すると仮定すると、ハッシュ構造を使用してそれを行うことができます。S のすべてのノードをハッシュセットに入れ、G のすべてのエッジを反復処理し、エッジごとに両方のエンドポイントがハッシュセットに含まれているかどうかを確認します。ハッシュセットの構築は O(n) であり、適切なハッシュ関数を想定すると、すべてのエッジの処理は O(|E|) です。の場合|E| in Omega(n^2)、O(n^2) を超えることはできません。

編集：2つのこと：

  • |E| in Omega(n^2)グラフに使用する表現によっては、うまくいかないという最後のステートメントが間違っています。をSE' = {e = {s,v} in E | s in S}の少なくとも 1 つのエッジに付随するエッジのセットとします。インシデント/隣接リストがある場合、S のノードに付随するエッジを反復処理するだけで、複雑さを O(|E'|) に改善できます。および |E'| |E| よりも小さい場合があります。S に依存する非定数係数によって。
  • このアプローチは、S と V\S の間を走るエッジを見つけることに簡単に変換できます。2 つのハッシュセットを作成し、S のすべてのノードを最初のノードに配置し、V\S のすべてのノードをもう一方のノードに配置します。次に、一方のハッシュセットに一方のエンド ノードがあり、もう一方のハッシュセットにもう一方のエンド ノードがあるエッジのみを受け入れるように条件を調整します。誘導された両方のサブグラフのサイズと密度に応じて、セット インシデント内のノードが含まれるエッジ インシデントをより少ないエッジで反復処理するだけで成果が得られるはずです。
于 2013-06-14T12:50:28.507 に答える