1.7 KiB
1.7 KiB
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
- 스패닝 트리(Spanning Tree)
-
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
- 크루스칼 알고리즘(Kruskal’s Algorithm)
-