크루스칼 MST 시각화
간선을 가중치 순으로 선택하여 최소 신장 트리를 구성하는 그리디 알고리즘을 학습합니다
그래프★★☆
속도
1 / 1MST 간선: 0총 가중치: 0
MST 간선 검사 중 스킵 (사이클) 미방문
크루스칼이 가중치 순으로 간선을 선택하여 MST를 구성하는 과정을 관찰하세요.
크루스칼이 가중치 순으로 간선을 선택하여 MST를 구성하는 과정을 관찰하세요.
크루스칼 알고리즘이란?
크루스칼(Kruskal) 알고리즘은 가중치가 있는 무방향 그래프에서 최소 신장 트리(MST)를 구성하는 그리디 알고리즘입니다. 1956년 조지프 크루스칼이 발명했으며, 모든 정점을 최소 비용으로 연결하는 트리를 찾습니다. Union-Find 자료구조를 활용하여 사이클을 효율적으로 검출합니다.
사용 방법
- 1새 그래프 버튼으로 랜덤 가중치 그래프를 생성하세요
- 2재생 버튼을 누르면 간선이 가중치 순으로 정렬됩니다
- 3각 간선이 사이클을 형성하는지 Union-Find로 검사합니다
- 4사이클이 없으면 MST에 추가(초록), 있으면 스킵(빨강)됩니다
- 5노드를 드래그하여 그래프 레이아웃을 조정할 수 있습니다
학습 팁
- •크루스칼은 간선 중심 알고리즘으로, 프림(Prim)은 정점 중심입니다
- •간선이 적은 희소 그래프에서 크루스칼이 더 효율적입니다
- •Union-Find의 경로 압축과 랭크 합치기로 거의 O(1) 연산이 가능합니다
- •MST는 V-1개의 간선으로 구성됩니다 (V: 정점 수)
자주 묻는 질문
Q. 크루스칼 vs 프림 알고리즘, 언제 어떤 것을 쓰나요?
A. 크루스칼: 간선을 정렬하여 선택하므로, 간선이 적은 희소 그래프에서 O(E log E)로 효율적입니다. 프림: 정점 기반으로 확장하므로, 간선이 많은 밀집 그래프에서 O(V^2) 또는 힙 사용 시 O(E log V)로 유리합니다.
Q. MST가 유일한가요?
A. 모든 간선의 가중치가 서로 다르면 MST는 유일합니다. 같은 가중치의 간선이 있으면 여러 MST가 존재할 수 있습니다.