그래프

[ttobaegi]

1. 크루스칼(Kruskal) 알고리즘

[ttobaegi]

크루스칼(Kruskal) 알고리즘

• 비용이 적은 간선부터 하나씩 선택하여 신장 트리를 만들어 가는 알고리즘
• 모든 간선을 비용 순으로 정렬한 다음 가중치 값이 작은 간선부터 차례대로 선택하여 신장 트리를 완성

문제 접근 방법

H = V(G)

입력 - 그래프 G ⇒ 불필요한 간선 제거 ⇒ 최소 비용 신장 트리 H 생성

1. 노드만 남겨 두고 간선을 모두 제거한다.
2. 가중치 값이 적은 간선부터 하나씩 추가. 가중치가 같은 간선일 경우 어느 간선을 선택해도 상관이 없다.
3. 추가로 순환을 일으키지 않는 '최소 가중치' 간선인지 체크한다.