[알고리즘] 최소신장트리, MST, 크루스칼/프림 알고리즘

_Spanning Tree 정의

Spanning Tree(신장트리)는 아래의 속성을 만족하는 그래프를 말한다.

• 원래의 그래프의 모든 노드를 포함
• 모든 노드가 서로 연결되어 있음
• 트리의 속성을 만족 ( 사이클이 존재하지 않음)

즉, 그래프의 최소 연결 부분 그래프이다.

• 최소 연결 = 간선의 수가 가장 적다
• N개의 노드를 가진 그래프
  • 최소 간선의 수 : N-1
  • (N-1)개의 간선으로 == 최소 간선으로 연결되어 있으며 트리의 형태이면 Spanning Tree

 

_Minimum Spanning Tree (MST)

가능한 Spanning Tree 중에서 간선의 가중치 합이 최소인 Spanning Tree

출처 : 위키백과

위 사진에서 첫 번째 그래프의 경우 2개의 MST를 가질 수 있다.

두번째, 세번째 트리가 모두 가중치의 합이 최소이기 때문에 최소신장트리의 조건을 만족한다.

 

_MST 구현방법

그래프에서 MST(최소 신장 트리)를 찾을 수 있는 알고리즘

• Kruskal's algorithm (크루스칼 알고리즘)
• Prim's algorithm (프림 알고리즘)

'algorithm & data structure' 카테고리의 다른 글

[알고리즘] 최소신장트리, MST, 크루스칼/프림 알고리즘  (0)	2020.12.11
[알고리즘] 정렬알고리즘 _ 버블, 선택, 삽입, 병합, 셸  (0)	2018.11.21
[알고리즘] 힙정렬(Heap Sort)  (0)	2018.10.25
[알고리즘] 퀵정렬(Quick Sort)  (0)	2018.10.25
[자료구조] 트리, 이진트리, 이진탐색트리  (0)	2018.10.24
[알고리즘] 레드블랙트리(red-black tree) - 특징, 삽입  (0)	2018.06.29