MST ( Minimum Spanning Tree ) - Kruskal , Prim

 

[ MST ] = Minimum Spanning Tree = 최소 신장 트리.

- 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것.

- 사례 : 도로 건설, 전기 회로, 통신 ,배관 등등

 

흔히 아는 트리는 rooted 트리 라고 한다.

싸이클이 없고 연결된(connected), 무방향( Undirected) 그래프를 트리라고 부른다.

---

 

[ MST 특징 ]

 

- Undirected ( 무방향 ) weight( 가중치 ) 그래프이고, 가중치들은 모두 양수이다.

- 싸이클이 없어야 된다.

    => 싸이클이 존재한다고 가정해보자. 그렇다면 싸이클 상의 랜덤한 한 엣지를 버리더라도 모든 노드들은 연결됨.

    => 이 말은 즉, 최소 비용이라는 MST에 모순.

 

- 노드가 n 개인 트리는 항상 n-1 개의 엣지를 가짐.

- 해가 유일하지는 않음.

 

---

 

[ MST 알고리즘 ]

 

구현은   1. Kruskal 알고리즘과 2. Prim 알고리즘 두 가지 방법으로 가능.

 

Kruskal 과 Prim 이 공통적으로 가지고 있는

< Generic MST 알고리즘 >

어떤 MST 의 부분집합 A 에 대해서 A U { ( u, v) } 도 역시 어떤 MST의 부분집합이 될 경우,
에지 (u ,v )는 A 에 대해서 안전하다 ( safe ) 라고 한다.

 

1. 처음 A는 공집합 이다.

2. 집합 A에 대해서 안전한 엣지를 하나 찾은 후 이것을 A에 더해준다.

3. 엣지의 개수가 n-1 개가 될 때까지 반복한다. ( MST는 노드가 n 개라면 항상 n-1 개의 엣지를 가진다. )

 

 

 

빨강 엣지들의 집합인 A가 어떤 MST의 부분집합이고 ( S , V - S )는 A를 존중하는 컷이라고 할때, ( S , V - S ) 를 cross 하는 엣지들 중 가중치가 가장 작은 엣지 (u,v) 는 A에 대하여 안전하다.
  => 엣지 (u,v)를 MST의 부분집합인 A에 넣어도 여전히 MST이다. ( 선택해도 된다.)

 

증명 :  아니라고 해보자.

A가 MST의 부분집합이고 엣지(u,v)는 MST에 포함하지 않는다고 해보자. 그런데 MST는 그래프의 모든 정점들을 서로 연결해야하므로 어디든 적어도 한번은 ( S , V-S )를 크로스 한다. 그 크로스 하는 엣지를 e 라고 해보자. 그럼 e 는 당연히 엣지(u,v) 보다 크다. 왜냐면 ( S,V-S ) 를 크로스하는 엣지중 가작 작은값이(u,v) 이므로 MST (미니멈)이라는 정의에 어긋난다.

 

---

 

1. Kruskal 알고리즘

- 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것.

- 간선 선택을 기반으로 하는 알고리즘 ( vs Prim 알고리즘은 정점을 선택하여 진행해나가는 알고리즘 )

- 이전 단계에서 만들어진 Spanning Tree 와 상관없이 무조건 최소 비용 간선만을 선택하는 방법. ( Greedy 한 방법 )

- 단 간선을 선택할때 해당 간선을 선택함으로서 사이클이 생기지 않는 간선을 택한다.

- 즉 이 간선을 선택했을때 사이클이 생기는지 안생기는지 유무를 검사해야 한다.

 

간선이 적은 그래프를 MST 로 만들 때 적합. (간선을 선택하기 때문에 비용 ▼)

 

[ 구현 과정 ]

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
 - 가장 낮은 가중치를 먼저 선택한다.
 - 사이클을 형성하는 간선을 제외한다.
3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.

 

구체적인 알고리즘 구현은 https://forward-movement.tistory.com/22

 

 

---

 

 

2. Prim 알고리즘

 

- 시작 정점에서부터 출발하여 MST 집합을 단계적으로 확장해나가는 방법.

- 정점 선택을 기반으로 하는 알고리즘.

- 이전 단계에서 만들어진 Spanning Tree 를 확정하는 방법.

- 즉 사이클 검사가 필요하지 않다.

 

간선이 많은 그래프를 MST 로 만들 때 적합.

 

[ 구현 과정 ]

1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
  - 가장 낮은 가중치를 먼저 선택한다.
3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

 

Prim 알고리즘은 kruskal과 구현 과정이 비슷하다. 다만 안전한 엣지를 찾는 과정이 조금 다르다.