8

私はunion-findアルゴリズムを扱っています。私のプログラムの最初の部分では、アルゴリズムは big set の分割を計算しEます。

その後S、特定の node を含むset のすべてのメンバーを取得したいと考えていますx。

E今までは単純に、 setのすべての要素のメンバーシップをテストしていましたS。しかし、昨日、「アルゴリズムの紹介」(CLRS、第 3 版、例 21.3-4) を読んでいて、演習で次のことがわかりました。

PRINT-SET(x)ノードが与えられ、のセットのxすべてのメンバーを任意の順序で出力する操作 を追加したいとします。x互いに素な集合の森の各ノードに単一の属性を追加する方法を示して、の集合PRINT-SET(x)のメンバーの数に比例して時間がかかりx、他の操作の漸近的な実行時間は変更されないようにします。

「セットのメンバー数の線形x」は、私の問題を大きく改善するでしょう! だから、私はこの演習を解決しようとしています...そしていくつかの失敗した試みの後、スタックオーバーフローで助けを求めています!

4

2 に答える 2

5

リストを使用せずに別のアルゴリズムを作成することができました (私のプログラミング言語、つまり ANSI-C で使用する方が便利です)。

私はの助けを借りてそれをしました

素集合データ構造のノードを線形時間で出力します。

最初の投稿後にこのスレッドを見つけました、申し訳ありません。

疑似コード (まだテストされていません) :

MAKE-SET(x)
    x.p = x
    x.rank = 0
    x.link = x        # Circular linked list

UNION(x,y)
    sx = FIND-SET(x)
    sy = FIND-SET(y)
    if sx != sy
        LINK(sx, sy)

LINK(x,y)
    temp = y.link     # Concatenation
    y.link = x.link   # of the two
    x.link = temp     # circular lists
    if x.rank > y.rank
        y.p = x
    else x.p = y
         if x.rank == y.rank
             y.rank = y.rank + 1

FIND-SET(x)
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p

PRINT-SET(x)
    root = x
    PRINT(x)
    while x.link != root
        x = x.link
        PRINT(x)
于 2014-04-14T13:32:47.343 に答える