[JS] 최소신장트리 (MST)

❗️ 신장트리 (Spanning Tree)

• 그래프의 모든 정점들이 연결되어 있지만 싸이클을 포함하지 않는 그래프
• 하나의 그래프에 여러개의 신장 트리가 존재 가능

❗️ 최소신장트리 (MST)

• 신장트리들 중 간선들의 가중치 합이 최소가 되는 그래프
• 크루스칼 알고리즘을 이용하여 최소 신장 트리를 구현

✅ 크루스칼 알고리즘 구현 방식

1. 그래프의 간선들의 가중치를 오름차순으로 정렬
2. 싸이클을 형성하지 않는 선에서 순서대로 간선을 선택
- 싸이클 여부를 확인할때 Union-Find 알고리즘을 활용

✅ 코드 구현

// 유니온 파인드 구현
// 처음에는 자기 자신의 값을 부모로 가지는 배열 생성
const parent = [];
for(let i=0; i<n; i++) parent.push(i);

// 각 섬의 부모를 찾는 재귀 함수
// 만약 초기 값이 아니라면 parent[x]를 이용해 위로 올라가서 부모값 찾음
const getParent = (parent, x) => {
  if(parent[x] === x) return x;
  return parent[x] = getParent(parent,parent[x]);
}

// 두 섬의 부모를 하나로 합쳐준다.
// 이때 두 부모중 작은 값을 가지는 부모로 합쳐준다.
const unionParent = (parent, x, y) => {
   const n1 = getParent(parent,x);
   const n2 = getParent(parent,y);
   if(n1<n2) return parent[n2] = n1;
   else return parent[n1] = n2;
}

// 두 섬의 부모를 찾고, 부모가 같으면 true, 다르면 false return
 const findParent = (parent, x, y) => {
   const n1 = getParent(parent,x);
   const n2 = getParent(parent,y);
   if(n1===n2) return true;
   else return false;
}

// 크루스칼 알고리즘 구현
for(const cost of costs){
  // 만약 두 섬의 부모가 다르면, 즉 사이클이 형성되지 않은 상태라면
  if(!findParent(parent,cost[0],cost[1])){
    answer += cost[2];	// 정답에 해당 가중치를 더해준다 (오름차순으로 정렬해서 작은값 선택 가능)
    unionParent(parent,cost[0],cost[1]);  // 이제 두 섬은 연결되었으니 합쳐준다
  }
}