graph-theory - 2 つのノードが接続されているかどうかを判断する方法は?

Question

これがNP-Completeの問題に取り組んでいる可能性があることを懸念しています。あるのかないのか、どなたか回答いただけると幸いです。そして、イエスかノーかだけでなく、もっと多くの答えを探しています。理由を知りたいです。「これは基本的にこの問題 'x' であり、NP-Complete である/そうではない (wikipedia リンク)」と言えます。

(いいえ、これは宿題ではありません)

任意の無向グラフで 2 つの点が接続されているかどうかを判断する方法はありますか。たとえば、次の

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

ポイント A から M (「I」なし) は、開いたり閉じたりできるコントロールポイント (天然ガスパイプのバルブのようなもの) です。「+」はノード (パイプ T のようなもの) であり、ウェルとハウスもノードであると思います。

任意のコントロールポイント (例: C) を閉じた場合、井戸と家がまだ接続されているかどうかを知りたいです (他のコントロールポイントも閉じている可能性があります)。たとえば、B、K、D が閉じている場合でも、AEJFCGLM を通るパスがあり、C を閉じると井戸と家が切断されます。もちろん; D だけが閉じられた場合、C だけを閉じてもハウスは切断されません。

これを別の言い方をすれば、C は橋/切り口/地峡ですか?

各コントロールポイントをグラフの重みとして扱うことができます (オープンの場合は 0、クローズの場合は 1)。次に、Well と House の間の最短経路を見つけます (結果 >= 1 は、それらが切断されたことを示します。最短経路を見つけるためのアルゴリズムを短絡する方法もいくつかあります (たとえば、1 に達したら経路を破棄し、停止します)。井戸と家などをつなぐパスがあれば検索します。) そしてもちろん、あきらめる前にチェックするホップ数に人為的な制限を設定することもできます。

誰かがこの種の問題を以前に分類したに違いありません。名前がわかりません。

score 38 · Accepted Answer

あなたの説明は、最短経路を見つけるのではなく、2 つのノードが接続されているかどうかに関心があることを示しているようです。

2 つのノードが接続されているかどうかを確認するのは比較的簡単です。

Create two sets of nodes:  toDoSet and doneSet
Add the source node to the toDoSet 
while (toDoSet is not empty) {
  Remove the first element from toDoSet
  Add it to doneSet
  foreach (node reachable from the removed node) {
    if (the node equals the destination node) {
       return success
    }
    if (the node is not in doneSet) {
       add it to toDoSet 
    }
  }
}

return failure.

toDoSet と doneSet にハッシュテーブルなどを使用する場合、これは線形アルゴリズムだと思います。

このアルゴリズムは基本的に、マークアンドスイープガベージコレクションのマーク部分であることに注意してください。

score 7 · Accepted Answer

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithmを参照してください。これは、グラフに関連するすべての問題のワンストップショップです。あなたの問題は実際には二次時間で解けると思います。

score 5 · Accepted Answer

この問題にはダイクストラのアルゴリズムは必要ありません。これは、必要のないヒープを使用し、複雑さに log(N) の係数を導入するためです。これは単なる幅優先検索です。閉じたエッジをエッジとして含めないでください。

score 3 · Accepted Answer

最短経路を見つける問題は NP 完全ではありません。これは、最短経路問題 (元々は十分) と呼ばれ、さまざまなバリエーションを解決するためのアルゴリズムがあります。

2 つのノードが接続されているかどうかを判断する問題も NP 完全ではありません。いずれかのノードから開始する深さ優先検索を使用して、それが他のノードに接続されているかどうかを判断できます。

score 2 · Accepted Answer

隣接行列があると仮定します。

bool[,] adj = new bool[n, n];

i と j の間に開いているパスがある場合は bool[i,j] = true で、bool[i,i] = false です。

public bool pathExists(int[,] adj, int start, int end)
{
  List<int> visited = new List<int>();
  List<int> inprocess = new List<int>();
  inprocess.Add(start);

  while(inprocess.Count > 0)
  {
    int cur = inprocess[0];
    inprocess.RemoveAt(0);
    if(cur == end)
      return true;
    if(visited.Contains(cur))
      continue;
    visited.Add(cur);
    for(int i = 0; i < adj.Length; i++)
      if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i))
        inprocess.Add(i);
  }
  return false;
}

上記のアルゴリズムの再帰バージョン (Ruby で記述) を次に示します。

def connected? from, to, edges
  return true if from == to
  return true if edges.include?([from, to])
  return true if edges.include?([to, from])

  adjacent = edges.find_all { |e| e.include? from }
                  .flatten
                  .reject { |e| e == from }

  return adjacent.map do |a|
    connected? a, to, edges.reject { |e| e.include? from }
  end.any?
