개발 공부 - [그래프 알고리즘] 순회 - 최소비용신장트리(minimum spanning tree) - 3

서로소인 집합들의 표현

- 각 직합을 하나의 트리로 표현

예 : 2개의 집합

disjoint한 집합 (sets) = 두 집합이 공집합이다.

집합의 각 원소들이 트리의 노드가 된다.

누가 루트이고 누가 누구의 부모이든 상관이 없다

트리의 각 노드는 자식노드가 아닌 부모 노드의 주소를 가진다. (상향식 트리)

이걸 모든 트리를 하나의 배열로 표현할 때 쓸 수 있도록 배열에 담아서 구현 할 수 있도록 가능하게 설명을 해 주신다...

Find-set(v)

: 자신이 속한 트리의 루트를 찾음

FIND-SET(x)

if x != p[x]

    then p[x] <- FIND-SET(p[x])

return p[x]

o(h), h는 트리의 높이

h는 최악의 경우 o(n)

Union(u,v)

한 트리의 루트를 다른 트리의 루트의 자식 노드로 만듬

UNION(u,v)

x <- find-set (u);

y <- find-set (v);

p[x] <- y;

루트 노드를 찾은 이후에는 o(1)

하지만 루트를 찾는데 O(h)

이거는 그냥 u와 v가 속한 두 집합을 하나로 합치는 법이다 (전체  수도코드에 해당)

Weighted Union

: 두 집합을 union 할 때 작은 트리의 루트를 큰 트리의 루트의 자식으로 만듬!!!!

ㄴ 오... -.-)... 더 큰 데에 그냥 합쳐버리면 전체 트리 레벨이 증가하지도 않음!!!

이것은 각 트리의 크기 (노드의 개수)를 카운트 하고 있어야 함

Path Compression

이거로 union find의 성능을 빠르게 해줄 수 있음!

Find(g) 

find를 할 때 트리를 위로 따라 올라가야 하는데,

올라가면서 자식 트리들을 다 노드의 자식으로 만드는 방식임!

find 작업을 하며, 트리 높이를 줄이는 방식 (find 한 영역에 대해서만 줄어든다)

-.-)...