SLENDER ANKLES's 개발블로그

앞써 설명했던 최소 비용 스패닝 트리를 구하는 알고리즘 2번째, 크루스칼 알고리즘이다.

크루스칼 알고리즘 역시 Greedy 알고리즘의 방법으로 구한다. 

크루스칼(Kruskal) 알고리즘

로직은 다음과 같습니다.

1. 비용을 기준으로 간선을 적은 것부터 큰 것 순으로 정렬한다.

2. 적은 비용의 간선부터 하나씩 그린다.(사이클을 만들게 되는 간선은 그리지 않는다)

3. 모든 정점이 선으로 연결될 때까지 2의 과정을 계속한다.

1) 그래프가 주어집니다.

2) 가중치가 낮은 엣지들 순으로 정렬합니다.

3 - 1) 가중치가 낮은 엣지들을 순으로 엣지를 선택해줍니다.

3 - 2) 사이클이 발생하면 사이클 중에 가장 가중치가 높은 선을 선택하지 않고 넘어갑니다.

4) 모든 노드들이 엣지로 연결되면 최소 비용 스패닝 트리가 완성됩니다. 

엣지의 개수는 (노드의 개수 - 1)입니다.

최소 비용 스패닝 트리

그래프의 서브 그래프 중에 모든 vertex를 가지고 있고, edge를 가지는 것을 스패닝 트리라고 한다.

가중치가 있는 그래프에서 이러한 스패닝 트리 중에서 최소 비용인 것을 최소 비용 스패닝 트리라고 한다. 

신장 트리의 중요한 요건

하나, 순환이 되어서는 안 된다.

잠시만!!

최소 비용 스패닝 트리는 실제로 어디에 쓸 수 있을까? 맹목적으로 알고리즘을 배우고 외우는 것 보다 어디에 쓰일 수 있는지에 대해서 알면 좀 더 필요서이 생길 것 같다. 

필요한 상황에 대해서 한 번 예를 들어보겠다. 우리가 위치기반 서비스를 통해 가장 서울 지역 관광 명소를 현재 위치를 기반으로 최소의 거리 비용으로 돌 수 있는 서비스를 만들고 있다고 쳐보자.

위의 경우에 우리는 최소의 비용으로 관광지를 모두 돌 수 있는 알고리즘이 필요하다. 이러한 상황에서 최소 비용 스패닝 트리 알고리즘을 적용 해 볼 수 있을 것이다.

최소 비용 스패닝 트리를 구하기 위한 몇 가지 용어들에 대해서 알아두어야 한다.

트리(tree)정점 : 지금까지 만든 트리에 속하는 정점

주변확인(fringe) 정점 : 트리에는 속하지 않고, 트리에 속한 정점과 인접한 정점

미확인(unseen) 정점 : 나머지 정점들

프림(Prim) 알고리즘

모든 정점을 미확인 정점으로 초기화한다.

임의의 정점 s를 출발정점으로 한다. 

s에 인접한 모든 정점을 주변 정점으로 둔다. 

while(주변 정점이 있으면)

{

트리 정점 t와 주변 정점들 사이의 최소 가중치를 가진 에지 tv를 선택한다.

v를 트리 정점으로 둔다. 에지 tv를 트리에 추가한다.

v에 인접한 모든 미확인 정점을 주변정점으로 한다. 

}

다음의 그래프를 통해 prim알고리즘을 통해 greedy한 방법으로 최소비용스패닝트리를 구하는 과정을 설명하겠다.