크루스칼 알고리즘(MST+유니온 파인드)

크루스칼 알고리즘
그래프 내 모든 정점을 포함하고 사이클을 생성하지 않으며 선을 연결했을 때 가중치 합이 최소가 되는 상황을 구할 때 사용

• 그리디의 일종 → 가중치가 작은 것부터 먼저 선택

신장 트리

1. 모든 정점 연결
2. 정점 간 연결이 되었을 때 사이클이 생성되면 안됨
   → 정점의 개수 = n개 인 경우, 간선은 n-1개가 나옴

최소 신장 트리

신장트리에서 가중치 합이 최소인 트리

동작 원리

1. 가중치 기준으로 오름차순 정렬
2. 연결되어 정점을 순회하면서 사이클을 이루지 않는 조건에서 간선 선택 → 선택된 간선의 수가 정점의 수-1이 될 때까지 반복
3. 사이클 판단 → 유니온 파인드로 확인

   유니온 파인드(Union&Find)
   유니온: 서로 다른 두 집합 병합
   파인드: 집합 원소가 어디 집합에 속해 있는지 찾기

const parentNode = Array.from({length: n}, (_, idx) => idx); // 부모 정점 배열(처음에 본인으로 초기화)
const Find = (x) => {
	if(x===parentNode[x]) return x; // 부모 정점 찾은 경우 리턴
  	else return parentNode[x] = Find(parentNode[x]);
}

const Union = (x, y) => {
  const fx = Find(x);
  const fy = Find(y);
  
  if(fx !== fy) parentNode[fy] = fx;
}

4. 사이클 X, 해당 간선 선택 후, 정점 연결
5. 사이클 O, 해당 간선 선택 X

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)