알고리즘_최소신장트리(MST)(그리디)

1. 최소신장 트리

주어진 가중치 그래프에서 사이클이 없이 모든 점을 연결시킨 트리중 선분의 가중치의 합이 최소인 트리

(a) 기중치 그래프
(b) 최소 신장트리 <-
(c) 신장트리
(d) 신장트리

1.1 최소신장 트리의 특징

1. 그래프에 n개의 점이 있을때 선분의 갯수는 (n-1)이 된다
2. 트리에 선분을 하나 추가하면 반드시 사이클이 생긴다.

1.2 탐욕 MST알고리즘

• 크러스컬 알고리즘

1. 가중치가 가장 작은 선분이 사이클을 만들지 않을 경우 선분을 추가시킴
2. 위 연산을 반복해 트리를 완성함

• 프림 알고리즘

1.3 크러스컬 알고리즘

그래프의 모든 선분을 오름차순으로 정렬한다.

오름차순으로 정렬된 선분중에 가장 길이가 작은 선분을 우선적으로 트리에 포함시킨다.
그리고 사용한 선분은 오름차순 정렬에서 지운다.

알고리즘을 반복해 나가다 사이클이 생성되면 해당 선분을 버린다.

알고리즘을 수행중에 연결되어 있지 않은 부분 트리가 생성될 수 있다.

간선의 수가 n-1이 되게되면 트리가 완성된다.

1.3.1 크러스컬 알고리즘에서 사이클 검사

알고리즘 코드

자기 자신을 가리키는 리스트를 만듬

음수는 대표원소라는 의미
아래표를 따라서 설명하자면
1번 원소는 자식 노드르 2개 가지고 있는 대표원소
2번 원소는 자식 노드를 3개 가지고 있는 대표원소
3번 원소는 2의 자식 노드
4번 원소는 1의 자식노드
...

자신과 같은 대표원소를 가지고 있는 원소는 같은 집합안에 존재함
즉, 같은 대표원소를 가지고 있는 점을 포함하는 선분을 추가하면 사이클이 생성됨

점의 갯수 n
선분의 갯수 m = n-1
시간복잡도 O(mlogm)