최소 신장 트리로 연결 비용을 줄이는 방법

연결은 유지하고 불필요한 비용은 덜어내는 트리

최소 신장 트리(Minimum Spanning Tree, MST)는 가중치가 있는 그래프에서 모든 정점을 연결하면서도 사이클을 만들지 않는 부분 그래프다. 이 조건을 만족하는 트리 가운데 간선 가중치의 합이 가장 작은 구조를 뜻한다.

네트워크 설계에서는 모든 지점을 연결해야 하지만, 중복 경로까지 무조건 추가하면 비용이 커진다. MST는 연결성을 보장하는 데 필요한 간선만 남기고 전체 비용을 최소화하는 기준이 된다.

MST에는 다음 성질이 있다.

모든 정점을 포함하므로 연결성이 보장된다.
사이클이 존재하지 않아 트리 조건을 만족한다.
정점이 n개라면 간선은 정확히 n-1개다.
선택된 간선 가중치의 합이 최소다.
모든 정점 쌍 사이에는 유일한 경로가 존재한다.

그래프로 표현하는 MST 조건

가중 무방향 그래프 G = (V, E)에서 MST는 부분 그래프 T = (V, E')로 나타낼 수 있다. 여기서 V는 정점(Vertex) 집합, E는 간선(Edge) 집합이며 E'⊆E다.

T는 모든 정점 쌍 사이에 경로가 있어야 하고, |E'| = |V|-1을 만족해야 한다. 이때 ∑(u,v)∈E' w(u,v), 즉 선택한 간선 가중치의 합이 최소가 되도록 E'를 선택한다.

⤢✕

이 그래프에서 MST를 구성하면 모든 정점은 연결되지만 사이클은 생기지 않으며, 선택한 간선들의 가중치 합은 가능한 값 중 최소가 된다.

비용이 연결 설계의 기준이 되는 곳

MST는 연결 대상이 많고 각 연결에 비용이 붙는 문제에서 활용할 수 있다. 통신 네트워크에서는 여러 도시를 광케이블로 잇되, 모든 도시가 연결되는 최소 비용의 구성을 찾는 데 사용한다.

전력망을 새 지역에 구축할 때는 변전소와 건물 사이의 연결 경로를 설계하는 기준이 될 수 있다. 신도시의 주요 시설을 잇는 도로망, 원유 생산지와 정제소를 연결하는 파이프라인, PCB에서 모든 구성요소를 연결하는 배선 설계도 같은 유형의 문제다.

간선을 정렬해 선택하는 Kruskal 방식

Kruskal 알고리즘은 간선을 가중치 오름차순으로 정렬한 뒤, 사이클을 만들지 않는 간선을 차례로 선택한다. 가장 비용이 낮은 연결부터 검토하되 기존 선택과 순환 구조를 만들면 제외한다.

모든 간선을 가중치 오름차순으로 정렬한다.
가장 작은 가중치의 간선부터 검토한다.
사이클을 만들지 않으면 MST에 추가한다.
n-1개의 간선이 선택될 때까지 반복한다.

시간 복잡도는 O(E log E)이며, E는 간선 수다. 구현에서는 Union-Find 자료구조로 두 정점이 이미 같은 집합에 속하는지 확인해 사이클 형성 여부를 판별한다.

⤢✕

시작 정점에서 확장하는 Prim 방식

Prim 알고리즘은 하나의 시작 정점에서 출발해 현재 트리와 연결된 간선 가운데 가중치가 가장 작은 것을 계속 고르는 방식이다. 새 간선은 반드시 기존 트리와 맞닿아 있으므로 트리가 점진적으로 확장된다.

임의의 시작 정점을 선택한다.
현재 트리에 연결된 간선 중 최소 가중치 간선을 선택한다.
해당 간선과 이어진 새 정점을 트리에 추가한다.
모든 정점이 트리에 포함될 때까지 반복한다.

인접 행렬을 쓰면 시간 복잡도는 O(V²)이고, 우선순위 큐를 쓰면 O(E log V)다. 최소 힙(Min Heap) 기반 우선순위 큐는 현재 트리에서 다음으로 연결할 후보를 관리하는 데 쓰인다.

⤢✕

여러 트리를 함께 합치는 Sollin 알고리즘

Sollin(Borůvka) 알고리즘은 각 정점을 독립된 트리로 시작한 다음, 각 트리가 가진 외부 연결 간선 중 가중치가 가장 작은 것을 선택해 트리들을 병합한다. 하나의 트리만 남을 때까지 이 과정을 반복한다.

시간 복잡도는 O(E log V)다. 여러 트리가 동시에 확장되는 구조이므로 병렬 처리에 적합하며, 분산 시스템에서 활용할 수 있다.

⤢✕

그래프의 형태가 알고리즘 선택을 가른다

간선 수가 적은 희소 그래프(Sparse Graph)에서는 Kruskal 알고리즘이 효율적이다. 광역 통신망이나 도시 간 도로망 설계가 이에 해당한다.

간선 수가 많은 밀집 그래프(Dense Graph)에서는 Prim 알고리즘이 적합하다. 사회연결망 분석이나 컴퓨터 네트워크 설계처럼 연결 후보가 많은 경우를 예로 들 수 있다.

분산 시스템에서 병렬 처리가 필요하다면 Sollin 알고리즘을 검토할 수 있다. 대규모 클라우드 인프라 설계가 해당 상황이다.

비용 외 조건이 추가되는 경우

실제 설계는 간선 비용만으로 끝나지 않는다. 통신 네트워크에는 대역폭 제약이 있을 수 있고, 도로망은 지형 조건을 고려해야 하며, 전력망에는 안정성 요구사항이 붙는다. 이런 다중 제약 MST(Multi-Constrained MST)는 단순 MST만으로 해결하기 어려워 추가 제약 처리 로직이 필요하다.

네트워크 구조가 계속 변하면 동적 MST(Dynamic MST)가 필요해진다. 간선이 추가되거나 삭제될 때 전체 MST를 다시 계산하지 않고 부분적으로 갱신하는 방식이며, 실시간 네트워크 라우팅에서 중요하다.

그래프가 매우 큰 경우에는 정확한 MST 계산 대신 근사 MST(Approximate MST)를 사용할 수 있다. 샘플링 기반 계산이나 분산 환경에서의 MST 계산이 여기에 속한다.

구현에서 먼저 정할 문제들

그래프 표현은 간선 리스트, 인접 행렬, 인접 리스트 중에서 선택해야 한다. Union-Find 역시 사이클 판별 성능에 영향을 주므로 구현 방식을 함께 검토해야 한다.

대규모 그래프에서는 메모리 사용량이 문제가 되며, 희소 행렬 표현 방식을 활용할 수 있다. 가중치 값의 범위와 정밀도, 동일 가중치 간선을 처리하는 방법도 미리 정해야 한다. 연결되지 않은 그래프와 음수 가중치 역시 예외 처리 대상이다.

성능을 더 끌어올리려면 명백히 MST에 포함되지 않을 간선을 사전 필터링하고, 대규모 그래프에는 병렬 알고리즘을 적용할 수 있다. 전체 MST를 한 번에 계산하지 않고 부분 계산 후 통합하는 점진적 방식도 가능하다. 자주 접근하는 부분그래프의 MST 결과는 캐싱 대상으로 고려할 수 있다.

MST는 네트워크 비용 절감, 통신 효율성 향상, 인프라 최적화 같은 문제를 다루는 기반 구조다. 그래프의 특성과 운영 제약을 함께 봐야 알고리즘 선택과 구현 방식이 실제 설계 목적에 맞는다.