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

최소 스패닝 트리(Minimum Spanning Tree)

최소 스패닝 트리를 이야기하기 전에 우선 스패닝 트리란 무엇인지 알아보도록 할게요.

우선 어떤 무향 그래프가 있다고 해보도록 가정하겠습니다. 스패닝 트리는 말 그대로 그래프에서 트리의 상태를 유지해야합니다. 그러니 사이클이 있으면 안되지요. 반드시 부모와 자식 관계로 이루어져 있지 않아도 됩니다.

다음의 그림은 올바른 스패닝 트리와 그렇지 않은 스패닝 트리를 보여줍니다.

                 

왼쪽의 그림의 선택된 간선(굵은 선)은 사이클을 이루지 않지요.

반면 오른쪽 그림은 빨간선 때문에 사이클을 이루게 됩니다.

어때요? 간단하지요?

스패닝 트리는 그래프에서 여러개가 존재할 수도 있지만 우리가 눈여겨 볼 것은 스패닝 트리의 간선들이 가장 최소의 값을 갖는 것으로 바로 최소 스패닝 트리(Minimum Spanning Tree)라고 합니다.

대표적인 알고리즘에는 대표적으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있는데요. 이 두가지 알고리즘을 함께 보도록 하지요.

크루스칼 알고리즘 개념(Kruskal's Algorithm Concept)

우리는 아래의 그래프의 최소 스패닝 트리를 구할 겁니다. 이제 이 그래프를 가지고 크루스칼 알고리즘이 어떻게 동작하는지를 확인해 보도록 할게요.

원리는 이렇습니다.

1. 스패닝 트리에 포함되지 않는 가장 작은 값의 간선을 찾는다.

2. 그 간선이 이미 만들어진 트리에 포함되어 있는지 확인한다.

3. 그 간선이 추가된다면 이미 만들어진 트리에서 사이클을 이루는 지 확인한다. 

4-1. 그 간선이 트리에 포함되어 있고 사이클이 있다면 다른 간선을 확인한다.

4-2. 그 간선이 위의 두 조건에 성립되지 않으면 스패닝 트리에 포함시킨다.

우리는 위의 조건들을 가지고 최소 스패닝 트리를 찾는 겁니다.

        

우선 가장작은 간선의 값인 1, 즉 3-5의 간선을 봅니다. 현재 선택된 간선은 없으므로 3-5의 간선을 추가합니다. 그 다음 작은 간선을 보면 2인데, 이 간선은 현재 추가된 간선이 없으므로 2-4의 간선도 추가합니다.

        

이제 추가된 간선은 3-5, 2-4의 간선(파란색)입니다. 그 후 가장 작은 간선을 보면 1-2인데 이 간선은 추가된적이 없으므로 추가합니다. 그 후 역시 3인 간선이 있는데요. 이 간선을 추가하게 되면 사이클을 이루게 됩니다. 그러니까 다음 간선으로 넘어가게 되지요.

       

그 다음 작은 간선은 2-3입니다. 값은 4인데, 이 간선은 현재 추가한적이 없지요?(파란색 간선이 추가한 간선입니다.) 그러니 이 간선을 포함시키도록 합니다.

그 후 4-5 간선을 보게 되면 현재 선택되지는 않았지만 추가하게 되면 사이클을 이루게 됩니다. 그러니 넘어가죠.

        

이후 간선 0-1의 간선을 추가합니다. 다음으로 큰 수가 5이니까요.

이제 모든 정점이 트리에 포함되었으니 종료합니다.

따라서 최종 최소 스패닝 트리는 아래의 그림과 같습니다.

어떻습니까??

가장 최소의 값으로 스패닝 트리를 완성했다는 것을 알 수 있습니다.

프림 알고리즘 개념(Prim's Alogorithm Concept)

이번에는 최소 스패닝 트리의 다른 알고리즘, 프림 알고리즘을 보도록 하지요. 프림 알고리즘은 트리에 연결된 간선 중 가장 작은 것을 차례차례 선택해나갑니다. 크루스칼 알고리즘과 같은 점은 역시 사이클을 이루는 간선을 선택하지 않는다는 것이죠.

        

어느 정점에서 시작하든 상관없습니다. 우리는 3번의 정점부터 계속 트리에 정점을 추가할 것입니다. 3과 가장 가까운 정점은 5가 되겠네요. 3과 5를 트리에 추가합니다. 3, 5 정점 중 가장 작은 간선은 2-3과 4-5네요. 구현에 따라 다를수 있으므로 둘 중에 아무거나 선택하면 됩니다. 2-3의 간선을 선택하지요. 따라서 트리에는 2가 추가가 됩니다.

        

이제 2, 3, 5에 붙어 있는 간선 중 가장 작은 간선 2-4를 선택합시다. 

그렇다면 현재 트리에는 2, 3, 4, 5가 됩니다. 이제 이 정점에서 가장 작은 간선을 선택해보도록 하지요. 후보는 1-2 간선과 1-4 간선이 됩니다. 아무거나 선택합시다. 

1-2의 간선을 선택하지요.

        

그 후 트리에 속해있는 정점과 붙어있는 가장 작은 간선은 1-4의 간선이 되는 군요. 하지만 선택할 수 없습니다. 사이클을 이루니까요. 그러니 버립시다.

다음 가장 작은 간선은 4-5의 간선입니다. 이것 역시 사이클을 이루게 되죠? 그러니 그냥 버리도록 합시다.

다음으로 가장 작은 간선은 0-1의 간선입니다. 이 간선을 포함해도 사이클을 이루지 않으니 선택하도록 하지요.

그렇다면 이제 모든 정점이 트리에 포함되어 있습니다. 여기서 종료합니다.

프림 알고리즘과 크루스칼 알고리즘이 동작하는 방식은 다르나 최소 스패닝 트리를 구할 수 있다는 것을 알 수 있습니다. 두 알고리즘 다 15의 값을 갖는 최소 스패닝 트리를 만들어 낼 수 있었습니다. 최소 스패닝 트리는 여러개 존재할 수는 있지만 그 값은 같다는 것을 잊지마세요.