MST 최소비용신장트리, Union find 개념과 JS코드

신장트리란

• 모든 노드가 연결되있고
• 사이클이 없는 그래프이다.
• n개의 노드를 n-1개의 선으로 연결한다.
• 그래프의 최소연결 그래프이다
• 보통 네트워크 구축에 많이 사용된다

ㅣ용

 

최소비용신장트리란 MST (Minimum Spanning Tree)

간 선에 비용을 붙여 최소의 비용이 드는 신장트리다

조건은

• 비용 최소
• 반드시 n-1개의 선만 사용
• 사이클이 없다

 

 

MST를 구하는데 주로 크루스칼, 프림알고리즘이 사용된다

먼저 크루스칼 알고리즘의 베이스인 union find를 알아보자.

 

Union-Find란

여러개의 노드가 존재할 때 선택한 두 개의 노드가 같은 그래프에 있는지를 판별하는 알고리즘이다.

 

먼저 기본적으로 자기자신을 부모로 가지는 배열을 만들고

서로 다른 부모를 합칠 때 더 작은 쪽으로 합친다.

 

 

 

3과 1이 연결되있는지를 파악하기 위해 재귀함수를 사용한다.

3의 부모 2를 찾고, 2의 부모 1을 찾고, 1의 부모는 1이므로 3의 부모도 1임을 알 수 있다

참고) arr[i] = i 로 자기자신을 가리키는 노드가 최상위 부모노드이다.

 

3의 부모가 1로 변경되었다

 

노드 1,2,3의 부모가 모두 1이기 때문에 이 세 노드는 같은 그래프에 속한다. 

 

 

이제 밑의 그래프로 union find를 구현해보겠다

const nodeCount = 8;
const parents = Array.from({ length: nodeCount + 1 }, (_, i) => i);

// 부모 노드를 찾는 재귀함수
function getParent(i) {
  if (parents[i] === i) {
    return i;
  }
  return getParent(parents[i]);
}

// 두 부모 노드를 합치는 함수
function unionParent(a, b) {
  a = getParent(a);
  b = getParent(b);
  if (a < b) parents[b] = a;
  else parents[a] = b;
}

// 두 노드의 부모가 같은지 확인하는 함수
function isUnionParent(a, b) {
  return getParent(a) === getParent(b);
}

unionParent(1, 2);
unionParent(2, 3);
unionParent(4, 6);
unionParent(6, 5);
unionParent(7, 8);

console.log(parents); // [0, 1, 1, 1, 4, 4, 4, 7, 7]
console.log("2와 3의 parent가 같나요?", isUnionParent(2, 3)); // true
console.log("8와 5의 parent가 같나요?", isUnionParent(8, 5)); // false

 

 

따라서 신장트리 즉 n-1개의 선으로 모든 노드가 연결되있지만 사이클이 없는지를 확인하려면

parents의 부모가 통일되는지를 보면 된다.

 

 

하지만 여기서 쉽게 간과 될 수 있는것은

union은 a, b 이 둘 만의 부모를 통합할 뿐이지, 그 둘을 부모로 가지고 있는 다른 노드들의 부모는 갱신되지 않는다.

예를 들어서 1,5를 union하면 5의 부모는 1로 갱신되지만, 5를 부모로 갖고있던 노드들의 부모는 1로 갱신되지 않는다.

https://school.programmers.co.kr/questions/55001

 

두 노드의 부모를 합친 뒤 연결 된 노드의 부모를 전부 업데이트 하는 함수

function unionParent(a, b) {
  a = getParent(a);
  b = getParent(b);
  if (a < b) {
    parents.forEach((p, i) => {
      if (p === b) {
        parents[i] = a;
      }
    });
  } else {
    parents.forEach((p, i) => {
      if (p === a) {
        parents[i] = b;
      }
    });
  }
}