[이산수학] 크루스칼(Kruskal) 알고리즘

 

 

크루스칼(Kruskal) 알고리즘

---

1. 알고리즘 개요

크루스칼 알고리즘은 임의의 그래프에서 최소 신장 트리를 찾는 알고리즘입니다. 크루스칼 알고리즘은 그래프 변의 가중치를 중심으로 알고리즘을 전개합니다.

 

1.1. 알고리즘 동작

1. 모든 그래프 변을 가중치 기준으로 오름차순 정렬합니다.
2. 가장 왼쪽에 위치한(=가중치가 작은) 변부터 트리에 추가합니다. 단, 기존 배치된 변과 사이클을 이룰 경우 추가하지 않고 건너뜁니다.
3. 신장 트리를 형성할 때까지 즉, 그래프 모든 꼭짓점을 포함할 때까지 2번 과정을 반복합니다.

 

2. 예시

그래프 예시

 

위와 같은 그래프가 있을 때, 크루스칼 알고리즘으로 아래 과정을 통해 최소 신장 트리를 찾을 수 있습니다.

크루스칼 알고리즘 예시

 

④과정에서 AD와 BC가 가중치 3으로 값이 같음에도 AD를 선택하지 않은 이유는 사이클을 형성하기 때문입니다.

---

연관 게시글

[이산수학] 그래프 - 트리

[이산수학] 그래프 - 트리

---

참조

•