4

私がこれまでに持っているものは、Cormen et al. による「Introduction To Algorithms」の 571 ページに大きく基づいています。

私はセットを表す Python の Node クラスを持っています:

class Node:
    def __init__(self, parent, rank = 0):
        self.parent = parent
        self.rank = rank

この実装ではList、ノードの 1 つをフォレストとして使用します (セットを格納するためのより良い方法を受け入れます)。

Initialize()ノードのリストを返します。これを変数に格納setし、他の関数に渡します。

Findは、フォレスト内で値を検索し、それが含まれるセットを返します。for s in range(len(set)):再帰で、 によって渡されるセットのリストを縮小できるように、 を使用することにしましたset[s:]。 

def Find(set, value):
    for s in range(len(set)):
        if value != set[s].parent:
            set[s].parent = Find(set[s:], set[s].parent)
        return set[s]

Mergeフォレスト内のセットを見つけて、より高いランクのセットを昇格させることにより、セットをマージします。 

def Merge(set, value1, value2):
    set_val_1 = Find(set, value1)
    set_val_2 = Find(set, value2)
    if set_val_1.rank > set_val_2.rank:
        set_val_2.parent = set_val_1
    else:
        set_val_1.parent = set_val_2
        if set_val_1.rank == set_val_2.rank:
            set_val_2.rank += 1

Finds とsを実行するとエラーが発生しますMerge。つまりFind、適切なセットが返されないため、Mergeも適切に機能しているかどうかわかりません。機能が適切に実装されていることを確認するための助けをいただければ幸いです。

4

5 に答える 5

2

私はその本の最新版を持っていませんが、これはバラバラに設定された森のようには見えません。

あなたの間違いは、フォレストをコレクションに格納する必要があり、ノードで操作を行うにはこのコレクションをトラバースする必要があると考えることだと思います。から削除setしMerge()てFind()実装Find()する

def Find(n):
    if n != n.parent:
        n.parent = Find(n.parent)
    return n.parent

ちょうど本のように。次に、MakeSet()正しく初期化された単一のノードを返す a を追加し、場合によってはSameSet()関数も追加します。

def SameSet(n1, n2):
    return Find(n1) == Find(n2)

これで、互いに素なセットの実装が機能するようになりました。

于 2011-02-23T20:40:54.240 に答える
1

各ノードがそれ自身の親になるように初期化されていると仮定します。

def Find(node):
    while node is not node.parent:
        node = node.parent
    return node
于 2011-02-23T21:33:56.460 に答える