알고리즘 - 최소 신장 트리(MST, Minimum Spanning Tree)

최소 신장 트리(MST, Minimum Spanning Tree)

---

그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리다.

MST를 사용하는 대표적인 알고리즘으로 크루스칼, 프림 알고리즘이 있다.

 

MST 특징

사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.

N개의 노드가 있으면 최소 신장 트리를 구헝하는 에지의 개수는 항상 N - 1개다.

 

아래의 예제는 크루스칼 알고리즘을 기준으로 한다.

MST 핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기

초기화

MST는 데이터를 노드가 아닌 에지를 중심으로 저장하기 때문에 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.

유니온 파인드를 사용하는 이유는 사이클이 발생하면 안되기 때문에 사이클 유무를 판단하기 위해 사용한다.

 

2. 그래프 데이터를 가중치 기준으로 오름차순 정렬을 한다.

오름차순 정렬

 

3. 가중치가 낮은 에지부터 연결을 시도한다.

에지 연결을 시도

먼저 해당 에지를 연결했을 때 사이클이 생기는지 유니온 파인드를 통해 확인하고 사이클이 발생하지 않을 경우 연결을 수행한다.

 

4. 3번 과정을 반복한다.

반복하기

전체 노드의 개수가 N개이면 연결한 에지의 개수가 N - 1이 될 때까지 3번 과정을 반복한다.

2번 노드와 5번 노드를 연결할 때 유니온 파인드 연산을 통해 해당 노드들의 유니온 파인드 리스트 값이 같아지는 것을 확인할 수 있다. 따라서 연결할 시 사이클이 생기는 것을 알 수 있고 해당 노드의 연결을 시도하지 않는다.

 

5. 총 에지 비용을 출력한다.

총 에지 비용 출력

완성된 그래프를 확인하여 연결된 에지의 가중치를 총 합하여 출력한다.

위의 예시를 보면 3 + 4 + 8 + 2 = 17이므로 총 가중치의 합은 17이라는 것을 알 수 있다.