최소 신장 트리

최소 신장 트리(Minimum Spanning Tree) 

연결된 가중치 그래프에서 모든 정점을 연결하면 가중치의 합이 최소인 트리

 

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

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(vertices, edges):
    # 간선을 가중치순으로 정렬
    edges.sort(key=lambda x: x[2])
    
    uf = UnionFind(len(vertices))
    vertex_to_index = {v: i for i, v in enumerate(vertices)}
    
    mst = []
    total_weight = 0
    
    for u, v, weight in edges:
        u_idx = vertex_to_index[u]
        v_idx = vertex_to_index[v]
        
        if uf.union(u_idx, v_idx):
            mst.append((u, v, weight))
            total_weight += weight
    
    return mst, total_weight

# 예제
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
    ('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1),
    ('B', 'D', 5), ('C', 'D', 8), ('C', 'E', 10),
    ('D', 'E', 2)
]

mst, total_weight = kruskal(vertices, edges)
print(f"최소 신장 트리: {mst}")
print(f"총 가중치: {total_weight}")

 

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

import heapq

def prim(graph, start):
    mst = []
    visited = {start}
    total_weight = 0
    
    # 시작 정점과 연결된 모든 간선을 힙에 추가
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start]]
    heapq.heapify(edges)
    
    while edges:
        weight, u, v = heapq.heappop(edges)
        
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            total_weight += weight
            
            # 새로 추가된 정점과 연결된 간선들을 힙에 추가
            for neighbor, w in graph[v]:
                if neighbor not in visited:
                    heapq.heappush(edges, (w, v, neighbor))
    
    return mst, total_weight

# 예제 그래프
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
    'D': [('B', 5), ('C', 8), ('E', 2)],
    'E': [('C', 10), ('D', 2)]
}

mst, total_weight = prim(graph, 'A')
print(f"프림 알고리즘 MST: {mst}")
print(f"총 가중치: {total_weight}")