[伯俊]117:最小生成木


質問する


https://www.acmicpc.net/problem/1197
最小生成ツリーをクルーズアルゴリズムで実現した.
  • グラフの幹線を重み付け昇順に並べます.
  • に並ぶ幹線リストでは、순서대로サイクルを形成しない幹線が選択される.
    すなわち、낮은重み付けが最初に選択される.
  • サイクルを形成する幹線を除く.(木の基本条件)
    この幹線현재의 MST(최소 비용 신장 트리)의 집합에 추가.
  • 良いウェブサイト
    最小生成ツリー(最小拡張ツリー)
    https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
    find関数
    https://www.crocus.co.kr/683

    に答える

    import sys
    
    # 노드의 개수, 간선의 개수
    V, E = map(int, sys.stdin.readline().split())
    
    # 부모 테이블 초기화
    parent = [0] * (V + 1) # 왜 V + 1?
    
    # 모든 간선을 담을 리스트와 최종 비용을 담을 변수
    edges = []
    result = 0
    
    # 부모 테이블상에서, 부모를 자기 자신으로 초기화
    for i in range(1, V + 1):
        parent[i] = i
    
    # 모든 간선에 대한 정보를 입력받기
    for i in range(E):
        a, b, cost = map(int, sys.stdin.readline().split())
        # 비용순으로 정렬하기 위해 튜플의 첫번째 원소를 비용으로 설정
        edges.append((cost, a, b))
    
    # 간선을 비용순으로 정렬
    edges.sort()
    
    # find 함수 : 특정 원소의 루트 원소 찾기 (속한 집합 찾기)
    def find_parent(parent, x):
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
        return parent[x]
    
    # union 함수 : 두 원소의 루트 원소를 하나로 합치기 (노드를 연결)
    def union_parent(parent, a, b):
        a = find_parent(parent, a)
        b = find_parent(parent, b)
        
        if a < b:
            parent[b] = a # 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가
        else:
            parent[a] = b
        
    # 간선을 하나씩 확인하며 최소 신장 트리에 넣어줄 수 있는지 확인
    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)