MST 크루스칼 알고리즘 설명

크루스칼 알고리즘은 최소 신장 트리를 찾기 위한 알고리즘입니다.

 

신장 트리란?
: 무방향 그래프의 부분 그래프 중 모든 정점을 포함하는 트리

최소 신장 트리란?
: 간선의 합이 최소인 신장 트리

Union & Find 알고리즘
: 두 정점이 같은 그래프에 속하는지 판별하는 알고리즘
https://blog.naver.com/ndb796/221230967614

 

 

크루스칼 알고리즘

1. 간선의 크기대로 오름차순 정렬하고 제일 낮은 비용의 간선을 선택
2. 현재 선택한 간선이 정점 u,v를 연결하는 간선이라고 할 때
      1. 만약 u와 v가 같은 그룹이라면 아무 것도 하지 않고 넘어간다
      2.만약 u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가한다(union&find 알고리즘)
3. 최소 신장 트리에 v-1개의 간선을 추가시켰다면 과정 종료, 그렇지 않다면 과정 반복

 

백준 최소 신장 트리 알고리즘 문제
https://www.acmicpc.net/problem/1197

 

출처: 바킹독 블로그
https://blog.encrypted.gg/1024