language-agnostic - 完全な到達可能性をテストする最良の方法

Question

ノードのセットがあり、それぞれが少なくとも 1 つの他のノードに接続されています。各ノードが他のすべてのノードから到達できるように接続されているかどうかを知りたいです。例えば：

1--2
   |
3--4

対：

1--2

3--4

この種の到達可能性テストは、正確なカバー問題の観点から投影できると確信していますが、その方法について頭を悩ませているようには見えません。これを行う方法について、ポインタ、ドキュメント、Web サイトなどを持っている人はいますか? 例は非常に価値があります。

更新:この種のテストにははるかに効率的なアルゴリズムがあるように思われるため、私の無知が裏切りました。もしお持ちでしたら、それを教えてください。

Answer 1

• 任意のノードから開始し、深さ/幅優先のトラバーサルを実行します
• 訪問したノードの数を数えます (もちろん、どのノードにも 2 回アクセスしないでください!)
• カウントされた数と合計数を比較する

Answer 2

この論文に示されているように、接続を動的に (つまり、エッジの挿入/削除の下で) 維持するための高速な (しかし非常に複雑な) アルゴリズムもあります。

基本的な考え方は、スパニング ツリーを維持することです。簡単なケースは、エッジの挿入と、非スパニング ツリー エッジの削除です。問題は、スパニング ツリー エッジを削除する場合です。これは、接続が保証されていないためです。壊れた部分を接続する代替ルートを効率的に検索する必要があります。そうしないと、グラフが切断されます。