Minimum Spanning Tree

모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리

 

> 가중치가 작은 에지부터 에지가 N-1개가 될 때까지 연결하되(정렬 > union)

> find로 대표 노드가 같으면(왼쪽 방향 회전(find로 찾아진 대표 노드)이 오른쪽 새 연결과 만날 때) 사이클이 생기므로 건너뛴다

 

- 사이클이 포함되지 않는다

- N개의 노드가 있을 때, 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 개이다

- 에지 중심의 시행

 

------------------------------------

1

재료

edge list 형태로 저장

edge class에는 Node-start, Node-end, weight로 구성

union find 배열도 초기화

 

2

가중치 기준으로 오름차순 정렬

comparable() 함수 사용가능

 

3

cycle unit

가중치가 낮은 edge부터 연결 시도한다

바로 연결하지 않고, 연결했을 때 그래프의 사이클 형성 유무를 find연산 이용하여 확인 > union을 이용해 두 노드 연결

왼쪽 방향 회전(find로 찾아진 대표 노드)이 오른쪽 새 연결과 만난다

 

4

에지 개수가 N-1이 될 때까지 반복(N개 노드일 때)