[python] 프림 알고리즘

07 Dec 2023

python

프림 알고리즘은 최소 신장 트리(MST, Minimum Spanning Tree)를 구하는 알고리즘 중 하나입니다. MST는 그래프에서 최소 비용으로 모든 노드를 연결하는 부분 그래프입니다.

프림 알고리즘은 다음과 같은 과정으로 동작합니다:

임의의 시작 노드를 선택합니다.
선택한 노드와 연결된 간선 중에서 가장 작은 비용의 간선을 선택합니다.
선택한 간선의 연결된 노드를 방문할 때마다, 이미 선택된 노드와 연결된 간선 중에서 최소 비용의 간선을 선택합니다.
모든 노드를 방문할 때까지 2, 3번 과정을 반복합니다.

아래는 프림 알고리즘을 파이썬으로 구현한 예시 코드입니다:

def prim(graph):
    # 그래프의 첫 번째 노드를 시작 노드로 선택
    start_node = list(graph.keys())[0]
    
    # 시작 노드를 방문한 것으로 처리
    visited = set([start_node])
    
    # 선택한 간선들을 저장할 리스트
    edges = []
    
    while len(visited) < len(graph):
        min_edge = None
        min_cost = float('inf')
        
        for node in visited:
            for neighbor, cost in graph[node].items():
                if neighbor not in visited and cost < min_cost:
                    min_edge = (node, neighbor)
                    min_cost = cost
        
        if min_edge:
            edges.append(min_edge)
            visited.add(min_edge[1])
    
    return edges

# 그래프 예시
graph = {
    'A': {'B': 7, 'D': 5},
    'B': {'A': 7, 'C': 8, 'D': 9, 'E': 7},
    'C': {'B': 8, 'E': 5},
    'D': {'A': 5, 'B': 9, 'E': 15, 'F': 6},
    'E': {'B': 7, 'C': 5, 'D': 15, 'F': 8, 'G': 9},
    'F': {'D': 6, 'E': 8, 'G': 11},
    'G': {'E': 9, 'F': 11}
}

# 프림 알고리즘 실행
minimum_spanning_tree = prim(graph)
print(minimum_spanning_tree)

위 예시 코드를 실행하면, 다음과 같은 결과가 출력됩니다:

[('A', 'D'), ('D', 'F'), ('A', 'B'), ('B', 'E'), ('E', 'C'), ('E', 'G')]

프림 알고리즘을 사용하면 그래프에서 최소 비용의 신장 트리를 구하는데 사용할 수 있습니다. 자세한 내용은 다양한 자료와 참조를 통해 공부하시기 바랍니다.