2

この問題を解決しようとしていますが、すぐに解決できません。

要するに、グラフ (有向) があり、どのノード (選択するノードのセットが与えられている) から最も多くのノードにアクセスできるかを調べたいと考えています。簡単な実装は、すべてのノードから DFS/BFS を実行し、アクセスできる数を確認することです。しかし、グラフに5000を超えるノードがあるため、遅すぎます。5000 BFS/DFS の実行には非常に長い時間がかかります。

一方で、この問題は Disjoint Set データ構造と関係があるのではないかと感じていますか? しかし、前述のルールのいくつかを分離したセットの実装のように、そのように定式化することはできません。

誰かがこの問題にアプローチする方法についてヒントを与えることができますか?

4

1 に答える 1

3
  1. Tarjan のアルゴリズム (O(V+E))を使用して強連結成分(SCC) を見つけ、SCC グラフを作成します。
  2. 結果の SCC グラフをトポロジー的に並べ替えます (これはDAGです)。
  3. 最後から最初の順に、各コンポーネントから到達可能なノードの数を見つけます。
  4. 最大数のノードに到達できる SCC にあるノードを選択します。

ステップ 3 - 詳細化:

(明確にするために、元のグラフの頂点を「ノード」、SCC グラフの頂点を「頂点」と表記します)。

ステップ 3 では、SCC の各頂点から到達可能なノードの数を見つけたいと考えています。これは、このセットを明示的に見つけるか、ノードの数だけを見つけることで実行できます。

  1. 各頂点から到達可能なノードのセットを明示的に見つける:
    これは非常に簡単です。各頂点には関連するノードのセットがあり、SCC グラフの先頭のすべてのエッジでユニオンを実行して、各頂点に関連付けられたセットを見つける必要があります。現在の頂点から。
  2. 包含/除外を使用して到達可能なノードの数を見つける:
    包含/除外は、セットに繰り返しがある可能性があるセットの和集合のサイズをカウントするために使用される手法です。たとえば、2 つのセットがある場合、結合のサイズは です|A|+|B|- |A[intersection]B|。
    3 つのセット A、B、C の場合: |A|+|B|+|C|-|A[intersrction]B| - |A[intersection]C| - |B[intersection]C + |A[intersection]B[intersection]C|
    (など)
    包含/除外を使用 - セットは前のノードであり、交差は後で同じ頂点にリンクする 2 つの異なる頂点に基づいています。
于 2014-03-17T10:45:18.250 に答える