크루스칼 알고리즘 (1) - 동작 원리

 

 

이번 시간에는 크루스칼 알고리즘의 동작 원리를 살펴보겠습니다.

 

크루스칼 알고리즘(Kruskal Algorithm) - "가장 작은 값부터 잇자"

- 간선 비용이 가장 적은 것부터 이어나가되 사이클이 형성되지 않게 하는 최단 경로 알고리즘 입니다. 가장 좋은 것부터 찾아나가므로 그리디 알고리즘에 해당합니다.

 

 

위의 그래프를 비용이 가장 적은 것부터 차례대로 이어나갈 것입니다.

 

 

비용이 가장 적은 1을 잇습니다

 

그 다음으로 적은 2를 잇습니다

 

그 다음으로 적은 3을 잇습니다

 

그 다음으로 적은 4를 잇습니다. 같은 비용인 간선이 2개 있을 때는 왼쪽 상단에 있는 것부터 잇도록 하겠습니다. (오른쪽에서부터 이어도 상관 없습니다)

 

두 번째 4를 잇습니다

 

그 다음으로 적은 5를 이었으나 사이클이 형성되므로 제외합니다

 

그 다음으로 적은 6을 이었으나 사이클이 형성되므로 제외합니다

 

그 다음으로 적은 7을 이었으나 사이클이 형성되므로 제외합니다

 

그 다음으로 적은 8을 잇습니다

 

그 다음으로 적은 9를 이었으나 사이클이 형성되므로 제외합니다

 

그 다음으로 적은 10을 이었으나 사이클이 형성되므로 제외합니다

 

최소 비용 신장 부분 그래프가 완성 되었습니다 ^^

 

 

<출처>

위키백과: 크러스컬 알고리즘