3

整数で表される頂点を持つ無向グラフを検索して結合するユニオン検索アルゴリズムを実装しました。コンポーネントが「接続」されているかどうか、つまり、あるノードから別のノードに移動するパスがあるかどうかを確認する方法について、誰かが擬似コードまたはアイデアを持っているかどうかを知りたいです。たとえば、次の頂点があります。

7（ソース頂点）、9（宛先頂点）および8（ソース頂点）、7（宛先頂点）はすべて接続されています。ただし、3（ソース頂点）、5（宛先頂点）のようなものは、前のコンポーネントのセットに接続されません。誰かが私を正しい方向に導くか、これをテストする方法について私にアイデアを与えることができますか？ありがとう！

4

2 に答える 2

0

はい、2つのノードが同じルートを持っているかどうかをテストするだけです。グラフを作成するときにパス圧縮を使用すると、これは非常に高速であることがわかります。

クラスカルのアルゴリズムの実装に取り​​入れようとしているからだと思います。接続されているすべてのコンポーネントを見つけたら、各互いに素なセットからの各素集合を示す出力を並べ替えたいと思います。ご迷惑をおかけして申し訳ありませんが、可能であれば、意味を説明するための疑似コードがありますか？

セットは、共通のルートノードによってすでに識別されています。 すべてのユニオンを実行すると、それぞれの一意のセットに単一のルートが作成されます。したがって、各ノードを実行して呼び出しますFind。これはどう：

typedef std::list< Node* > TNodeList;
typedef std::map< Node*, TNodeList > TSetMap;

TSetMap mysets;

// Assuming you have nodes stored in the list type I declared above...
for( TNodeList::iterator n = nodes.begin(); n != nodes.end(); n++ )
{
    Node *thisnode = *n;
    Node *rootnode = Find(thisnode);

    // Add to list for root.  Using the [] operator on map will create a new
    // list if none exists for that node.
    mysets[rootnode].push_back(thisnode);
}

これで、すべてのセットを個別のリストとして含むマップが作成され、好きなことを実行できます...

std::cout << "Number of disjoint sets: " << mysets.size() << std::endl;
int count = 0;

for( TSetMap::iterator s = mysets.begin(); s != mysets.end(); s++ )
{
    TNodeList & nl = s->second;
    std::cout << "Set " << ++count << " contains " << nl.size() << " nodes\n";
}

これらすべての呼び出しをFind効率的に行うには、関数にパス圧縮を実装する必要がありますUnion。

于 2012-11-12T01:31:41.170 に答える
0

グラフが有向であるかのように聞こえますが、その場合、union-findは実際には接続に役立ちません（正しく思い出せば、クラスカルのアルゴリズムで最小スパニングツリーを決定するために一般的に使用されますが、これは無向グラフ用です）。グラフが無向である場合は、Union-Findを使用して、すべてのノードで2パスを使用して接続されているすべてのコンポーネントを判別できます。

  1. ノードごとに、ノードとエッジを持つすべてのノードを結合します。
  2. 各ノードについて、代表ノードを見つけて、それが報告されたかどうかを確認します。そうでない場合は、それを報告し、たとえば、std::set<T>（T代表者を識別するために使用されるタイプであるために）に入れます。

実際には、DFSのような検索アルゴリズムを使用する方が簡単な場合があります。

  1. 各ノードについて、すでにアクセスされているかどうかを確認します。
  2. 訪問されなかった場合、それは新しい接続コンポーネントの一部です。ノードでDFSを開始し、見つかったすべてのノードにマークを付けます（接続されたコンポーネントの一部として検出されたすべてのノードを報告することもできます）。

このアルゴリズムには、O（n）でもあるという利点があります（接続された各コンポーネントが1つのノードのみで構成される最悪の場合、他のアルゴリズムはO（n log n）です）。どちらのアルゴリズムも、有向グラフを適切に処理しません。

于 2012-11-12T01:58:42.277 に答える