그래프 내의 모든 정점을 포함하는 트리
= 신장 트리
: 최소 연결 부분 그래프
Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
탐욕적인 방법(Greedy method)을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지 체크!!
-> 즉, 추가할 새로운 간선의 양끝 정점이 같은 집합에 속해 있으면 사이클이 형성된다.
사이클 생성 여부를 확인하는 방법
: 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사해야 한다.
: union-find 알고리즘 이용
import sys
v, e = map(int, input().split())
# 부모 테이블 초기화
parent=[i for i in (1, v+1)]
# find 연산
def find(x):
if parent[x] !=x:
parent[x]= find(parent[x])
return parent[x]
def union(a, b):
a=find(a)
b=find(b)
if a<b:
parent[b]=a
else:
parent[a] =b
# 간선 정보 담을 리스트와 최소 신장 트리 계산 변수 정의
edges=[]
total_cost=0
# 간선 정보 주어지고 비용을 기준으로 정렬
for _ in range(e):
a, b, c = map(int, input().split())
edges.append((c, a, b))
# 간선 정보 비용 기준으로 오름차순 정렬
edges.sort()
# 간선 정보 하나씩 확인하면서 크루스칼 알고리즘 수행
for i in range(e):
c, a, b = edges[i]
# find 연산 후, 부모 노드 다르면 사이클 발생하지 않으므로 union 연산 수행 -> 최소 신장 트리에 포함!
if find(a) != find(b):
union(a, b)
total_cost+=total_cost
print(total_cost)
그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합
시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장 해나가는 방법
그래프에 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 의 경우는 Prim 알고리즘이 적합