[알고리즘] 최소 스패닝 트리(MST) - 크루스칼, 프림

최소 스패닝 트리(Minimum Spannig Tree) = 최소 신장 트리

: 스패닝 트리 중 가장 작은 가중치의 간선으로 구성된 트리를 의미한다.

 

 

조건

• 본래의 그래프의 모든 노드를 포함
• 간선의 가중치의 합이 최소여야 한다
• 모든 노드가 서로 연결되어있다
• 트리의 속성을 만족 (사이클이 존재하지 않는다)

↓스패닝 트리란?

스패닝 트리란? : 그래프의 최소 개수의 간선으로 이뤄진 트리 (n개의 노드가 존재한다면 간선은 항상 n-1개이다)

• 모든 노드가 연결되어야 함
• 사이클이 존재하지 않음
• 즉, 최소 스패닝 트리에서 최소 가중치의 합 조건만 빠진 트리를 의미.

 

 

 

 

 

 

이 최소 스패닝 트리 문제를 다루는 알고리즘에는 2가지가 있다.

 

 

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

: 두 노드 간 제일 작은 가중치의 간선을 선택하여 최소 스패닝 트리를 구성하는 알고리즘

 

 

동작원리

1. 간선을 오름차순으로 정렬

2. 정렬된 간선을 차례대로 선택

3. 만약 연결되지 않은 노드 간의 간선이라면 연결 (가중치의 합을 구한다면 이때 가중치를 더하기)

+ 사이클이 생기지 않아야 함

4. 모든 노드들이 연결될 때까지 반복 

 

크루스 칼 관련 문제, 풀이, 코드

 

 

 

 

 

 

 

2. 프림(Prim) 알고리즘

: 시작 노드를 시작으로 작은 가중치를 선택하여 뻗어나가며 최소 스패닝 트리를 구성하는 알고리즘

 

 

동작원리

1. 임의의 간선을 선택

2. 선택한 간선의 노드로부터 가장 작은 가중치를 갖는 노드를 선택

3. 모든 노드들이 선택될 때까지 반복

 

프림 관련 문제, 풀이, 코드

 

 

프림 알고리즘은 O(V^2) , O(ElogV) 복잡도를 갖는 2가지의 방법이 존재한다.

 

1. O(V^2)

: 배열을 사용하여, 연결되는 트리와 각 노드를 연결하는 최소 간선 가중치를 찾는 방법

 

다익스트라처럼 트리와 연결된 노드의 배열에 최소 가중치를 업데이트시키며 진행.

연결된 노드의 정보를 나타내는 배열을 업데이트시키며 연결되지 않은 노드 중 가중치가 최소인 간선을 찾아 트리에 포함시키면서 진행한다.

1) 임의의 노드를 선택하여 비어있는 트리에 포함시킨다. -> 노드가 한 개인 트리가 생성됨

2) 트리에 있는 노드와 트리에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

3) 찾은 간선에 연결된 노드를 트리에 포함시킨다.

4) 모든 노드가 트리에 포함될 때까지 반복한다.

 

 

2.O(ElogV)

: 힙 ( min heap )을 사용해 최소의 간선 가중치를 찾는 방법

 

 1번 방법에서는 다익스트라처럼 배열로 간선의 정보를 저장하며 진행하였지만, 트리 안에 있는 노드가 출발점인 간선들을 배열이 아닌 최소 힙(PriorityQueue)에 넣어서 사용하게 된다.

 

1) 임의의 노드를 선택하여 비어있는 트리에 포함시킨다. -> 노드가 한 개인 트리가 생성됨

2) 트리에 있는 노드와 트리에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

3) 찾은 간선에 연결된 노드를 트리에 포함시킨다.

4) 모든 노드가 트리에 포함될 때까지 반복한다.

 

 

 

 

 

 

 

 

 

크루스 칼(Kruskal) 알고리즘 Vs 프림(Prim) 알고리즘

특징을 살펴 상황에 따라 적절한 알고리즘을 선택하여 문제를 풀이하면 된다.

 

크루스칼	프림
간선 위주	노드 위주
최소비용 간선 차례로 선택 하므로 사이클 확인 필요 O	시작노드 -> 가까운 노드 순으로 트리 구성하므로 사이클 X
간선의 개수가 적은경우 적합	간선의 개수가 보다 많은 경우 적합
간선 정렬 필요하므로 정렬과정 오래걸림	최소 거리 노드 찾는 부분에서 자료구조의 성능에 영향받음

 

 

 

 

 

 

 

참고 사이트 1-프림 알고리즘(코드)

참고 사이트 2