최소 비용 신장 트리 알고리즘

1. 그래프 이론

1.1. 간선

1.2. 가중치

1.3. 경로

1.4. 단순 경로

1.5. 사이클

1.6. 그래프

2. 신장 트리(spanning tree)

3. 최소 비용 신장 트리(minimum spanning tree, 이하 MST)

4. 최소 비용 신장 트리 알고리즘

4.1. 정의

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

1. 그래프 이론

1.1. 간선

정점을 잇는 선분

1.2. 가중치

변 위의 숫자

1.3. 경로

두 개의 정점을 잇는 간선을 순서대로 나열한 것

1.4. 단순 경로

동일한 간선을 중복하여 포함하지 않는 경로

1.5. 사이클

자기 자신으로 되돌아오는 경우

1.6. 그래프

연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조

2. 신장 트리(spanning tree)

- 신장 트리: 사이클을 형성하지 않는 그래프
- n개의 지점을 모든 점들이 서로 도달 가능하면서 전체 거리의 합이 최소가 되도록 연결한 트리 구조의 그래프
-

3. 최소 비용 신장 트리(minimum spanning tree, 이하 MST)

최소 비용 신장 트리: 간선의 가중치의 합이 최소인 신장 트리

4. 최소 비용 신장 트리 알고리즘

4.1. 정의

그래프의 신장 트리 중에서 가중치의 합이 최소인 신장 트리

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

- 이런 최소 비용 신장 트리를 구하는 대표적인 방법으로는 크루스칼 Kruskal) 알고리즘이 있다, 크루스칼 알고리즘은 간선을 정렬한 후에 하나씩 그려나가는 방식이다. 먼저 크루스칼 알고리즘의 흐름은 다음과 같다.
1. 비용을 기준으로 간선을 적은 것부터 큰 것 순으로 정렬한다.
2.적은 비용의 간선부터 하나씩 그린다. (사이클을 만들게 되는 간선은 그리지 않는다.)
3.모든 정점이 선으로 연결될 때까지 2의 과정을 계속한다.
이제 직접 위의 흐름대로 따라 해보자. 다음의 그래프를 크루스칼 알고리즘으로 최소 비용 신장 트리로 만들어보자.
먼저 비용이 작은 간선부터 큰 순서대로 정렬하면 다음과 같다.
1, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18
현재 비용이 1, 3, 4, 5, 6, 7인 간선들이 그려진 상태이다. 여기까지는 앞에서부터 순서대로 그려나가면 된다. 이제 다음 순서인 비용이 8인 간선을 그릴 차례이다. 하지만 이를 그리면 정점 Ⓒ, Ⓓ, Ⓕ, Ⓖ를 잇는 사이클이 생기게 된다. 최소 비용 신장 트리는 사이클이 포함되면 안 되기 때문에 비용이 8인 간선은 그리면 안 된다. 다음은 8인 간선을 그려서 사이클이 발생했을 경우를 나타낸다.

<비용이 8인 간선을 그렸을 때 발생하는 사이클 >

<비용이 10인 간선을 그렸을 때 발생하는 사이클 >

또 다음 간선으로 넘어가보자. 비용이 11인 간선은 그려도 사이클이 생기지 않는다. 비용이 11인 간선을 추가한 그림은 다음과 같다.
이제 모든 정점들이 선으로 연결되었다. 따라서 비용이 12 이상인 간선들은 그릴 필요가 없다. 이로써 최소 비용 신장 트리가 완성된 것이다. 추가적으로 최소 비용 신장 트리가 완성되었는지 확인하는 방법은 다음의 식이 성립하는지 보면 된다.
간선의 수 + 1 = 정점의 수
위의 식이 왜 성립하는지는 그래프를 작은 것부터 그려나가 보면 이해할 수 있다. 먼저 정점이 2개일 때를 그려보자. 정점이 2개일 때는 1개의 간선이 필요하다. 정점이 3개일 때는 간선이 2개가 필요하다. 이런 식으로 정점을 하나씩 추가할 때마다 간선도 하나씩 더 필요하게 된다. 따라서 항상 정점은 간선보다 하나가 더 많게 된다.

분류

알고리즘