MST 최소신장트리 (python,파이썬)

🌲 최소 신장 트리(MST-Minimum Spanning Tree)란?

• 정의: 무방향 가중치 그래프에서 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 트리를 의미합니다.
• 조건
  • 모든 정점이 연결되어 있어야 함 (연결 그래프)
  • 사이클이 없어야 함 (트리 구조)
  • 정점의 갯수가 V인 그래프의 최소 신장 트리는 V-1개의 간선을 가진다.

📌 크루스칼 알고리즘 (Kruskal's Algorithm)

🔧 핵심 아이디어

"간선을 하나씩 가중치가 작은 순으로 선택하되, 사이클을 만들지 않도록 유니온-파인드(Disjoint Set)를 이용해서 연결한다."

🪜 동작 순서

1. 간선을 가중치 기준으로 오름차순 정렬한다.
2. 가장 가중치가 낮은 간선부터 하나씩 선택한다.
3. 선택한 두 정점이 **서로 다른 집합(사이클 X)**이면 연결한다.
4. 모든 정점이 연결될 때까지 반복한다.

🧠 시간 복잡도

• 정렬: O(E log E)
• 유니온-파인드 연산: 거의 O(1) (경로 압축 시)
• 전체: O(E log E)

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 경로 압축
    return parent[x]

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a != b:
        parent[b] = a  # 누가 부모가 되느냐는 상관없음 (일관성만 있으면 OK)

def kruskal(V, edges):
    parent = [i for i in range(V + 1)]
    edges.sort(key=lambda x: x[2])  # 간선 정렬

    mst_weight = 0
    for u, v, w in edges:
        if find(parent, u) != find(parent, v):
            union(parent, u, v)
            mst_weight += w

    return mst_weight

📌 프림 알고리즘 (Prim's Algorithm)

🔧 핵심 아이디어

"한 정점에서 시작해서 인접한 정점 중 가장 가중치가 작은 간선을 선택해 점진적으로 MST를 확장한다."

🪜 동작 순서

1. 임의의 정점에서 시작한다.
2. 그 정점과 연결된 간선들을 최소 힙에 넣는다.
3. 가장 가중치가 작은 간선을 꺼내어 연결하고, 새로운 정점의 간선들도 힙에 추가한다.
4. 모든 정점이 연결될 때까지 반복한다.

🧠 시간 복잡도

• 우선순위 큐(힙) 사용 시: O(E log V)

import heapq

def prim(V, graph):
    visited = [False] * (V + 1)
    heap = [(0, 1)]  # (가중치, 정점)
    mst_weight = 0

    while heap:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        mst_weight += w

        for v, weight in graph[u]:
            if not visited[v]:
                heapq.heappush(heap, (weight, v))

    return mst_weight

 

graph는 인접 리스트 형식이며, graph[u] = [(v1, w1), (v2, w2), ...] 식으로 구성됩니다.

🌀 힙의 동작 방식

• heapq는 기본적으로 최소 힙(min-heap) 구조입니다.
• heapq.heappop()은 가중치(weight)가 가장 작은 튜플을 꺼냅니다.
• 간선 정보가 (가중치, 도착노드) 형식이기 때문에, 가중치 기준으로 정렬됩니다.

                                        크루스칼 알고리즘                                                 프림 알고리즘

접근 방식	간선을 기준으로 정렬 후 선택	정점을 기준으로 확장
구현 방식	간선 정렬 + 유니온 파인드	우선순위 큐 + 방문 체크
사이클 확인	유니온-파인드 사용 필요	방문 여부로 자동 방지
성능	간선이 적은 경우 유리	정점이 적은 경우 유리
주요 자료구조	간선 리스트, Disjoint Set	힙(priority queue), visited set

🧩 어떤 걸 선택해야 할까?

• 그래프의 간선 수가 적으면 → 크루스칼
• 정점 수가 적고 연결이 복잡하면 → 프림