최소비용신장트리(minimum spanning tree)-3

서로소인 집합들의 표현

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

배열 parent를 만들어 모든 트리를 하나의 배열로 표현

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

FIND-SET(x)

if x≠p[x]

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

return p[x]

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

UNION(u,v)

1. x<-FIND-SET(u);

2. y<-FIND-SET(v);

3. p[x]<-y;

weighted union

- 두 집합을 union할때 작은 트리의 루트를 큰 트리의 루트의 자식으로 만듬(여기서 크기란 노드의 개수)

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

WEIGHTED-UNION(u,v)

1. x<-FIND-SET(u);

2. y<-FIND-SET(v);

3. if size[x]>size[y] then

4.    p[y]<-x;

5.     size[x]<-size[x]+size[y];

6. else

7.    p[x]<-y;

8.    size[y]<-size[y]+size[x];

Path compression

FIND-SET-PC(x)  

1. while x ≠ p[x] do

2.    p[x]<-p[p[x]];  //경로의 길이를 반으로 줄임

3.    x<-p[x];

4. end.

5. return p[x];