1

私はwikipeidaを読んでいて、Kruskalの疑似コードを次のように見つけました:

KRUSKAL(G):    
    foreach v ∈ G.V:    
        MAKE_SET(v)    
    G.E = sort(G.E)    
    i = 0    
    while (i != |V|-1):      
        pick the next (u, v) edge from sorted list of edges G.E        
        if (FIND_SET(u) != FIND_SET(v)):          
            UNION(u, v)        
            i = i + 1

私は何をしているのかよくわかりませんFIND_SET().Wikipediaには次の説明があります：

そのエッジが 2 つの異なるツリーを接続する場合、それをフォレストに追加し、2 つのツリーを 1 つのツリーに結合します。

2 つの異なるツリーが接続されているかどうかをチェックしていると思いますが、これは実際にはどういう意味ですか?

4

4 に答える 4

0

これfind_set()は、Union-Find として知られる一種のデータ構造の一般的な操作です。このデータ構造の考え方は、（例では頂点の）互いに素なセットを持つことです。

このアルゴリズムでは、各セットは接続されている頂点を表すと思います。

したがってfind_set()、頂点を渡すと、接続された頂点のセットを表す要素を受け取ります。

于 2012-11-30T23:28:20.800 に答える
0 
find_set(u)!=find_set(v)

は巡回しないというスパニングツリーの基本的な性質を表します。等しい場合は、グラフに循環があることを示します。

基本的に、Kruskal アルゴリズムを使用して (エッジの重みが最小の) フォレストを作成し、各ステップでそれが循環しているかどうかを確認します。

それが役に立てば幸い ：）

于 2012-12-01T07:56:32.980 に答える