1

FIND-SET(x) – 要素 x を含むセットの代表または代表へのポインターを返します。

アルゴリズムでは、find-set(x) はばらばらなデータ構造で使用されます。この関数の使い方がわかりません。4 つの頂点 a、b、c、d と ab=4、bc=5、cd=6 として指定された重みを持つグラフがあるとします ... find-set(u)!=find-set(v ) (u,v はグラフの任意の頂点です) は、グラフ内のサイクルの発生を定義するのに役立ちます!?? 検索は次のように定義されます。

function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)
4

1 に答える 1

2

Find-Set(x)最小スパニング ツリー (MST) を実装するために、ばらばらなデータ構造で最も頻繁に使用されます。

uとが同じセットにある場合v、それらは既に接続されていることを意味します。それらがすでに接続されている場合、それらの間に別の接続を追加すると、サイクルが作成されます。

すべての頂点が独自の個別の単一要素セット内にあると言って、これを分析し始めることができます。2 つの頂点間の接続を確立する場合、たとえば、 と を同じセット内a-bに配置aします。bしたがって、それらがどのように同じセットに含まれているかを判断する必要があります。したがって、Find-Set(x)それらが同じセット内にあるかどうかを判断するために使用します（あなたの場合、それはばらばらなフォレストの実装です）。

あなたが提供する例にはサイクルがないため、別のエッジを追加します。

例

a最初に、一連の頂点、b、cおよびがあると仮定しdます。3 つの頂点すべてを同じフォレストに接続できる最小数のエッジが存在するように、最小スパニング ツリーを決定します。

現在利用可能なエッジ: (a, b), (c, d), (b, c), (d, c)(サイクルである余分なエッジ!)

これは、基本的なグラフ用語である頂点、エッジ、フォレストの定義を知っていることを前提としています

aとは現在別個のセットであるため、それらを同じセット内に配置するbなどのアルゴリズムを使用してそれらを組み合わせることができます:まだとが接続されている必要があります。ここでそれがセットの名前であることに注意してくださいMerge-Set(a, b)A=(a, b)cdA

(c, d)それも可能であることがわかります。したがって、それらをマージできます:B=(c, d)そして、 もあります(a, b)。Bこの素集合の名前

A=(a, b)これで、エッジがあることをB=(c, d)知ることでマージできます(b, c)。セット内には複数の要素があるため、まず でエッジが必要かどうかを判断しFind-Set(x)ます。if Find-Set(b) == Find-Set(c)then は、サイクルがあることを知っていますA == B。幸いなことに、(b, c)setA=(a, b)またはのいずれにも発生しないので、そうではありませんB=(c, d)。ここで、通常どおりそれらをマージし、セットである MST に到達しますA=(a, b, c, d)(B が削除されていることに注意してください!)。

サイクルになる余分なエッジを思い出してください。を追加しようとすると、とが存在する集合が同じであること(d, c)がわかります。したがって、このエッジがサイクルを作成していると判断できます。dcFind-Set(d) == Find-Set(c)A == AdcA

于 2012-05-09T17:23:33.140 に答える