728x90
MST란?
Minimum Spanning Tree의 약자로 최소신장트리 라고 불린다.
위 그림과 같이 그냥 Spanning Tree는 모든 정점이 연결되어 있는 Tree이다.
조금 더 구체적으로 말하면 모든 정점이 임의의 간선들을 거쳐 만날 수 있는 Tree이다.
따라서 MST는 최소한의 가중치로 모든 정점을 연결시킨 Tree이다.
MST를 만들 수 있는 알고리즘은 크게 2가지가 있는데 다음과 같다.
1) 크루스칼(kruskal) 알고리즘
2) 프림(prim) 알고리즘
1) 크루스칼 알고리즘 이란?
크루스칼 알고리즘이란 주어진 간선의 가중치를 기준으로 MST를 찾는 알고리즘이다.
크루스칼 알고리즘 구현을 위해 쓰이는 자료구조 및 개념 -> 우선순위큐, Union Find
2) 프림 알고리즘이란?
프림 알고리즘이란 임의의 정점으로부터 Tree영역을 늘려나가며 MST를 찾는 알고리즘이다.
프림 알고리즘 구현을 위해 쓰이는 자료구조 및 개념 -> 우선순위큐, visit 2중처리
자세한 개념은 다음에 ..
'자료구조, 알고리즘' 카테고리의 다른 글
| [알고리즘] 크루스칼(Kruskal) 알고리즘이란? (0) | 2022.03.30 |
|---|---|
| 우선순위 큐는 왜 힙 구조를 사용할까? (0) | 2022.03.01 |
| 힙(Heap)의 구조와 동작과정 (0) | 2022.03.01 |
| 트리(Tree)의 개념과 종류들 (0) | 2022.03.01 |
| 스택(Stack)과 큐(Queue) (0) | 2022.03.01 |
