最小拡張ツリー-1(クルーズアルゴリズム)

3379 ワード
アルゴリズム#アルゴリズム# テキストリンク

腎臓の木とは何ですか。

  • 原図のすべてのノードが接続され、ツリーの属性を満たす図である.
  • 新疆樹の条件
    -元の図面のすべてのノードを含める必要があります.
    -すべてのノードが相互に接続されている必要があります.
    -ツリーのプロパティを満たす必要があります.(ループは存在しません.)

    • 2.最小身長木


    ->可能な腎臓樹のうち、肝臓の重量の和が最小の腎臓樹.

    3.クルーズアルゴリズム


    ->代表的な最小伸長木アルゴリズムには「クルーズアルゴリズム」と「Primアルゴリズム」がある.まずクルースカのアルゴリズムを理解してみましょう.
    『クルーズアルゴリズム』
    1.すべての頂点を独立した集合にする.
    2.すべての幹線を費用順に並べ替え、費用の少ない幹線から両端の2つの頂点まで比較します.
    3.2つの頂点の最上位頂点を決定し、異なる場合は2つの頂点を接続します.(ループが発生しないように)


    4.UNION-FINDアルゴリズム


    :ノードに接続されているノードを検索したり、ノードを接続したりします.
    <必要な機能>
    1.初期化
    2. Union
  • 木ごとにrank(高さ)を覚えておいて、2本の木の高さが異なる場合は、より高いスローツリーに貼り付け、2本の木の高さが同じ場合は、1本の木の高さを増やし、別の木に貼り付けます.

  • Find

    • 5.コード作成


    グラフ＃グラフ＃
    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
    結果
    #2630色紙[白駿](H 99.34)
    洛谷p 1637三元上昇サブシーケンス