최소 스패닝 트리(Minimum Spanning Tree, MST)

목차

최소 스패닝 트리(Minimum Spanning Tree, MST) / Union-Find

• 신장 트리(Spanning Tree)는 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프를 의미함.(루트 노드가 없는 트리라고 생각)
  • 트리 : n개의 노드, n-1개의 간선 (모든 노드가 연결, 순환이 없는 그래프)
  • 신장 트리 : 루트노드가 없는 트리
• 최소 스패닝 트리(MST,minimum spanning tree)
  • 그래프에 간선이 여러개 존재할텐데, 그중에서 스패닝 트리로 만들수 있는 모양중 가중치의 합이 최소가 되는 것
• 최소 스패닝 트리를 만드는 방법 (크루스칼 알고리즘, MST 알고리즘중 가장 많이쓰이고 빠른편)
  • 먼저 간선을 가중치값을 오름차순으로 정렬
  • 그후에 하나씩 연결을 진행하는데, 연결을 하는 노드가 이미 연결이 되어 있는 노드인지 Union-Find 알고리즘을 통해 확인을 진행해야함.
  • 이미 연결이 된 노드라면 더 낮은 가중치 값으로 연결한것이기 때문에 지나가기
  • 이런식으로 간선 v-1개가 뽑혔을때, MST가 완성됨
• 예시의 [백준 1922] 네트워크 연결 문제를 통해 개념 정리가 가능합니다.

예시

• [백준 1922] 네트워크 연결
  • 모든 컴퓨터를 연결할 수 없는 경우는 없기 때문에 모든 노드들이 연결된 간선들이 주어진 그래프입니다.
  • 이 그래프에 대해서 모든 노드들을 연결할 수 있는 최소 스패닝 트리를 찾는 문제입니다.
  • 코드

    • import sys
      
      input = sys.stdin.readline
      
      n = int(input())
      m = int(input())
      
      
      def find(x):
          if parent[x] == x:
              return x
      
          parent[x] = find(parent[x])
          return parent[x]
      
      
      def union(a, b):
          a = find(a)
          b = find(b)
      
          if a == b:
              return False
          elif a > b:
              parent[a] = b
              return True
          elif a < b:
              parent[b] = a
              return True
      
      
      parent = [i for i in range(n + 1)]
      
      pay_list = []
      for _ in range(m):
          pay_list.append(list(map(int, input().split())))
      
      pay_list.sort(key=lambda x: x[2])
      answer = 0
      for a, b, w in pay_list:
          if union(a, b):
              answer += w
      
      print(answer)