MST, 최소 신장 트리 [CPP]

정의는

정점의 집합 V와 가중치를 갖는 간선의 집합 E로 구성된 그래프 

G = <V, E> 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오

 

다시 쉽게 말하면

최소 비용으로 모두를 잇는 방법이라고 볼 수 있다.

 

아래 그림을 보자

 

 

 

 

어떤 알고리즘에 의해 만들어졌을까?

**이 아이디어는 Kruskal's Algorithm이라고도 부른다.

매 반복마다 최소 값을 꺼내기 때문에 Greedy라고도 부른다.

 

1. 그래프의 주어진 모든 간선을 최소힙(Min Heap) H 에 추가한다.

2. H로부터 간선, e을 하나 꺼낸다.

3. 해당 간선의 양 끝점이 T에 있는 경우 e 때문에 cycle이 발생할 수 있으니  e를 버리고 다시 2 단계로 돌아간다.

4. 해당 간선을 T, 트리에 추가시키고 다시 2 단계로 이동한다.

 

**즉, 우리는 주어진 정점과 간선만으로 최소 신장 트리를 만드는 것이다.

다시 말해서 해당 정점에 이어진 간선이 없다면 처음부터 만들지를 못한다는 뜻이다.

 

해당 방법이 정말 최소인지 검증은 우리는 하지 않는다.

공학자는 수학자가 검증하면 가져다 쓰는 것에 족하자

 

---

 

알고리즘은 간단하다.

근데 구현을 어떻게 할까가 문제다.

1,2 단계야 쉽지

3 단계에서 해당 edge에 대해서 cycle이 발생할 지에 대해서 판단해야 한다.

사실 MST의 핵심은 3단계다.

 

이것을 Union-Find, Disjoint-Set이라는 자료구조로 Tree 형태를 가지게끔 표현되는데

이를 통해 Cycle이 만들어지는지 확인할 것이다.

 

각각의 원소는 숫자 ID로 표현되고 부모에 대한 포인터를 가진다.

 

 

 

이 자료구조에서 핵심은 해당 노드에 대한 루트 노드를 찾는 것이다.

그 루트 노드를 찾는 것을 이용해서

union(x,y) 같은 것을 만들어내는데

x와 y의 루트노드를 찾아서 같다면 같은 트리에 속해 있음을 나타내고 아무런 작업을 하지 않고

(루트 노드가 같다면 cycle이 발생한다는 의미다)

 

만약 다르다면 낮은 레벨(level)의 루트노드를 부모로 설정한다.

(Tree가 확장된다)

 

**Tree에서 레벨은 무엇을 뜻하는지는 직접 찾아보자.

 

여기서 x,y는 Min Heap에서 꺼낸 edge의 양 끝 정점이겠지?

 

다른 분 깃헙에서 주웠다.

 

 

여기서 생각해볼 점은 Root Node가 같다면 왜 Cycle이 발생할까?

당연하지만 그냥 받아들이지 말고 한 번 생각해보고 넘어가자

루트 노드가 같다는 것은 (a,b)가 연결되어있다는 것을 의미한다.

즉, c와 a가 연결되어 있고 c와 b가 연결되어 있다면

a,b를 연결하게 된다면  c -> a -> b ->c 와 같은 Cycle이 생겨버린다.

즉, Tree 구조가 깨져버리는 것이다.

왜 Tree구조로 구현했는지 간접적으로나마 알 것 같다.

 

---

 

다른 분이 또 MST에 대한 알고리즘을 만들어놨다.

Prim's Algorithm이다.

 

이 알고리즘은 어떠한 방법으로 MST를 구현할 수 있을까?

BFS 방식과 유사하다.

 

BFS와 마찬가지로 시작 정점이 필요하고시작 정점을 이용해서 한 단계씩 나아가는 방식이다.경계는 이전에 방문했던 정점들에 의해 구성되고, 현재 경계에 인접한 정점을 반복적으로 탐색한다.여기서 프림 알고리즘이 경계를 넘는 간선 중 가장 가중치가 작은 간선을 선택하고 이 간선에 연결된 정점을 방문하게 한다.

사실 이렇게 들으면 잘 모르겠다.

 

단계는 이렇다.

1. 모든 정점의 거리 값을 무한대로 초기화시킨다( 위 그림에선 다름)  또한 시작 정점에서 자기 자신까지의 거리는 0이므로 시작 정점의 거리 값은 0으로 설정한다. 그리고 모든 거리 값을 최소 힙 H에 추가시킨다.

 

2. H으로부터 정점 A를 꺼낸다. 해당 정점은 경계에서 가장 가까이 있는 정점이다.이 정점을 MST에 추가하고 이 정점을 포함하도록 경계를 새로 설정한다.

 

3. A와 인접한 모든 정점 B에 대해  B거리 값이( A, B) 보다 가중치가 크면 B의 거리 값을 간선(A,B)의 가중치로 설정한다.

 

 

 

이를 끝날 떄까지 반복