최소비용신장트리 - 3

원소들의 집합을 표현하는 방법

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

* 누가 누구의 자식이고 부모인지는 상관없음

* 각 노드들은 자식노드가 아닌 부모노드의 정보를 갖는다

위의 트리를 배열로 표현할 수 있음 - 각 원소의 부모노드가 무엇인지를 넣는다.

find-set(v)

시간복잡도 : 트리의 높이 , 최악의 경우 o(n)

 

union(u,v)

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

weight union

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

- 각 트리의 크기를 카운트하고 있어야 한다.

- 위에서 노드를 찾을 때 트리의 높이에 영향을 받는다 했으므로 트리의 높이가 작을수록 좋음

- 큰 트리안에 작은 트리가 들어가면 높이의 변화가 없지만 작은 트리에 큰 트리가 들어가면 1씩 증가하게 됨

** 수정 --> 4,7 

p[y] <- x;

p[x] <- y;

- 왼쪽과 오른쪽 트리의 높이 차이가 남을 알수 있다!!

 

path compression

- 올라가면서 부모 노드가 아니면 부모 노드로 붙여준다.

kruskal의 알고리즘 시간복잡도

여기서 시간복잡도의 대부분은 sort하는데 걸린다.

sort를 하는데 걸리는 시간은 mlogm이고 여기서 m은 n^2이므로

mlogn^2이고 2는 상수이므로 mlogn이된다

따라서 시간복잡도는 o(mlogn)이다.

 

** 위의 그림들은 '영리한 프로그래밍을 위한 알고리즘 강좌'에서 가져왔습니다.