최소신장트리(Minimum Spanning Tree) 를 구하는 법
최소신장트리 (Minimum Spanning Tree)란 무엇인가
최소신장트리의 특징은 크게 3가지가 있다.
- 그래프에서 모든 정점을 연결해야 한다.
- 연결된 트리가 사이클을 포함하고 있으면 안 된다.
- 그러한 트리들 중에서 에지의 가중치 합이 최소가 되는 트리여야 한다.
이러한 최소신장트리는 그래프에서 노드를 연결하는 에지의 부분 집합 중에서 최소한의 비용으로 모든 노드를 연결하는 트리를 찾는 문제에 나온다.
이때 사용하는 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 존재한다.
프림 알고리즘 (Prim's algorithm)
프림 알고리즘은 최소신장트리를 구하는 알고리즘 중 하나로 그래프에서 노드를 중점으로 탐색하여 최소신장트리를 구합니다.
프림 알고리즘의 순서는 아래와 같습니다.
- 시작 노드를 선택합니다.
- 선택한 노드에서 갈 수 있는 노드 중 엣지의 가중치가 가장 짧은 노드를 선택합니다.
- 2에서 선택할 때 선택받는 노드는 한 번도 선택받지 않은 노드여야 합니다.
- 모든 노드들이 선택받을 때까지 2,3번 과정을 반복합니다.
프림 알고리즘은 위와 같은 순서로 진행되며, 시간 복잡도는 노드의 개수가 V, 에지의 개수가 E라고 할 때, O(E log V)입니다.
아래는 프림 알고리즘의 실행 예시입니다.
프림 알고리즘의 특징
- 간선이 많은 경우 크루스칼 알고리즘보다 효율적으로 동작합니다.
- 구현이 비교적 쉽고 가독성이 좋습니다.
크루스칼 알고리즘 (Kruskal's algorithm)
크루스칼 알고리즘도 최소신장트리를 구하는 알고리즘 중 하나로 그래프에서 에지를 중심으로 탐색하여 최소신장트리를 구합니다.
크루스칼 알고리즘은 아래와 같이 동작합니다.
- 모든 에지들을 가중치의 오름차순으로 정렬합니다.
- 아직 선택받지 않은 엣지 중에서 가장 작은 에지를 선택합니다.
- 에지를 선택했을때 그래프에 사이클이 생기면 안 된다는 점을 유의해야 합니다. 만약 사이클이 생기는 경우 다른 에지를 선택해야 합니다.
- 모든 노드들이 연결될 때까지 2,3번 과정을 반복합니다.
크루스칼 알고리즘은 위와 같은 순서로 진행되며, 시간 복잡도는 노드의 개수가 V, 엣지의 개수가 E라고 할 때, O(E log E)입니다.
아래는 크루스칼 알고리즘의 실행 예시입니다.
크루스칼 알고리즘의 특징
- 간선이 적은 경우 프림 알고리즘보다 효율적으로 동작합니다.
- 에지를 정렬해야 하는 작업이 필요합니다.
- 엣지를 선택할 때, 사이클을 형성하지 않는지 확인하는 과정을 구현하기 복잡하다.
의문이 생겼던 지점
크루스칼이나 프림 알고리즘으로 최소 신장 트리를 구하다 보면 선택을 해야 하는 상황에서 가중치가 가장 작은 에지가 여러 개인 상황에는 어떻게 해야 하지??
위 질문에 대답은 생각보다 간단했다. 아무 상관없다였다. 선택할 수 있는 에지 중에서 가중치가 가장 작은 에지가 여려 개 존재하는 것이라면, 그냥 그중에서 아무거나 고르면 된다. 이유는 위 예시에서도 최소신장트리를 그리면 여러 개가 나오기 때문인데, 이는 최소신장트리는 하나만 존재하는 것이 아니라 가중치 값의 합이 최소이기만 하면 되는것이라 여러개 존재할 수 있기 때문이다.
그러면 무엇을 선택해야 하나??
이 질문에 대한 원론적인 대답은 아마 "그래프의 에지에 따라 에지의 크기가 크다면 프림 알고리즘, 아니면 크루스칼 알고리즘을 선택하면 된다." 일거 같다. 하지만 나는 웬만해서는 크루스칼 알고리즘은 하고 싶지 않다. 입력받은 에지의 목록을 정렬하고, 에지를 선택하는 과정에서 사이클을 이루는지 아닌지 확인하는 과정이 어려울 거 같아서 이다.
하지만 문제를 풀어보다 보니 그냥 최소신장트리를 구하기보다는 문제에서 원하는 최소신장트리의 조건이 있었다. 그래서 문제에서 노드를 중심으로 문제를 풀어야 할지, 에지를 중심으로 문제를 풀어야 할지를 선택하고 그에 따라 프림 알고리즘이나 크루스칼 알고리즘을 통해 문제를 풀어갈 것 같다.