최소 신장 트리

왜 배우는가: 최소 신장 트리는 도로·통신망·배관처럼 모든 지점을 최소 비용으로 잇는 설계 문제의 기본 모형이다. 그래프 이론과 알고리즘 과목에서 그리디 전략의 대표 예로 다뤄지므로 시험에서 반복해서 출제된다. 크루스칼과 프림 알고리즘의 절차 비교와 비용 인접 리스트 작성이 함께 묻는다.

출제 이력: 제117회 3교시 3번, 제96회 1교시 1번, 제87회 4교시 2번

1. 한 줄 정의와 핵심 키워드

최소 신장 트리(MST)는 연결된 가중치 그래프의 모든 정점을 사이클 없이 잇는 부분 그래프 중 간선 가중치의 합이 최소인 트리이다.

• 신장 트리(Spanning Tree): 모든 정점을 포함하고 사이클이 없는 연결 부분 그래프
• 가중치(Weight): 간선마다 붙는 비용(공사비, 거리, 지연 시간 등)
• 사이클(Cycle): 출발 정점으로 되돌아오는 간선 경로. 신장 트리에는 존재하지 않는다
• 그리디 알고리즘(Greedy Algorithm): 매 단계에서 그 순간 최선의 간선을 고르는 전략
• 컷 속성(Cut Property): 그래프를 두 집합으로 나눴을 때 가장 가벼운 교차 간선은 어떤 MST에든 포함된다는 성질
• 유니온-파인드(Union-Find): 크루스칼 알고리즘에서 사이클 여부를 빠르게 판정하는 집합 자료구조
• 희소 그래프 / 밀집 그래프: 간선 수가 적은 그래프 / 많은 그래프

2. 개념 풀이

쉬운 말로 하면, 도시 여러 곳을 도로로 모두 연결하되 공사비 합계가 가장 적게 드는 도로망을 고르는 문제다. 모든 도시를 잇고 순환 도로가 없어야 하므로 결과는 트리 모양이다.

정식 정의는 다음과 같다. 연결 가중치 무방향 그래프 G=(V, E)에서 신장 트리 T=(V, E')의 가중치 합 w(T)=Σw(e)가 최소인 T를 최소 신장 트리라 한다. 정점 수가 n개인 신장 트리의 간선 수는 n-1개다. 간선이 하나라도 많으면 사이클이 생기고, 하나라도 적으면 연결되지 않는다.

신장 트리는 MST의 상위 개념이다. 가중치가 없는 그래프에서도 신장 트리는 존재하지만, MST는 가중치 합을 기준으로 고른 신장 트리다. 사이클을 허용하지 않는 조건이 있기 때문에, 알고리즘은 간선을 추가할 때마다 사이클 여부를 검사해야 한다.

그리디 전략은 두 대표 알고리즘의 공통 원리다. 크루스칼은 간선 단위로, 프림은 정점 단위로 가장 가벼운 연결을 고른다. 두 방법 모두 이 선택이 최종 MST의 일부가 된다는 것을 컷 속성으로 보장한다. 최단 경로(다익스트라)는 시작점에서 각 정점까지의 거리를 구하는 문제이고, MST는 간선 가중치의 총합을 최소화하는 문제라는 점이 다르다.

3. 등장 배경과 필요성

여러 지점을 연결하는 인프라를 설계할 때는 모든 지점을 잇는 것이 1차 목표이고, 그 다음이 비용 최소화다. 지점 수가 많아지면 모든 연결 방식을 나열하는 것은 현실적이지 않다. 그래서 그래프 이론에서 효율적인 탐색 알고리즘이 필요해졌다.

대표 적용 분야는 도로·철도 건설, 통신망과 케이블 배선, 전력망 설계, 클러스터링, 이미지 처리 등이다. 소프트웨어 공학에서는 네트워크 구성과 분산 시스템의 통신 경로 설계에 쓰인다. 최소 비용 조건을 만족하면서 연결성을 보장하는 구조를 자동으로 찾는다는 점이 핵심 가치다.