포시코딩

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

자료구조알고리즘/이론

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

포시 2023. 4. 18. 05:48
728x90

신장 트리(Spanning Tree)

Spanning Tree 또는 신장 트리. Spanning Tree가 더 많이 사용된다.

원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프를 의미

 

신장 트리의 조건

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

 

최소 신장 트리(MST)

Minimum Spanning Tree, MST라고 불린다.

가능한 신장 트리(Spanning Tree)중에서, 사용된 간선들의 가중치 합이 최소인 Spanning Tree를 지칭한다.

그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재한다.

대표적인 최소 신장 트리 알고리즘은 아래와 같다.

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

 

대표적인 사용 예

  • 내비게이션
  • 통신 네트워크 구축

 

해당 포스팅에 한번에 정리하기엔 내용이 많아 따로 정리했다. 아래 링크에서 확인

크루스칼 알고리즘(Kruskal's algorithm)

https://4sii.tistory.com/527

 

[MST][최소 신장 트리] Kruskal's algorithm

크루스칼 알고리즘(Kruskal's algorithm) 탐욕 알고리즘을 기반으로 한다. 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 비용(가중치)을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두

4sii.tistory.com

 

프림 알고리즘(Prim's algorithm)

https://4sii.tistory.com/583

 

[MST][최소 신장 트리] Prim's algorithm

프림 알고리즘(Prim's algorithm) Kruskal's algorithm과 함께 대표적인 최소 신장 트리(Minimum Spanning Tree) 알고리즘 중 하나 Kruskal's algorithm보다 다소 복잡도가 올라간 알고리즘이다. 시작 정점을 선택한 후,

4sii.tistory.com

728x90
저작자표시

'자료구조알고리즘 > 이론' 카테고리의 다른 글

코딩테스트 관점에서의 시간복잡도  (0) 2023.04.18
[MST][최소 신장 트리] Kruskal's algorithm  (0) 2023.04.18
백트래킹(backtracking)  (0) 2023.04.16
그래프 - 최단 경로 알고리즘, 다익스트라 알고리즘  (0) 2023.04.16
알고리즘 코딩테스트를 대비해 외울 것들  (0) 2023.04.16
'자료구조알고리즘/이론' Related Articles more