[이코테]-신장트리/크루스칼 알고리즘

page 281
크루스칼 알고리즘은 union / find 의 공식을 이용한다.

const parent_arr = Array.from({ length: 8 }, () => 0);
for (var i = 1; i < parent_arr.length; i++){
 parent_arr[i] = i;
}
var gey = [[1, 2, 29], [1, 5, 75], [2, 3, 35], [2, 6, 34], [3, 4, 7], [4, 6, 23], [4, 7, 13], [5, 6, 53], [6, 7, 25]];

gey = gey.sort((a, b) => a[2] - b[2]);

console.log(parent_arr)

const find_parent = function (a) {
 if (parent_arr[a] != a) {
  parent_arr[a] = find_parent(parent_arr[a]);
 }
  return parent_arr[a];
 
}
const union = function (a, b) {
 
 const find_X = find_parent(a);
 const find_y = find_parent(b);
 
 
 if (find_y > find_X) {
  parent_arr[find_y] = find_X;
 }
 else {
  parent_arr[find_X]=find_y
 }



}
//경로 압축 즉 길을 가면서 경로에 해당하는 부모 노드 값을 자동으로 바꿔주는 함수이다.

var count = 0;

for (var i = 0; i < gey.length; i++){

 var [a, b, c] = gey[i];

 if (find_parent(a) != find_parent(b)) {
  console.log(a, b, '시작')  
  union(a, b);
  count += c;
   }
  
}

console.log(parent_arr, '학부모');
console.log(count)

크루스칼의 코드 오류 해결

문제를 풀어보는데 이상한 값이 나와서 오류가 왜 나느지 분석 해보았다. 그결과
자식 노드들이 갱신이 안되는 문제점으로 인하여 오류가 발생