스패닝 트리 (Spanning Tree)

신장 트리

그래프 내의 모든 정점을 포함하는 트리(Tree) = 최소 연결 부분 그래프(Graph)
즉, 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 트리

특징

- DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있음 ( 탐색 중 사용된 간선만 합 )
- 하나의 그래프에는 많은 신장 트리가 존재할 수 있음
- 모든 정점들이 연결되어 있어야 하고, 사이클을 포함해선 안됨
- n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개
    = 그래프가 (n-1)의 간선으로 연결되어 있으면 필연적으로 트리 형태
    = 그것이 스패닝 트리 (= Spanning Tree)

---

최소 스패닝 트리 (Minimum Spanning Tree)

최소 (비용) 신장 트리

신장 트리들 중 간선의 가중치 합이 가장 작은 트리(Tree)

특징

각 간선의 가중치가 동일하지 않을 때, 가장 적은 간선을 사용하는 것이 최소 비용이 아님
MST는 간선 간의 가중치를 고려하여 최소비용의 Spanning Tree를 선택
= 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것

• 간선의 수가 적은 Sparse Graph : 크루스칼 알고리즘이 유리
• 간선의 수가 많은 Dense Graph : 프림 알고리즘이 유리하다.
  
  

[ 활용 예시 ]
- 크루스칼 알고리즘 (Kruskal Algorithm)
- 프림 알고리즘 (Prim Algorithm)
- 솔린 알고리즘 (Solling Algorithm)

---

크루스칼 알고리즘

탐욕 기법(Greedy Algorithm) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

조건

1) 최소 비용의 간선으로 구성됨
2) 사이클을 포함하지 않음

• 위의 두 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택
• 간선 선택을 기반으로 하는 알고리즘이다.
• 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법 ( Union-Find )
  
  

원리

1. 그래프의 간선들을 가중치의 오름차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택
   = 즉, 가장 낮은 가중치를 먼저 선택
3. 사이클을 형성하는 간선을 제외
4. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가
   
   

복잡도

[ 간선의 개수 = E ]
탐색 : O(상수)
정렬 : O( E log E )

• 크루스칼 알고리즘은 정렬하는 데 더 긴 시간이 걸리므로 O(E log E)

---

예제

import sys
input = sys.stdin.readline

# vertexs[a]가 a가 아닌 경우(vertexs 리스트는 value가 인덱스 번호 순으로 되어있음)
# vertex[a]에 할당되어 있는 값을 리턴
def find_node(vertexs, a):
  if vertexs[a] != a:
    vertexs[a] = find_node(vertexs, vertexs[a])
  return vertexs[a]

def union_node(vertexs, a, b):
  a = find_node(vertexs, a)
  b = find_node(vertexs, b)
  
  if a < b:
    vertexs[b] = a
  else:
    vertexs[a] = b

node, edge = map(int, input().split())

edges = []
result = 0

# 1부터 node 까지 노드배열 생성
vertexs = [ i for i in range(node+1)]

for _ in range(edge):
# 시작 노드, 도착 노드, 노드 사이의 가중치를 저장
  start, end, weight = map(int, input().split())
  edges.append([start, end, weight])

# 가중치를 기준으로 오름차순 정렬
edges.sort(key=lambda edge: edge[2])

# 사이클이 발생하지 않을 때만 집합에 포함
for start, end, weight in edges:
  if find_node(vertexs, start) != find_node(vertexs, end):
    union_node(vertexs, start, end)
    result += weight

sys.stdout.write(str(result))

---

프림 알고리즘

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법

• 정점 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법

원리

1. 시작 단계에서는 시작 정점만이 MST 집합에 포함
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장
   = 즉, 가장 낮은 가중치를 먼저 선택
3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복