최소 신장 트리

1926년, 오타카르 보루프카(Otakar Borůvka)는 남부 모라비아의 전력망을 최대한 싸게 설계해 달라는 요청을 받았습니다. 선의 총길이를 가장 적게 써서 모든 곳을 연결하는 방법을 묻는 그의 질문이 바로 최소 신장 트리 문제이며, 이 문제에는 컴퓨터 과학 전체에서 손꼽히게 간단하고 우아한 해법들이 있습니다.

간선에 길이가 있는 그래프. 자라는 트리의 짧은 간선이 강조되어 있고, 사이클을 만들어 건너뛴 간선은 빨간 점선으로 표시되며, 그 아래에 아직 시도할 간선 목록이 있습니다
간선에 길이가 있는 그래프. 자라는 트리의 짧은 간선이 강조되어 있고, 사이클을 만들어 건너뛴 간선은 빨간 점선으로 표시되며, 그 아래에 아직 시도할 간선 목록이 있습니다

문제

간선에 길이, 또는 비용이 있는 연결 그래프를 생각해 봅시다. 신장 트리는 모든 노드를 연결하면서 사이클이 없는 간선의 집합입니다. 노드가 n개면 간선은 항상 정확히 n − 1개입니다. 간선 하나가 노드 하나를 더 연결하기 때문입니다. 모든 신장 트리 가운데 최소 신장 트리는 총길이가 가장 작습니다. 그래프에는 엄청나게 많은 신장 트리가 있을 수 있지만, 전부 시도해 볼 필요는 없습니다.

그리디가 통하는 이유

노드를 어떤 식으로든 두 그룹으로 나눕니다. 두 그룹 사이를 가로지르는 가장 짧은 간선은 항상 어떤 최소 신장 트리에 속합니다. 어떤 트리가 대신 더 긴 가로지르는 간선을 쓴다면, 그것을 더 짧은 간선으로 바꿔 같은 노드를 더 싸게 연결할 수 있기 때문입니다. 이것이 컷 속성입니다. 그 반대편이 사이클 속성으로, 어떤 사이클에서든 가장 긴 간선은 결코 필요하지 않습니다. 아래 두 알고리즘은 이 규칙들을 계속 적용할 뿐입니다.

예제

길이 1인 간선 A–B, 2인 B–C, 3인 A–C, 4인 C–D, 5인 B–D가 있다고 합시다. 크러스컬 알고리즘은 A–B를 고르고, 다음으로 B–C를 고른 뒤, A–C는 건너뜁니다. A와 C가 이미 연결되어 있어 사이클을 만들기 때문입니다. 그다음 C–D를 고릅니다. 노드 4개에 간선이 3개이므로 트리가 완성되고, 총길이는 7이며, B–D는 아예 보지도 않습니다. A에서 시작하는 프림 알고리즘은 먼저 A–B로 B를 더합니다. C로 가는 길로는 B의 간선 B–C (2)가 A–C (3)보다 나으므로 C는 B–C로 합류합니다. C의 간선 C–D (4)가 B–D (5)보다 나으므로 D는 C–D로 합류합니다. 같은 트리, 같은 7입니다.

크러스컬, 프림, 보루프카

1956년 조지프 크러스컬(Joseph Kruskal)이 발표한 크러스컬 알고리즘은 간선을 정렬하고 유니온-파인드 구조로 한 조각 안의 간선을 건너뛰므로, 작업량이 E log E에 비례해 늘어납니다. 프림 알고리즘은 1930년 보이테흐 야르니크(Vojtěch Jarník)가 처음 설명했고, 1957년 로버트 프림(Robert Prim)과 1959년 에츠허르 다익스트라(Edsger Dijkstra)가 다시 발견했습니다. 이진 힙을 쓰면 작업량이 E log V로, 단순한 배열을 쓰면 V²로 늘어나며, 후자는 밀집 그래프에 좋습니다. 보루프카의 1926년 알고리즘은 모든 조각이 바깥으로 나가는 가장 짧은 간선을 동시에 잡게 하므로 병렬 컴퓨터에 알맞습니다.

1981년의 오타카르 보루프카. 1926년 남모라비아의 전력망을 가능한 한 싸게 계획해 달라는 요청을 받고, 최초의 최소 신장 트리 알고리즘을 내놓았다.
1981년의 오타카르 보루프카. 1926년 남모라비아의 전력망을 가능한 한 싸게 계획해 달라는 요청을 받고, 최초의 최소 신장 트리 알고리즘을 내놓았다.

활용

최소 신장 트리는 케이블, 파이프, 도로의 저렴한 네트워크를 설계하는 데 쓰입니다. 데이터를 클러스터로 묶기도 합니다. 트리에서 가장 긴 간선들을 없애면 남은 조각들이 클러스터입니다. 거리가 삼각 부등식을 따를 때는 외판원 문제에서 최선의 경로보다 최대 두 배 긴 경로를 빠르게 얻을 수 있습니다. 또 간선 길이가 무작위인 격자에서 크러스컬이나 프림 알고리즘을 실행하는 것은 미로를 만드는 고전적인 방법입니다.

직접 해 보기

앱을 열고 크러스컬이나 프림을 고른 다음 단계를 누르세요. 크러스컬에서는 아직 시도할 간선이 그래프 아래에 짧은 것부터 긴 것 순서로 나열되고, 사이클을 만드는 간선은 빨간 점선으로 그려집니다. 프림에서는 합류를 기다리는 노드가 가장 좋은 간선의 길이와 함께 나열되며, 그 간선은 점선으로 그려집니다. 같은 그래프에서 둘 다 실행해 비교해 보세요. 순서는 달라도 총길이는 항상 같습니다.

자주 묻는 질문

신장 트리에는 간선이 몇 개 있나요?

정확히 노드 수보다 하나 적습니다. 간선이 그보다 적으면 모든 노드를 연결할 수 없고, 하나라도 더 있으면 반드시 사이클이 생깁니다.

크러스컬과 프림 중 어느 쪽이 더 빠른가요?

간선을 정렬하는 크러스컬 알고리즘은 보통 더 간단하고, 간선이 적은 희소 그래프에서 빠릅니다. 힙을 쓰는 프림 알고리즘은 밀집 그래프에서 잘 동작하며, 단순한 배열을 쓰면 간선이 몇 개든 약 V² 단계가 필요합니다.

유니온-파인드란 무엇인가요?

어떤 노드들이 같은 조각에 있는지 추적하는 자료 구조입니다. ‘이 둘이 연결되어 있나?’에 답하고 두 조각을 거의 즉시 합치는데, 이것이 바로 크러스컬 알고리즘이 간선마다 필요로 하는 일입니다.

최소 신장 트리는 방향 그래프에도 쓸 수 있나요?

그대로는 안 됩니다. 한 방향 간선이 있는 그래프에서는 대응하는 문제가 최소 신장 유향 트리(아보레선스)이며, Chu–Liu/Edmonds 알고리즘으로 풉니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

최소 신장 트리 만들기