[알고리즘] 최소 스패닝 트리 + 문제풀이

신장트리

• 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
• 즉, 사이클 없이 모든 노드가 연결됨 (=트리)

 

최소 신장 트리 알고리즘 => E(logE)

• 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘
• 간선 개수 = 노드 개수 - 1
• 대표적으로 크루스칼 알고리즘이 있음

1. 간선을 가중치에 따라 오름차순 정렬
2. 사이클이 발생하지 않는 경우 MST에 포함

 

코드

n,m = map(int, input().split()) #n=노드 m=간선
edges = [] 
parent = [i for i in range(n+1)] #부모를 본인으로 초기화
result = 0

def find(x):
  if parent[x] != x:
    parent[x] = find(parent[x])
  return parent[x]

def union(a,b):
  a = find(a)
  b = find(b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

for i in range(m):
  a,b,cost = map(int, input().split())
  edges.append((cost,a,b)) #간선치 순으로 정렬하기 위해 위치를 바꿈

edges.sort()
 
for edge in edges:
  cost,a,b = edge #위치 주의하기

  if find(a) != find(b): #사이클이 없는 경우(=루트 노드가 다른 경우) mst에 포함시킴
    union(a,b)
    result+=cost

print(result)

 

관련 문제 풀이