最小コスト生成ツリー

重み付け無方向図で、すべての頂点を接続するときに最小費用で接続するアルゴリズムを探します.
加重無方向図
頂点の間には重みがあり、幹線には方向の図形がありません.

条件

グラフ内のすべての頂点を含む

サイクル

は存在しない.

Kruskalアルゴリズム

幹線を基準に木を作る方法.クルーズアルゴリズムは、重みが最も小さい幹線が周期を生成しない場合、ツリー幹線を選択して、幹線を重みの増加順にソートします.次の重み付けで、ループを作成しない場合は、ツリーの幹線を選択し、この手順を繰り返して、頂点-1の幹線のアルゴリズムを選択します.
グレースケールアルゴリズム
常に貪欲に最切り上げを選択し、重み付けと最小を探すので、階調アルゴリズムと言える.

アクション

所与の全ての幹線情報を、幹線コストが低い順(昇順)に並べ替える

.

に配列する幹線情報を1つずつチェックすることにより、現在の幹線にノード間の周期

が発生するか否かを判定する.

周期が発生しない場合は最小伸長ツリーに含む、周期が発生する場合は最小伸長ツリーには含まれない

.

第1-3プロセスは、すべての幹線情報に対して

を繰り返す.

UnionFindアルゴリズム(サブセットアルゴリズム)

クルーズアルゴリズムでは、幹線が周期を生じるかどうかを知るために使用されます.このアルゴリズムは、複数のノードが存在する場合、2つのノードを選択してルーティングを決定し、現在同じグラフィックに属しているかどうかを判断する.反発セットは1次元リストで表され、ルートのリスト要素はルートノードの要素ではなくルート自身を格納します.
Disjoint Set
部分集合の要素を繰り返さない情報を格納および操作するデータ構造.
すなわち,共通要素のない「互いに反発する」部分集合の要素に関する資料構造である.

Union

2つの集合を1つの集合に統合する演算.

Find

2つのノードを選択して、現在のノードが同じグラフィックに属しているかどうかを判別し、各グループのルートノードを決定します.ルートノードが同じ場合、ループが発生します.

インプリメンテーション

時間複雑度:O(ElogE)

v, e=map(int, input().split())

#부모 테이블 초기화
parent=[0]*(v+1)
for i in range(1, v+1):
    parent[i]=i

#find 연산
def find(node):
    if parent[node]!=node:
        parent[node]=find(parent[node])
    return parent[node]

#union 연산
def union(node_v, node_e):
    root1=find(node_v)
    root2=find(node_e)

    if root1<root2:
        parent[root2]=root1
    else:
        parent[root1]=root2

total_cost=0
edges=[]

for _ in range(e):
    a, b, cost=map(int, input().split())
    edges.append((cost, a, b))

edges.sort()

for i in range(e):
    cost, a, b=edges[i]
    if find(parent, a) != find(parent, b):
        union(a, b)
        total_cost+=cost

print(total_cost)

Primアルゴリズム

開始頂点を選択した後、展開して最小幹線に接続するノードを展開し、このノードで最小幹線のノードに再接続します.
クルーズアルゴリズムとの違い
クルーズアルゴリズム:重み付け最小の幹線から
プリフェッチアルゴリズム:特定のノードから開始し、そのノードの重みが最も小さい幹線接続ノードを通過します.

プロセス

の任意のノードを選択し、接続するノードセット

に挿入する.

を選択した頂点に接続する幹線列をリスト

とする.

幹線リストで最も重みの小さい幹線から選択
3-1. この幹線に接続されているノードが接続されているノードセットにある場合は、(ループを避ける)
3-2. 接続ノードセットにない場合、幹線を選択し、最小伸長ツリー

に挿入する.

抽出幹線はリストから

を削除する.
幹線リストに幹線がないまで

を繰り返します

インプリメンテーション

コレクションライブラリのdefaultdict関数の使用
時間複雑度:O(EGE)

from collections import defaultdict
from heapq import *

def prim(first_node, edges):
    mst = []
    # 해당 노드에 해당 간선을 추가
    adjacent_edges = defaultdict(list)
    for weight, node1, node2 in edges:
        adjacent_edges[node1].append((weight, node1, node2))
        adjacent_edges[node2].append((weight, node2, node1))

    # 처음 선택한 노드를 연결된 노드 집합에 삽입
    connected = set(first_node)
    # 선탠된 노드에 연결된 간선을 간선 리스트에 삽입
    candidated_edge = adjacent_edges[first_node]
    # 오름 차순으로 정렬
    heapify(candidated_edge)

    while candidated_edge:
        weight, node1, node2 = heappop(candidated_edge)
        # 사이클 있는지 확인 후 연결
        if node2 not in connected:
            connected.add(node2)
            mst.append((weight, node1, node2))

            for edge in adjacent_edges[node2]:
                if edge[2] not in connected:
                    heappush(candidated_edge, edge)

    return mst

改良アルゴリズム
メインライン以外のノードを中心に優先キューを作成して解放
-初期化
選択したノードキー構造を作成し、キー値を0に入力し、残りのノードのキー値を無限大に設定します.
すべての[ノード:key]値をキューに挿入
-ノード:キーをpopに抽出
-ノードの隣接ノードでキー値とウェイト値を比較し、ウェイト値が小さい場合はキー値をウェイト値に更新します.
-更新後、優先キューのキー値が最も小さいノードをルートノードにアップロードする必要があります.
heapdictライブラリの使用

from heapdict import heapdict

def prim(graph, first):
    mst = []
    keys = heapdict()
    previous = dict()   
    total_weight = 0

    #초기화
    for node in graph.keys():
        keys[node] = float('inf')
        previous[node] = None
    keys[first], previous[first] = 0, first

    while keys:
        current_node, current_key = keys.popitem()
        mst.append([previous[current_node], current_node, current_key])
        total_weight += current_key
        for adjacent, weight in graph[current_node].items():
            if adjacent in keys and weight < keys[adjacent]:
                keys[adjacent] = weight
                previous[adjacent] = current_node
    return mst, total_weight
    ```