5

1 つ以上のノードがソースとして区別される有向グラフ (必ずしも接続されている必要はありません) があります。いずれかのソースからアクセス可能なノードは、「点灯」していると見なされます。ここで、エッジの 1 つが削除されたとします。問題は、以前に点灯していて、もう点灯していないノードを特定することです。

都市の電力システムのようなアナロジーが考えられるのではないでしょうか。

4

5 に答える 5

7

これは「動的グラフの到達可能性」の問題です。次の論文が役に立ちます。

有向グラフの完全に動的な到達可能性アルゴリズムで、更新時間がほぼ線形です。リアム・ロディティ、ユリ・ズウィック。コンピューティングの理論、2002。

これにより、O(m * sqrt(n)) 回の更新 ( amortized ) と O(sqrt(n)) 回のクエリ (m はエッジの数、n はエッジの数)のアルゴリズムが得られます。ノード）。グラフが非周期的である場合、これは O(m) 回の更新 ( amortized ) および O(n/log n) 回のクエリに改善できます。

問題の特定の構造を考えると、またはスペースを時間と交換することで、これよりもうまくいく可能性は常にあります。

于 2009-01-05T16:12:43.300 に答える
1

これはあなたの宿題ですか？

最も簡単な解決策は、元のグラフの開始時にDFS（ http://en.wikipedia.org/wiki/Depth-first_search）またはBFS（http://en.wikipedia.org/wiki/Breadth-first_search ）を実行することです。ソースノードから。これにより、元のすべての点灯ノードが取得されます。

ここで、問題のエッジを削除します。DFSをもう一度実行します。まだ点灯しているノードを使用できます。

最初のセットに表示されるが、2番目のセットには表示されないノードを出力します。

これは漸近的に最適なアルゴリズムです。2つのDFS（またはBFS）を実行し、O（n + m）時間とスペース（n =ノードの数、m =エッジの数）を取り、複雑さを支配するからです。入力を読み取るには、少なくともo（n + m）の時間とスペースが必要であるため、アルゴリズムが最適です。

ここで、いくつかのエッジを削除したい場合、それは興味深いでしょう。この場合、動的データ構造について話します。これはあなたが意図したことですか？

編集：コメントを考慮に入れて：

  • 検索中に到達不能な接続コンポーネントのノードに到達しないため、接続されていないことは問題ではありません。
  • すべてのノードから一度にDFSまたはBFSを実行するスマートな方法があります（BFSについて説明します）。それらすべてを最初にスタック/キューに配置する必要があります。

開始ノードのいずれかから到達可能なすべてのノードを検索するBFSの擬似コード：

キューq=[すべての開始ノード]
while（qは空ではありません）
{{
   x = q.pop（）
   forall（xのyネイバー）{
      if（yは訪問されなかった）{
         訪問済み[y]=true
         q.push（y）
      }
   }
}

キューをスタックに置き換えると、一種のDFSが得られます。

于 2009-01-05T15:53:58.800 に答える
1

単に「点灯」または「消灯」する代わりに、ノードの電源または点灯元のノードのセットを保持し、空のセットを持つノードを「点灯しない」と見なし、空でないセットを持つノードを「点灯している場合、エッジを削除するには、ターゲット ノードのセットからソース ノードを削除するだけです。

編集：これを忘れてください：そして、セット内の最後のlit-from-nodeを削除する場合は、エッジをトラバースし、セットから「unlit」したばかりのノードを削除します（おそらくそこからトラバースするなど）

EDIT2（tafaの言い換え）：最初に：元の質問を読み違えて、各ノードについて、点灯または消灯がすでに知られていると述べていると思いましたが、今読み直したところ、言及されていませんでした。

ただし、ネットワーク内の各ノードに対して、それが照らされたノードを含むセットを保存すると、削除されたエッジからグラフを簡単にトラバースして、照らされた/照らされていない参照を修正できます。たとえば、次のようなノード A、B、C、D がある場合: (アスキー アートでの不十分な試み)

A -> B >- D
 \-> C >-/

次に、ノード A では、それがソースである (したがって、それ自体で照らされている) ことを保存し、B と C の両方で、A によって照らされていることを保存し、D では、A と C の両方によって照らされていることを保存します。 .

次に、B から D へのエッジを削除するとします。D では、lit-source-list から B を削除しますが、A によってまだ照らされているため、点灯したままです。次に、A から C へのエッジをその後削除するとします。 C のセットから削除されたため、C は点灯しなくなりました。次に、C で発生したエッジをトラバースし、D のセットから C を削除します。これも現在は消灯しています。この場合はこれで終わりですが、セットがもっと大きい場合は、D から続けます。

このアルゴリズムは、エッジの削除または追加によって直接影響を受けるノードにのみアクセスするため、(各ノードで必要な追加のストレージは別として) 最適に近いはずです。

于 2009-01-05T15:48:06.547 に答える
0

グラフを作成している間、エッジに接続されたソース ノードの情報を保持します (エッジにソース S1 および S2 への接続がある場合、そのソース リストには S1 および S2 が含まれます)。出力エッジ。エッジが削除されると、ノードの入力エッジを考慮して、そのエッジのターゲット ノードの出力エッジを更新します。そして、DFS または BFS を使用して、更新されたエッジのすべてのターゲット ノードをトラバースします。(周期グラフの場合は、マーキングを検討してください)。グラフの更新中に、ソース接続を持つエッジのないノードを見つけることもできます (点灯 -> 点灯していないノード)。ただし、複数のエッジを同時に削除したい場合は、同じエッジを何度もトラバースする可能性があるため、良い解決策ではない可能性があります。

于 2009-01-05T16:13:21.410 に答える
0

グラフはどのくらいの大きさで、どの程度つながっていますか? ソース ノードから他のすべてのノードへのすべてのパスを保存し、そのノードへのすべてのパスに削除エッジの 1 つが含まれるノードを探すことができます。

編集：この説明を少し拡張します

各ソース ノードから DFS を実行します。各ノードに生成されたすべてのパスを追跡します (頂点ではなくエッジとして、その順序ではなく関係するエッジのみを知る必要があるため、ビットマップを使用できます)。ソースからノードへのパスの数をノードごとにカウントします。

次に、パスを反復処理します。削除されたエッジを含むパスを削除し、そのノードのカウンターを減らします。ノード カウンターがゼロにデクリメントされた場合、それは点灯していましたが、現在は点灯していません。

于 2009-01-05T15:45:57.490 に答える