end

score 2 · Accepted Answer

あなたは解決策に向かっているように思えますが、問題を誤解している可能性があります。あなたが言うように、閉じたエッジに 1 の重みを与えると、ダイクストラのアルゴリズムhttp://en.wikipedia.org/wiki/Dijkstra%27s_algorithmを適用できます。これは O(E*lg(V)) の問題を解決するはずです

score 2 · Accepted Answer

2

NP完全ではなく、よく知られた解で解決 -ダイクストラのアルゴリズム

于 2008-12-09T21:43:24.283 に答える

score 1 · Accepted Answer

2 つのノードが接続されているかどうかを判断するだけでよい場合は、代わりにセットを使用できます。これは、グラフアルゴリズムよりも高速です。

グラフ全体をエッジに分割します。各エッジをセットに追加します。
次の反復では、手順 2 で作成したエッジの 2 つの外側ノード間にエッジを描画します。これは、元のエッジの元のセットに新しいノードを (対応するセットと共に) 追加することを意味します。（基本的に合体設定）
探している 2 つのノードが同じセットに含まれるまで、2 を繰り返します。また、ステップ 1 の後にチェックを行う必要があります (2 つのノードが隣接している場合に備えて)。

最初に、ノードはそれぞれのセットになります。

o   o1   o   o   o   o   o   o2
 \ /     \ /     \ /     \ /
 o o     o o     o o     o o
   \     /         \     /
   o o o o         o o o o 
      \               /
       o o1 o o o o o o2

アルゴリズムが進行してセットをマージするにつれて、入力が相対的に半分になります。

上記の例では、o1 と o2 の間にパスがあるかどうかを調べていました。すべてのエッジをマージした後、最後にこのパスを見つけました。一部のグラフには、個別のコンポーネント (接続されていない) が含まれている場合があり、これにより、最後に 1 つのセットを作成できなくなります。このような場合、このアルゴリズムを使用して接続性をテストし、グラフ内のコンポーネントの数を数えることさえできます。コンポーネントの数は、アルゴリズムが終了したときに取得できるセットの数です。

考えられるグラフ (上のツリーの場合):

o-o1-o-o-o2
  |    |
  o    o
       |
       o

score 0 · Accepted Answer

ダイクストラはやり過ぎです!! A からの幅優先検索を使用して、到達したいノードを検索するだけです。見つからない場合は、接続されていません。複雑さは、検索ごとに O(nm) であり、ダイクストラよりも小さくなります。

多少関連するのは、最大フロー/最小カットの問題です。それを調べてください、それはあなたの問題に関連しているかもしれません。

score -1 · Accepted Answer

ノードが別のノードに接続されているかどうかを確認することだけが必要な場合、グラフの最短経路アルゴリズムは過剰になります。それを実現する優れた Java ライブラリはJGraphTです。使い方はとても簡単です。整数グラフの例を次に示します。

public void loadGraph() {
    // first we create a new undirected graph of Integers
    UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);

    // then we add some nodes
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addVertex(4);
    graph.addVertex(5);
    graph.addVertex(6);
    graph.addVertex(7);
    graph.addVertex(8);
    graph.addVertex(9);
    graph.addVertex(10);
    graph.addVertex(11);
    graph.addVertex(12);
    graph.addVertex(13);
    graph.addVertex(14);
    graph.addVertex(15);
    graph.addVertex(16);

    // then we connect the nodes
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(5, 6);
    graph.addEdge(6, 7);
    graph.addEdge(7, 8);
    graph.addEdge(8, 9);
    graph.addEdge(9, 10);
    graph.addEdge(10, 11);
    graph.addEdge(11, 12);
    graph.addEdge(13, 14);
    graph.addEdge(14, 15);
    graph.addEdge(15, 16);

    // finally we use ConnectivityInspector to check nodes connectivity
    ConnectivityInspector<Integer, DefaultEdge> inspector = new ConnectivityInspector<>(graph);

    debug(inspector, 1, 2);
    debug(inspector, 1, 4);
    debug(inspector, 1, 3);
    debug(inspector, 1, 12);
    debug(inspector, 16, 5);
}

private void debug(ConnectivityInspector<Integer, DefaultEdge> inspector, Integer n1, Integer n2) {
    System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2)));
}

このライブラリは、すべての最短パスアルゴリズムも提供します。

graph-theory - 2 つのノードが接続されているかどうかを判断する方法は?

11 に答える 11

Related

Reference