MST (Minimum Spanning Tree)

MST란 그래프의 모든 vertex를 최소 edge의 weight로 연결한 그래프이다.

최소 비용으로 모든 도시의 도로를 연결하거나, 통신망을 연결하는 데 응용할 수 있다.

 

Kruskal's Algorithm 

MST를 찾아내는 알고리즘으로, 가장 작은 weight를 갖는 edge를 추가하면서, 모든 vertex가 연결될 때까지 반복한다. 이때 cycle이 발생하지 않도록 주의한다. 

 

정리하자면, Kruskal algorithm은

1. weight의 오름차순으로 edge를 더해가는데

2. edge의 개수가 vertex-1개가 될 때까지만 반복한다.

3. Cycle이 생기지 않도록 유의하면서 과정을 진행한다.

 

그렇다면 cycle은 어떻게 찾을까?

cycle detection 배열을 이용한다. 연결되었다면 알파벳 숫자가 빠른 것을 기준으로 수정해준다. edge를 추가해주려고 하는데 값이 같다면 추가해주지 않는다. 아래의 그래프로 차근차근 살펴보자.

주인공 그래프

첫 번째로, 엣지들을 오름차순으로 정렬하여 정리해준다.

weight가 가장 작은 edge부터 시작한다. cycle detection 배열에서 D와 E의 값이 달랐으므로, 연결해줄 수 있다. 둘을 연결했다는 의미로 D와 E의 값을 같게 설정한다.(기준은 더 작은 알파벳을 기준으로 한다.)

다음으로 D와 G를 잇는 edge 보면, 이 경우도 서로 다른 값을 갖고 있었으므로 연결해주고, 둘의 값을 같게 설정해준다. 

 

이제 E와 G를 연결해주려 하는데, 앞에서 E와 G의 값을 둘 다 D로 바꿨기 때문에 둘이 같은 값을 갖고 있다. 따라서 둘을 잇게 되면 DEG 사이에 cycle이 생기게 된다. 그러므로 둘을 잇지 않고 넘어간다.

다음으로 C와 D를 살펴보면, 둘의 값이 다르기 때문에 이어줄 수 있고, 더 작은 값인 C로 지금까지 D 였던 값까지 전부 바꿔준다.

G의 값은 원래 C였고, H는 H의 값을 갖고 있었기 때문에 둘이 이어 줄 수 있다. 따라서 연결했다는 의미로 둘 다 C로 바꿔준다.

 

C와 F의 경우도 마찬가지로, F는 원래 F의 값을 갖고 있었으므로 C와 이어줄 수 있다.

B와 C를 살펴보면, B는 B, C는 C의 값을 갖고 있었으므로 이어줄 수 있고, 이전까지 C의 값을 가졌던 vertex들 까지 전부 B로 바꿔준다.

B, E와 B, F 그리고 B, H는 모두 B의 값을 갖는다. 따라서 이어 줄 수 없으므로 넘어간다.

A와 H는 다른 값을 가지므로 이어주고, 지금까지 B의 값을 갖던 vertex들도 A로 바꿔준다. 이제 edge의 개수가 vertex-1인 7개가 되었으므로 종료한다.

 

이를 구현한 코드는 다음 글에.. 

https://qqs-diary.tistory.com/107

[C++] MST 구현