Python을 이용한 최소 신장 트리 알고리즘의 이해와 구현

최소 신장 트리(Minimum Spanning Tree, MST)는 그래프 내 모든 노드를 최소의 비용으로 연결하는 서브트리입니다. 이 서브트리는 그래프의 모든 노드를 포함하며, 사이클을 형성하지 않습니다. MST는 네트워크 설계, 클러스터 분석, 이미지 분할 등 다양한 영역에서 응용됩니다. Python에서는 주로 프림 알고리즘(Prim's Algorithm)과 크루스칼 알고리즘(Kruskal's Algorithm)을 사용하여 MST를 구현할 수 있습니다. 이 글에서는 이 두 알고리즘을 Python으로 구현하는 방법을 설명하겠습니다.

 

프림 알고리즘

프림 알고리즘은 하나의 정점에서 시작하여, 연결된 노드 집합을 점차 확장해 나가면서 최소 신장 트리를 구성합니다. 우선순위 큐를 활용하여 구현할 수 있으며, Python의 heapq 모듈을 사용할 수 있습니다. 다음은 프림 알고리즘의 간단한 구현 예입니다:

 

import heapq

def prim(graph, start):
    mst = []
    used = set([start])
    edges = [(cost, start, to) for to, cost in graph[start].items()]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in used:
            used.add(to)
            mst.append((frm, to, cost))
            
            for next_to, next_cost in graph[to].items():
                if next_to not in used:
                    heapq.heappush(edges, (next_cost, to, next_to))
    
    return mst

# 그래프 예제
graph = {
    'A': {'B': 4, 'H': 8},
    'B': {'A': 4, 'C': 8, 'H': 11},
    'C': {'B': 8, 'D': 7, 'F': 4, 'I': 2},
    'D': {'C': 7, 'E': 9, 'F': 14},
    'E': {'D': 9, 'F': 10},
    'F': {'C': 4, 'D': 14, 'E': 10, 'G': 2},
    'G': {'F': 2, 'H': 1, 'I': 6},
    'H': {'A': 8, 'B': 11, 'G': 1, 'I': 7},
    'I': {'C': 2, 'G': 6, 'H': 7}
}

print(prim(graph, 'A'))

 

 

반응형

 

 

 

크루스칼 알고리즘

크루스칼 알고리즘은 간선을 비용에 따라 오름차순으로 정렬한 뒤, 사이클을 형성하지 않는 선에서 최소 비용의 간선을 선택하여 MST를 구성합니다. 유니온 파인드(Union-Find) 자료구조를 사용하여 간선이 두 노드를 사이클 없이 연결할 수 있는지 확인합니다. 다음은 크루스칼 알고리즘의 Python 구현입니다:

 

def find(parent, i):
    if parent[i] == i:
        return i
    return find(parent, parent[i])

def union(parent, rank, x, y):
    xroot = find(parent, x)
    yroot = find(parent, y)
    
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

def kruskal(graph):
    result = []
    i, e = 0, 0
    edges = sorted([(graph[u][v], u, v) for u in graph for v in graph[u]])

    parent = {}
    rank = {}

    for node in graph:
        parent[node] = node
        rank[node] = 0

    while e < len(graph) - 1:
        w, u, v = edges[i]
        i = i + 1
        x = find(parent, u)
        y = find(parent, v)

        if x != y:
            e = e + 1
            result.append((u, v, w))
            union(parent, rank, x, y)

    return result

print(kruskal(graph))

 

 

이 두 알고리즘은 각각 그래프의 특성과 필요에 따라 선택할 수 있으며, Python을 통해 간결하게 구현할 수 있습니다. 프림 알고리즘은 연결 그래프에 더 적합하고, 크루스칼 알고리즘은 희소 그래프(간선이 적은 그래프)에 더 유리합니다. 이러한 최소 신장 트리 알고리즘은 복잡한 네트워크 설계와 최적화 문제에 필수적인 도구입니다.