28 lines
1.7 KiB
Markdown
28 lines
1.7 KiB
Markdown
deck:: Logseq/coding tip
|
||
|
||
- ## 1. 개념(Concept)
|
||
- **스패닝 트리(Spanning Tree)**
|
||
- 그래프의 모든 정점을 연결하는 트리를 의미하며, 정점이 $V$개면 간선은 항상 {{cloze $V-1$}}개.
|
||
id:: 6950f19e-3b2d-4a6e-a275-e24847b486be
|
||
- **최소 스패닝 트리(Minimum Spanning Tree)**
|
||
- 가중치가 있는 무방향 그래프에서 모든 정점을 연결하면서, {{cloze 간선 가중치 합}}이 최소가 되도록 고른 트리.
|
||
extra:: 스패닝 트리들 중 가중치 합이 최소인 트리
|
||
id:: 6950f0fd-13d7-4d6b-88c8-6d2fd1f1a732
|
||
- ## 2. 핵심 성질
|
||
- MST는 {{cloze 사이클}}을 가지지 않는다.
|
||
id:: 6950f2db-2f04-4e8d-adab-87f0a667cb0e
|
||
- MST가 유일한지 여부는 {{cloze 가중치 중복}} 등에 따라 달라진다.
|
||
extra:: 동일 가중치가 존재한다면 경우에 따라 여러개가 존재 할 수 있음.
|
||
id:: 6950f2f2-449b-4b90-a006-09fa3c4e2647
|
||
- ## 3. 구현 방법 및 비교
|
||
- ### 구현 알고리즘
|
||
- [[크루스칼 알고리즘(Kruskal’s Algorithm)]]
|
||
- 전체 간선 정렬 후 싼 것부터 추가하는 알고리즘
|
||
- {{cloze 간선의 개수가 적을 때 :: 크루스칼 알고리즘이 더 효율적인 경우는?}} 사용하기 유리하다.
|
||
extra:: 간선이 적은 그래프를 희소 그래프 (Sparse Graph) 라고 한다.
|
||
id:: 6951147c-369e-46ca-aebb-627ca0a1d63d
|
||
- [[프림 알고리즘 (Prim’s Algorithm)]]
|
||
- 시작점에서 조금씩 영역을 넓혀가는 알고리즘
|
||
- {{cloze 간선의 개수가 매우 많을 때 :: 프림 알고리즘이 더 효율적인 경우는?}} 사용하기 유리하다.
|
||
extra:: 간선이 매우 많은 그래프를 밀집 그래프 (Dense Graph) 라고 한다.
|
||
id:: 69511474-adb8-4eea-b8ba-617929628ee1 |