!!개인 공부용이기 때문에 틀린 내용이 있을 수도 있습니다!! 잘못된 내용이 있으면 언제든지 지적해 주세요.
최소 신장 트리(MST)를 구하는 방법 중의 하나.
탐욕법을 통해 MST를 구하는 방법이다.
Kruskal 알고리즘을 사용하기 위해서는 우선 간선들을 cost를 기준으로 오름차순으로 정렬해 두어야 한다.(priority queue를 사용하는 것도 좋은듯)
그 후 union-find를 통해 정점의 root가 다른 경우 간선을 선택하면 된다.
find 함수: 정점의 root를 찾아 반환
int find(int N){
if(root[N] == N) return N;
else
return root[N] = find(root[N]);
}union 함수: 간선 연결
void union(int a, int b){
a = find(a);
b = find(b);
root[b] = a;
}크루스칼 알고리즘 문제
