[알고리즘] MST(Minimum Spanning Tree, 최소 신장 트리) - Prim(프림), Kruskal(크루스칼) 알고리즘

 

목차

• Spanning Tree 개념
• MST(최소 신장 트리) 개념
• Prim's Algorithm
• Kruskal's Algorithm

 

Spanning Tree (신장 트리)

• 그래프 내의 모든 정점들을 포함하는 그래프의 부분집합(subgraph) Tree
• 최소한의 간선들로 그래프 내의 모든 정점을 포함
  - 따라서 Spanning Tree는 cycle을 포함하지 않음
  - 그래프 내의 정점의 수가 n개이면, Spanning Tree는 (n-1) 개의 간선을 가짐
• 한 그래프 내의 여러 개의 Spanning Tree가 있을 수 있음

출처: https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm

 

 

 

MST (Minimum Spanning Tree, 최소 신장 트리)

• 가중치가 있는 그래프(weighted graph)에서 최소 가중치를 가진 Spanning Tree
• 즉, 한 그래프 내의 여러 개의 Spanning Tree 중 minimum weight을 가진 Spanning Tree
• MST를 구하는 대표적인 알고리즘으로는 Prim과 Kruskal 알고리즘이 있음

 

 

 

 

Prim's Algorithm

프림 알고리즘은 Tree에 포함되지 않은 정점들 가운데, 이미 포함된 정점과 가장 가까운 정점을 선택해서 해당 간선을 추가하는 방식이다. 

 

V : 그래프의 모든 정점들의 집합

F : MST에 포함된 간선들의 집합

Y : MST에 포함된 정점들의 집합, Y = V가 되면 MST를 구현한 것

 

첫 번째 정점을 v1이라고 하면 F = { }, Y = { v1 }으로 초기화해준다. 이는 아직 선택된 간선이 없고, v1부터 알고리즘을 수행한다는 의미이다. 

 

Y=V가 될 때까지 다음 과정을 반복한다. 

1. (V - Y)의 정점들 중 Y와 가장 가까운 정점 A를 선택한다. 
2. Y에 정점 A를 추가한다. 
3. F에 간선을 추가한다. 

 

Y=V가 되어서 MST가 완성되면 F는 MST의 모든 간선을 포함한 집합이 되므로 F의 원소 개수는 (n-1)개가 된다. 

 

Prim's Algorithm

 

 

 

 

Kruskal's Algorithm

크루스칼 알고리즘은 각 정점을 하나의 원소로 갖는 V의 서로소 집합을 만들어서 시작한다.

 

n개의 정점을 가진 그래프라면 처음에 n개의 서로소 부분집합들로 시작하고, 이 집합들은 각 정점만을 원소로 가진다. 이후 간선들의 집합 E를 가중치를 기준으로 오름차순으로 정렬한다. 그리고 하나의 집합이 남을 때까지 다음을 반복한다. 

1. 간선들의 집합 E에서 다음 간선을 선택한다. 
2. 만약 간선이 서로소 부분집합에 있는 두 개의 정점을 연결한다면
   1) 두 집합을 합친다. 
   2) 간선을 F에 추가한다. (F는 MST에 포함되는 간선들의 집합)

 

모든 부분집합들이 합쳐지고 나면 F는 MST의 모든 간선을 포함한 집합이 되므로 F의 원소 개수는 (n-1)개가 된다. 

 

Kruskal's Algorithm

 

 

 

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)