[アルゴリズム概念]最小伸長ツリー-クルーズアルゴリズム


  • 生成ツリー:1つのグラフィック内のすべてのノードを含むが周期が存在しないローカルグラフィック
  • .
  • 最小拡張ツリーアルゴリズム:最小コストで拡張ツリーを検索するアルゴリズム
  • クルーズアルゴリズム(Kruskal Algorithm):典型的な最小拡張ツリーアルゴリズム
  • クルーズアルゴリズム
  • 幹線データ料金昇順
  • 幹線を1本ずつ検査し、現在の幹線が周期的に発生しているかどうかを確認します.
  • サイクルが発生しない場合、最小伸長ツリーに含まれます.
  • サイクルが発生した場合、最小伸長ツリーには含まれません.
  • すべての幹線に対して2回の過程を繰り返す.
    def find_parent(parent, x):
    	if parent[x] != x:
        	parent[x] = find_parent(parent, parent[x])
        return parent[x]
    
    def union_parent(parent, a, b):
    	a = find_parent(parent, a)
        b = find_parent(parent, b)
        if a < b:
        	parent[b] = a
        else:
        	parent[a] = b
    
    # 노드의 개수, 간선의 개수
    v, e = map(int, input().split())
    parent = [0] * (v+1)
        
    edges = []
    result = 0
        
    for i in range(1, v+1):
    	parent[i] = i
    
    for _ in range(e):
    	a, b, cost = map(int, input().split())
        # 비용순으로 정렬하기 위해 튜플의 첫번째 원소를 비용으로 설정
        edges.append((cost, a, b))
    
    edges.sort()
    
    for edge in edges:
    	cost, a, b = edge
        # 사이클이 발생하지 않는 경우에만 집합에 포함
        if find_parent(parent, a) != find_parent(parent, b):
        	union_parent(parent, a, b)
            result += cost
            
    print(result)