최소 신장 트리(Minimum Spanning Tree, MST)

1. 개요

• 가중치 그래프에서 모든 정점을 포함하면서, 간선들의 가중치 합이 최소가 되는 트리 형태의 서브그래프를 의미
• 사이클 미존재: 트리 구조이므로 정점이 V개일 때 간선의 수는 반드시 V - 1개가 되며 순환하는 경로 존재하지 않음
• 연결성: 그래프의 모든 정점이 어떻게든 서로 연결되어 있어야 함
• 최소 비용: 가능한 다양한 신장 트리(Spanning Tree) 중에서 간선 가중치의 총합이 가장 작음

 

2. 대표적인 알고리즘

• MST를 구하는 알고리즘은 크게 두 가지가 있으며, 둘 다 그리디(Greedy, 탐욕) 알고리즘을 기반으로 작동
• 크루스칼 알고리즘 (Kruskal's Algorithm)
  • 간선(Edge)을 중심으로 MST를 찾아나가는 방식.
  • 모든 간선을 가중치 기준으로 오름차순 정렬
  • 가중치가 가장 낮은 간선부터 하나씩 선택
  • 이때, 선택한 간선이 사이클을 형성하지 않는지 확인 (이를 위해 보통 Union-Find(서로소 집합) 자료구조를 사용)
  • 사이클이 생기지 않는다면 트리에 추가하고, 생기면 건너뚬
  • 간선의 개수가 V - 1개가 될 때까지 반복
  • 적합한 경우: 간선의 개수가 적은 희소 그래프(Sparse Graph)에서 유리

• 프림 알고리즘 (Prim's Algorithm)
  • 정점(Vertex)을 중심으로 MST를 찾아나가는 방식
  • 임의의 시작 정점을 선택하여 트리(방문 완료 집합)에 넣음
  • 현재 트리에 포함된 정점들과 연결된 간선 중, 트리에 포함되지 않은 정점으로 향하는 가장 가중치가 작은 간선을 선택
  • 해당 간선과 연결된 정점을 트리에 추가 후 모든 정점이 트리에 포함될 때까지 반복
  • 적합한 경우: 주로 우선순위 큐(Priority Queue)를 사용해 구현하며, 간선이 많은 밀집 그래프(Dense Graph)에서 유리

 

3. 어디에 사용되나요?

• 현실 세계에서 비용을 최소화하며 네트워크를 구축할 때 필수적으로 사용
• 통신망/도로망 설계: 여러 도시를 모두 연결하면서 도로 건설 비용이나 케이블 매설 비용을 최소화할 때
• 전력망 구축: 발전소에서 여러 지역으로 전력을 공급하는 최소한의 전선로 설계
• 클러스터링: 데이터 마이닝에서 유사한 데이터들을 그룹화하는 분석 과정

 

4. 예제 코드 (크루스칼 알고리즘)

# 특정 원소가 속한 집합을 찾는 함수 (Find 연산)
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])  # 경로 압축(Path Compression)
    return parent[x]

# 두 집합을 합치는 함수 (Union 연산)
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 정점의 개수(V)와 간선의 개수(E) 입력받기
v, e = 7, 9  # 예시: 정점 7개, 간선 9개
parent = [0] * (v + 1)  # 부모 테이블 초기화

# 모든 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선 정보를 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 간선 정보 입력 (시작 정점, 도착 정점, 비용)
# 실제로는 입력(input)을 받겠지만, 예시 데이터를 직접 넣었습니다.
example_edges = [
    (1, 2, 29), (1, 5, 75), (2, 3, 35), 
    (2, 6, 34), (3, 4, 7),  (4, 6, 23), 
    (4, 7, 13), (5, 6, 53), (6, 7, 25)
]

for a, b, cost in example_edges:
    edges.append((cost, a, b))  # 비용을 첫 번째 요소로 두어 정렬하기 쉽게 함

# 1. 간선을 비용순으로 오름차순 정렬
edges.sort()

print("--- MST 간선 선택 과정 ---")
# 2. 간선을 하나씩 확인하며 사이클이 발생하지 않는 경우에만 집합에 포함
for edge in edges:
    cost, a, b = edge
    # 두 정점의 루트 노드가 다르다면(사이클이 발생하지 않는다면)
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
        print(f"간선 연결: {a} - {b} (비용: {cost})")

print(f"\n최소 신장 트리의 총 비용: {result}")

 

--- MST 간선 선택 과정 ---
간선 연결: 3 - 4 (비용: 7)
간선 연결: 4 - 7 (비용: 13)
간선 연결: 4 - 6 (비용: 23)
간선 연결: 1 - 2 (비용: 29)
간선 연결: 2 - 6 (비용: 34)
간선 연결: 5 - 6 (비용: 53)

최소 신장 트리의 총 비용: 159


     29)          (35)
  ① -------- ② -------- ③
  |          |          |
  | (75)     | (34)     | (7)
  |          |          |
  ⑤ -------- ⑥ -------- ④
      (53)     \    (23) /
                \       /
             (25)\     / (13)
                  \   /
                    ⑦
                    
              ↓

      (29)
  ① ======== ②          ③
             ||         ||
             || (34)    || (7)
             ||         ||
  ⑤ ======== ⑥ ======== ④
      (53)   (23)      //
                      // (13)
                     //
                    ⑦