[알고리즘] 최소 신장 트리(MST) - 크루스칼, 프림

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

"그래프의 모든 정점을 최소한의 간선으로 연결하되, 간선들의 가중치 합이 최소가 되는 트리"

 

 

구성 요소

 

1. 무방향 가중치 그래프: 간선이 방향성을 가지지 않고, 가중치가 있는 경우  

• 정점: 연결하려는 대상
• 간선: 두 정점 

A --(5)-- B
|         |
(2)      (3)
|         |
C --(4)-- D

 

 

2. 신장 트리 (Spanning Tree): 그래프의 모든 정점을 포함하면서, 사이클 없이 연결된 부분 그래프 

                                                 -> N개의 정점을 연결하려면 최소 N-1개의 간선이 필요하다.

 

3. 최소 신장 트리 (Minimum Spanning Tree) : 가능한 모든 신장 트리 중 간선들의 가중치 합이 가장 작은 트리 

 

 

알고리즘

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

간선 기반 알고리즘

 

<Union-Find 알고리즘 사용>

[알고리즘] 유니온 파인드(Union-Find)

 

<구현 과정>

1. 가중치 순으로 간선 정렬 후 가중치가 가장 작은 간선부터 선택 
2. 유니온 파인드로 사이클을 확인하며 간선 선택 
3. 모든 정점이 연결될 때까지 반복

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]
    
    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(n, edges):
    uf = UnionFind(n+1)
    mst = []
    total_weight = 0
    
    # 가중치 순으로 간선 저렬
    edges.sort(key=lambda x: x[2])
    
    for u, v, weight in edges:
        # 사이클이 없다면 간선을 추가
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
            total_weight += weight
            
    return mst, total_weight

 

 

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

정점 기반 알고리즘

 

<우선순위 큐(Heap)  사용>

 

<구현 과정>

1. 임의의 정점에서 인접한 간선 중 가중치가 가장 작은 간선을 선택해 트리 확장
2. 방문하지 않은 정점을 선택하며 계속해서 트리 확장
3. 모든 정점이 연결될 때까지 반복

import heapq

def prim(n, edges):
    # 그래프 초기화 (인접 리스트)
    graph = {i: [] for i in range(n)}
    for u, v, weight in edges:
        graph[u].append((weight, v))
        graph[v].append((weight, u))
    
    # 프림 알고리즘 시작
    mst = []  # 최소 스패닝 트리에 포함된 간선들
    visited = [False] * n  # 방문한 노드를 체크
    min_heap = [(0, 0)]  # (가중치, 시작 노드)를 우선순위 큐에 넣음
    
    total_weight = 0  # 최소 스패닝 트리의 가중치 합

    while len(mst) < n - 1:
        # 우선순위 큐에서 최소 가중치 간선 선택
        weight, u = heapq.heappop(min_heap)
        
        if visited[u]:
            continue
        
        # 노드 방문 처리
        visited[u] = True
        total_weight += weight

        # 방문한 노드는 최소 스패닝 트리에 간선으로 추가
        if weight != 0:  # 시작 노드는 가중치 0으로 시작
            mst.append((u, weight))
        
        # 인접한 노드들을 우선순위 큐에 추가
        for next_weight, v in graph[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (next_weight, v))
    
    return mst, total_weight