[ 자료 구조 ] 신장 트리 / 최소 비용 신장 트리 / 프림 알고리즘, 크루스칼 알고리즘

트리는 사이클이 없는 연결 그래프

그래프에 대한 설명글은 👇🏻

https://tildacoderecorder.tistory.com/107

[ 자료 구조 ] 그래프의 개념과 구조

 

신장 트리

: n개의 정점으로 이루어진 무방향 그래프G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리

깊이 우선 신장 트리 : 깊이 우선 탐색을 이용해 생성된 신장 트리

너비 우선 신장 트리 : 너비 우선 탐색을 이용해 생성된 신장 트리

 

최소 비용 신장 트리

: 무방향 가중치 그래프에서 신장 트리를 구성하는 간선 들의 가중치 합이 최소인 신장 트리

최소 비용 신장 트리를 만드는 알고리즘

• 프림 알고리즘
• 크루스칼의 알고리즘

 

프림 알고리즘

: 간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나가는 방법

1. 그래프 G에서 시작 정점을 선택한다.
2. 선택한 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 연결하여 트리를 확장한다.
3. 이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 삽입한다. 단, 사이클을 형성하면 안되므로 이런 경우에는 그 다음으로 낮은 가중치를 가진 간선을 선택한다.
4. 그래프 G에 n-1개 삽입될 때 까지 위 과정을 반복한다.

 

위 그래프를 예시로 시작 정점이 A일 때, A와 연결된 간선들의 가중치는 17, 6, 3이다. 이 중 가장 낮은 가중치를 가진 간선은 (A, B)로 3이다. 정점 A와 정점 B를 이어 트리를 확장한다.

두 정점에서 연결된 간선들의 가중치는 A와 연결된 17과 6, B와 연결된 5와 12가 있는데 이 중 가장 낮은 가중치를 가진 간선은 (B, D)이므로 이 둘을 연결하여 트리를 확장한다.

세 정점에서 연결된 간선들 중 가중치가 가장 낮은 간선은 6인데, A와 D를 이으면 사이클이 되므로 잇지 않는다. (A, D)를 제외한 간선 중 가중치가 가장 낮은 것은 (D, E)이므로 이 둘을 연결한다.

위와 같은 과정을 n-1번, 즉 6번 반복한다면 아래와 같은 최소 비용 신장 트리를 확인할 수 있다.

 

 

크루스칼 알고리즘

: 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 방법

1. 그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정리한다.
2. 그래프 G에 가중치가 가장 낮은 간선을 삽입한다. 이 때, 사이클을 형성하면 안되므로 이런 경우 그 다음으로 낮은 가중치를 가진 간선을 삽입한다.
3. 그래프 G에 간선이 n-1개 삽입될 때 까지 반복한다.

 

위에서 사용한 그래프의 간선들을 가중치에 따라 오름차순으로 정렬했다.

가중치가 가장 낮은 간선 (E, G)를 연결한다. 그 다음 가중치를 가진 (A, B)도 연결한다. 그 다음 가중치를 가진 (E, F)도 연결한다. (B, D)도 연결.

하지만 이 때, 가중치 6을 가진 (A, D)를 연결하면 사이클이 만들어지므로 연결하지 않는다. 그 다음 간선 (C, F)는 연결해도 사이클이 생기지 않으니 연결. (D, E)도 연결.

(C, E)를 연결하면 사이클이 생기므로 연결하지 않는다. 끝까지 반복해도 좋지만 여기까지 넘어오기 이전에 이미 간선을 연결하는 작업을 n-1번, 6번 했으므로 신장 트리는 완성된 상태이다. 더 이상의 반복은 무의미하다.

 

반복이 끝나면 위와 같은 최소 비용 신장 트리가 만들어진다. 프림 알고리즘의 결과와 동일하다.

 

참고 : C로 배우는 쉬운 자료구조 / 이지영 / 한빛아카데미