[アルゴリズム]最小伸長ツリー

生成ツリー

ツリーのプロパティを満たし、元のシェイプのすべてのノードが接続されているシェイプ.
木を伸ばす条件

は、元の図面のすべてのノード

を含む必要があります.

全ノード相互接続

ツリーのプロパティを満たす(ループなし)

最小生成ツリー(Minimum Spanning Tree,MST)

可能な伸長ツリーで、幹線重み付けが最小の伸長ツリーを指定します.

クルーズアルゴリズム(Kruskal'sアルゴリズム)

幹線を最小料金でつなぎ、最小料金から周期のない幹線をつなぎます.
すべてのノードが接続されるまで

Prim'sアルゴリズム

Union Findアルゴリズム

周期があるかどうかをチェックし、あるなら捨て、ないなら2つの集合を接続します.
-->2つのサブセットを1つのサブセットにまとめる
れんけつロジック
部分セットのルートノードの他のノードをサブノードに接続
2つのツリーを1つのツリーに作成するプロセス
検索ロジック
2つのノードが同じ部分セットにあるかどうかを確認します.
各ノードのルートノードが同じであることを確認します.
union-by-rankメソッド
各ツリーの高さ(rank)を覚えておき、Union Siduツリーの高さ(rank)が異なる場合は、より小さなツリーをより高いツリーに貼り付けます.

同じ高さの2つの木が合併すると、漢民族の木の高さ1を増加することができ、別の木をこの木に貼り付ける

.

時間複雑度:O(logN)

path compression

Findを実行するノードが通過するノードをルートディレクトリに接続する技術

.

Findを実行するノードは、ルートノード

を一度に見ることができる.

クルーズアルゴリズムコード

グラフ＃グラフ＃

mygraph = {
    'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
    'edges': [
        (7, 'A', 'B'),
        (5, 'A', 'D'),
        (7, 'B', 'A'),
        (8, 'B', 'C'),
        (9, 'B', 'D'),
        (7, 'B', 'E'),
        (8, 'C', 'B'),
        (5, 'C', 'E'),
        (5, 'D', 'A'),
        (9, 'D', 'B'),
        (7, 'D', 'E'),
        (6, 'D', 'F'),
        (7, 'E', 'B'),
        (5, 'E', 'C'),
        (7, 'E', 'D'),
        (8, 'E', 'F'),
        (9, 'E', 'G'),
        (6, 'F', 'D'),
        (8, 'F', 'E'),
        (11, 'F', 'G'),
        (9, 'G', 'E'),
        (11, 'G', 'F')
    ]
}

parent = dict()
rank = dict()


def find(node):
    # path compression 기법
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]


def union(node_v, node_u):
    root1 = find(node_v)
    root2 = find(node_u)
    
    # union-by-rank 기법
    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1
    
    
def make_set(node):
    parent[node] = node
    rank[node] = 0

def kruskal(graph):
    mst = list()
    
    # 1. 초기화
    for node in graph['vertices']:
        make_set(node)
    
    # 2. 간선 weight 기반 sorting
    edges = graph['edges']
    edges.sort()
    
    # 3. 간선 연결 (사이클 없는)
    for edge in edges:
        weight, node_v, node_u = edge
        if find(node_v) != find(node_u):
            union(node_v, node_u)
            mst.append(edge)
    
    return mst

時間の複雑さ

O(E logE)