Minimum Spanning Tree (최소 신장 트리)

Spanning Tree (신장 트리)

  : 그래프의 최소 연결 부분 그래프.

    최소 연결 -> 간선의 수가 최소

    n개의 정점을 가지는 그래프의 최소 간선의 수: n-1

    n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다. => ST

    즉, 그래프에서 일부 간선을 선택해서 만든 트리.

 

출처 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

 

• Spanning Tree의 특징

하나의 그래프에는 여러 개의 신장 트리가 존재 가능.

 

ST는 트리의 특수 형태

=> 모든 정점들 연결

=> 사이클 포함 x

 

=> N개의 정점을 정확히 n-1개의 간선으로 연결

 

 

---

 

 

Minimum Spanning Tree (최소 신장 트리)

  : Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

 

   각 간선의 가중치가 상이할 때 단순히 간선 수를 가장 적게 사용한다고 해서 최소 비용이 얻어지는 것이 아님.

   MST => 간선의 가중치를 고려하여 최소비용의 Spanning Tree를 선택하는 것

 

• Minimum Spanning Tree의 특징

1. 간선의 가중치의 합이 최소
2. N개의 정점, n-1개의 간선 (ST의 특징)
3. 사이클 x (ST의 특징)

 

• Minimum Spanning Tree의 예시

도로건설, 전기회로, 통신, 배관

 

 

---

 

 

Prim 알고리즘

: 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장하는 방법

 

• 정점 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법   

 

• Prim 과정

1. In 시작 단계, MST 집합에는 시작 정점만 포함
2. 1단계에서 만들어진 MST 집합에 인접한 정점들 중 최소 간선으로 연결된 정점을 선택                                     -> 트리 확장 (최소 가중치부터 선택)
3. 위 단계를 트리가 n-1개의 간선을 가질 때까지 반복

2021.07.21 - [HUFS/Algorithm] - Prim Algorithm

 

 

 

---

 

 

Kruskal 알고리즘

: 그리디 방법을 사용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

 

• 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택
• 간선 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리와 무관하게 무조건 최소 비용 간선 선택

 

• Kruskal 과정

1. 그래프의 간선들을 가중치를 기준으로 오름차순 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택                                                           -> 최소 가중치 먼저 선택, 사이클 형성하는 간선은 제외
3. 해당 간선을 현재의 MST 집합에 추가

2021.07.21 - [HUFS/Algorithm] - Kruskal Algorithm

 

 

---

 

 

Prim vs. Kruskal

참고 : https://velog.io/@fldfls/%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC-MST-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

두 알고리즘의 차이는 

Prim : 우선순위 큐를 활용하여 임의의 시작점으로 부터 연결되는 가장 가중치가 낮은 간선부터 방문하는지

Kruskal : 간선의 리스트를 만들고 이를 정렬하여 가장 낮은 가중치의 간선부터 방문하는지

 

 

 

 

 

 

참고 : HUFS 알고리즘 강의자료 

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

https://godls036.tistory.com/26