그래프가 주어질때 가장 가중치 적은 노드로 최소한 연결된 트리만드는거

노드 N개라고할때 엣지개수 N-1개겠지

어케 구현할까

Union, find

초기에 노드 하나 하나가 그룹이라고봄

가중치가 작은 엣지들로 정렬해

(A노드, B노드, 가중치) 이렇게 그래프정보가 주어질텐데 얘네를 가중치 중심으로 오름차순 정렬하라는거야.

가중치가 작은 엣지부터 그룹으로 union하게 될거야

union은 뭐가됐던 그룹의 밑에 그룹이 붙게되는거. 노드 붙을때 자식노드 포인터 두지않음. Find할때 대장인 루트 노드 하나만 가지고 비교할거라서 필요가없음. 왜 대장인 루트만 비교하냐? 같은 루트라면 그 노드 둘이 서로 같은 그룹에 있다는거고 그러면 둘은 유니온하면 안된다는거니까.

그럼 대충 어떤 흐름인지 알겠지

정렬하고, Union(a,b)할때 a, b 노드가 속한 그룹이 서로 다른 그룹인지 파악하기위해 대장인 루트를 Find해서 서로 루트가 다르면 합쳐주고, 아니면 합쳐주지 않으면 되는거지

이슈라면 합칠때 어떤식으로 합쳐주느냐에 따라 성능이 달라진다는거

이진트리도 트리의 높이에따라 성능차이있었지?

그룹을 붙여줄때 노드가 속한 그룹의 루트를 서로 비교해서, 자식 개수가 많은 그룹을 적은 그룹이 따라 붙게한다거나 높이 높은 그룹의 밑에 따라 붙게한다거나 등..더 좋은 방법도 하나 더 소개해줬는데 알필욘 없는거같음. 탐색하면서 루트까지 가기전까지 거친 노드들 각각을 루트 바로 밑에 붙여버리는 방법인데 뭐..

암튼 이런 느낌의 알고리즘이고 크루스칼알고리즘이라고해