최소 신장 트리(Prim's, MST: Minimum spanning Tree)

✅ 1. 최소 신장 트리(Minimum Spanning Tree)란?

• 정의: 주어진 무방향 연결 그래프에서 모든 정점들을 연결하면서 가중치의 합이 최소가 되는 트리 구조의 부분 그래프.
• 조건
  • 모든 정점이 연결되어 있어야 함.
  • 사이클(순환)은 없어야 함.
  • 여러 개의 MST가 존재할 수도 있음.
• 📌 기본 개념
  • Undirected Graph (무방향 그래프)
  • 모든 노드가 연결되도록 (Connected)
  • 전체 간선의 가중치 합이 최소가 되도록 (Minimum Total Cost)
  • 노드가 n개라면 MST는 항상 n - 1개의 간선만 포함
    → 그래서 사이클이 생기지 않음
  • 어느 노드에서 시작해도 결과는 동일한 MST 완성 가능

✅ 2. Prim's Algorithm이란? (프림 알고리즘)

• 핵심 아이디어: 하나의 정점에서 시작해서, 가장 작은 가중치의 간선을 하나씩 선택하며 MST를 만들어가는 방식.

💡 동작 방식:

1. 임의의 정점에서 시작 (예: 0번 정점)
2. 현재 선택된 정점들과 연결된 간선 중 가장 작은 가중치의 간선을 선택
3. 그 간선으로 연결된 새로운 정점을 트리에 추가
4. 위 과정을 모든 정점이 포함될 때까지 반복

🔧 사용 자료구조

1. visited: 방문한 노드들을 저장 (보통 set/hashset)
2. minHeap (우선순위 큐):
   • 형식: [weight, n1, n2]
     → weight: 간선 가중치
     → n1: 현재 방문 중인 노드
     → n2: 연결할 다음 노드
   • 항상 가중치가 가장 작은 간선부터 탐색

🔄 전체 알고리즘 흐름

1. 아무 노드에서 시작 (예: 노드 0)
   → visited에 추가하고, 연결된 모든 간선을 minHeap에 넣음
2. minHeap에서 가장 작은 간선을 꺼냄
3. to_node가 아직 방문하지 않았다면:
   • 간선 선택 (MST에 포함)
   • to_node를 방문 처리 (visited에 추가)
   • to_node에서 뻗는 간선들을 minHeap에 추가
4. 이 과정을 n-1개의 간선이 선택될 때까지 반복

import heapq  # 최소 힙(min heap)을 구현하기 위한 heapq 모듈 임포트

# 주어진 무방향 연결 그래프의 간선 리스트와 노드 개수 n을 받아,
# 최소 신장 트리를 구성하는 간선들의 리스트를 반환하는 함수
def minimumSpanningTree(edges, n):
    adj = {}  # 인접 리스트로 그래프 표현
    for i in range(1, n + 1):
        adj[i] = []  # 각 노드를 키로 하여 빈 리스트 초기화

    # 간선 정보를 인접 리스트 형태로 구성 (무방향이므로 양쪽에 모두 추가)
    for n1, n2, weight in edges:
        adj[n1].append([n2, weight])
        adj[n2].append([n1, weight])

    # 최소 힙 초기화
    # 시작 노드는 1번 노드로 설정하고, 해당 노드에 연결된 모든 간선을 힙에 추가
    minHeap = []
    for neighbor, weight in adj[1]:
        heapq.heappush(minHeap, [weight, 1, neighbor])  # 형식: [가중치, 현재 노드, 다음 노드]

    mst = []          # 최소 신장 트리에 포함될 간선들을 저장할 리스트
    visit = set()     # 방문한 노드들을 저장할 집합
    visit.add(1)      # 시작 노드 1번을 방문 처리

    # 모든 노드가 방문될 때까지 반복
    while len(visit) < n:
        weight, n1, n2 = heapq.heappop(minHeap)  # 가장 가중치가 낮은 간선 꺼냄
        if n2 in visit:
            continue  # 이미 방문한 노드면 무시하고 다음 반복

        mst.append([n1, n2])  # 최소 신장 트리에 현재 간선 추가
        visit.add(n2)         # 새로 연결된 노드를 방문 처리

        # 새로 방문한 노드에서 연결되는 간선들을 힙에 추가
        for neighbor, weight in adj[n2]:
            if neighbor not in visit:
                heapq.heappush(minHeap, [weight, n2, neighbor])  # 형식: [가중치, 현재 노드, 다음 노드]

    return mst  # 최소 신장 트리에 포함된 간선 리스트 반환

✅ 추가 설명

• MST 구성만 하고 전체 비용은 리턴하지 않는 구조입니다.
  → 필요하다면 mst_cost += weight 로 가중치를 누적해 따로 반환 가능해요.
• 시작 노드가 항상 1번으로 고정되어 있지만, 그래프가 연결되어 있으면 어디서 시작하든 결과는 같아요.

---

✅ 3. 시간복잡도

• 인접 행렬 + 우선순위 큐 없음: O(V^2)
• 인접 리스트 + 우선순위 큐 사용 (Heap 사용): O(E log V)

---

✅ 예시

[0] -------- (1) -------- [1]
 |                          |
(4)                       (3)
 |                          |
[2] -------- (2) -------- [3]

시작: 노드 0
- Heap: [(1, 0, 1), (4, 0, 2)] → 1 선택 → 방문: 0, 1
- Heap: [(3, 1, 3), (4, 0, 2)] → 2 선택 → 방문: 0, 1, 3
- Heap: [(2, 3, 2), (4, 0, 2)] → 3 선택 → 방문: 0, 1, 2, 3
- 종료 (MST 완성)

[정점]: A, B, C, D
[간선] (가중치):
A - B (1)
A - C (3)
B - C (1)
B - D (4)
C - D (2)

▶ Prim's 시작: A
1. A-B (1) 선택 → 포함: A, B
2. B-C (1) 선택 → 포함: A, B, C
3. C-D (2) 선택 → 포함: A, B, C, D

==> 총 가중치: 1 + 1 + 2 = 4

 

✅ 핵심 요약 포인트

• MST는 노드가 n개일 때 n-1개의 간선만 필요
• 따라서 불필요한 간선을 없애는 문제로 바꿔서 생각할 수 있음
• Prim은 방문 노드를 확장하면서 가장 가벼운 간선을 선택해 나가는 방식
• 시작 노드는 아무거나 가능
• Cycle은 절대 생기지 않음 (visited로 방지)