[자료구조 C 언어] C 프로그래밍 자료구조 - 17 : 그래프(3) 최소 신장 트리 (MST): Kruskal, Prim 알고리즘

단순한 정리와 활용을 원하시는 분은 마지막 코드를 참조해주세요.

주석만으로도 충분히 이해하실 수 있습니다.

 

이번에는 최소 비용 신장 트리에 관해 설명드리겠습니다.

 

1. 최소 비용 신장 트리

 

저번 시간에 공부한 것과 같이 '신장 트리'는 '그래프 내의 모든 정점을 포함하는 트리'를 뜻합니다.

 

최소 비용 신장 트리에 관한 내용은 다음과 같습니다.

 

  1) 비용: 가중치가 부여된 무방향 그래프에서 신장 트리의 비용은 신장 트리를 구성하는 edge들의 비용의 합

 

  2) 최소 비용 신장 트리: 가장 비용이 적은 신장 트리

 

목표된 정점들을 이어 줄 간선을 정할 때 가장 적은 비용으로 모든 정점을 이을 수 있는 방법을 찾는 것이 핵심입니다.

 

응용 분야는 다음과 같습니다.

 

  1) 도로 건설: 도시를 모두 연결하면서 도로의 길이가 최소가 되도록 한다.

 

  2) 통신: 통신선의 길이를 최소가 되도록 한다.

 

  3) 배관: 파이크가 서로 모두 연결되면서, 사용된 파이프의 길이가 최소가 되도록 한다.

 

 

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

 

최소 비용 신장 트리의 알고리즘을 구성할 때 제약 조건은 다음과 같습니다.

 

  1) 그래프 내에 존재하는 edge들만 사용합니다.

 

  2) n-1개의 edge만 사용합니다. (정점(vertex)의 수 = n)

 

  3) 사이클을 형성할 수 있는 edge는 사용 불가합니다.

 

알고리즘의 종류는 대표적으로 다음의 세가지가 존재합니다.

 

  1) Kruskal의 알고리즘

 

  2) Prim의 알고리즘

 

  3) Sollin의 알고리즘

 

해당 게시물에선 Kruskal과 Prim 알고리즘만 구현해보겠습니다.

 

Solin은 추가 게시물로 설명 드리겠습니다.

 

 

3. Kruskal의 알고리즘

 

3-1. 개요

 

Edge들의 비용 (가중치)을 오름차순으로 정렬합니다.

 

정렬된 edge들 중에서 가장 비용이 적은 edge 부터 하나씩 선택합니다.

 

이때, 선택된 edge는 기존에 선택된 edge들과 사이클을 형성하지 않을 경우에만 신장 트리 T에 포함될 수 있습니다.

 

그래프 G가 연결되어 있으면, n > 0 개의 vertex가 존재할 경우, 정확히 n-1 개의 edge가 선택됩니다.

--> 따라서 그래프 G에 n-1 보다 작은 수의 edge가 존재하면 최소 신장 트리는 구성될 수 없습니다.

 

 

3-2. 알고리즘 예시

 

 

3-3. 동작 예시

 

 

 

 

4. Prim의 알고리즘

 

4-1. 개요

 

하나의 vertex만 갖는 트리 T에서 시작합니다.

 

T에 포함된 vertex와 포함되지 않는 vertex를 연결하는 edge 중에서 최소 비용을 갖는 edge를 T에 추가합니다.

 

추가된 edge의 vertex를 T에 포함합니다.

 

 

4-2. 알고리즘 예시

 

Kruskal 알고리즘과 달리 사이클을 검사하는 부분이 없습니다.

 

항상 방문하지 않은 정점에 대한 가중치 정보만 이용하기 때문입니다.

 

 

 

4-3. 동작 예시

 

 

 

5. Sollin의 알고리즘 (Greedy Strategy 개념을 사용합니다.)

 

5-1. 개요

 

크게 생각하면 각자 vertex를 모두 서로 다른 컴퓨터에 맡기고,

 

각각의 컴퓨터에서 할당된 vertex에서 다른 vertex로 연결 될 edge를 찾아 모든 edge를 취합하는 것 입니다.

 

해당 알고리즘은 여러 edge들을 선택하는 과정이 병렬로 진행될 수 있는 것이 특징입니다.

 

 

(1)

일단, 단계별로 T에 포함시킬 여러 edge들을 동시에 선택합니다.

 

각 단계에서 선택 된 edge들은그래프의 신장 숲 (Spanning Tree)을 구성합니다.

 

초기에는 edge가 없으므로, forest에 vertex 수 만큼의 트리가 존재합니다.

 

각 단계 에서 forest에 있는 각 트리에 대해 하나의 edge를 선택 (선택 기준은 가장 비용이 적은 edge)

 

하나의 트리만 남거나, 혹은 추가할 edge가 없을 경우 종료

 

 

(2)

쉽게 얘기 하면,

 

(A) edge 없이 vertex들을 흩뿌려 놓은 상태가 forest입니다.

 

(B) 하나의 트리에 대해 다른 vertex와 연결할 수 있는 edge 중 가장 비용이 적은 edge를 선택해 추가합니다.

 

이때, 중복되는 경우에 edge는 그중 먼저 연결된 하나의 edge만 추가합니다.

 

(C) 트리가 하나 남거나, 추가할 dege가 없을 때까지 (B) 알고리즘을 반복하고 종료합니다.

 

참고: https://etst.tistory.com/64

 

 

5-2. 동작 예시

 

 

 

 

6. 코드

 

해당 게시물을 참조해주세요.

 

2020/05/13 - [공부/c언어 자료구조] - [자료구조 C 언어] 부록 - 1: 최소비용 신장트리 MST_Kruskal 알고리즘

 

2020/05/14 - [분류 전체보기] - [자료구조 C 언어] 부록 - 2: 최소비용 신장트리 MST_Prim 알고리즘