MST - Kruskal 헷갈리는 부분 정리

Kruskal Algorithm은 Union-find 기법을 베이스로 한다.

본 게시물은 Kruskal Algorithm을 소개하는 글이 아닌, 실수 할 수 있는 부분에 대해서 기록해놓고자 한다.

union(x,y) 메소드를 실행 했을 때, union되는 node들의 부모 p[x], p[y]는

항상, 최 상위 부모노드 로 업데이트 되지 않는다.

만약 최상위 노드가 따로 있고, 하위 노드간에, union이 발생한 형태라면, union 되는 노드들 간의 우위 조건에 의한 부모 선택이 이뤄지지, 이 과정에서 최 상위 노드가 부모로 등록되지 않는다.

하위 노드의 부모노드로 최 상위 노드가 등록되는 시점은 findSet() 함수를 호출 했을 때이다.

findSet 함수의 body를 봤을 때, 현재 노드가 최상위 노드가 아닐경우,
재귀적으로 최 상위 노드를 찾아간다.

따라서, 자기 바로 위의 부모를 호출 할 때에는 findSet으로 부모가 업데이트 되기 전이라면 p[x], 자기가 속한 그룹의 최상위 부모노드를 호출하기 위해서는 findSet()을 호출해야한다.