프림(Prim) 알고리즘

정의

프림(Prim) 알고리즘은 그래프 이론에서 최소신장트리(Minimum Spanning Tree, MST)를 구하는 데 사용되는 알고리즘 중 하나입니다. MST는 그래프의 모든 노드를 포함하면서 사이클이 없는 부분 그래프 중에서 전체 가중치 합이 최소인 트리를 의미합니다.

프림 알고리즘은 크루스칼(Kruskal) 알고리즘과 함께 최소신장트리를 찾는 대표적인 알고리즘으로 사용됩니다. 둘 중에서 어떤 알고리즘을 선택할지는 그래프의 특성과 구현 방식 등에 따라 결정됩니다.

동작 방식

1. 임의의 시작 노드를 선택합니다.
2. 선택한 노드와 연결된 간선들 중에서 최소 가중치의 간선을 찾습니다.
3. 해당 간선으로 연결된 노드를 최소신장트리에 추가합니다.
4. 이미 선택된 노드들과 연결된 간선들 중에서 최소 가중치의 간선을 찾습니다.
5. 해당 간선으로 연결된 노드를 최소신장트리에 추가합니다.
6. 위의 과정을 모든 노드가 포함될 때까지 반복합니다.

장점과 단점

장점:

• 구현이 간단하고 직관적이다: 프림 알고리즘은 간선을 하나씩 선택하며 최소신장트리를 확장해가는 방식으로 동작하기 때문에 구현이 상대적으로 쉽습니다. 용어와 개념도 이해하기 쉽습니다.

• 효율적인 실행 시간: 프림 알고리즘은 노드의 개수가 많은 밀집 그래프(Dense Graph)에서 효율적으로 동작합니다. 최적화된 구현을 사용하면 시간 복잡도는 O(E log V) 수준이다. (V는 노드의 수, E는 간선의 수)
  

• 무방향 그래프에 적합: 프림 알고리즘은 무방향 그래프에서 사용하는 것이 자연스럽습니다. 무방향 그래프의 간선은 양방향으로 연결되어 있기 때문에 간선 선택에 있어서 방향성을 고려할 필요가 없습니다.

단점:

• 간선의 수가 적은 희소 그래프(Sparse Graph)에서는 성능이 떨어질 수 있다: 프림 알고리즘은 간선을 탐색하면서 최소 가중치의 간선을 찾기 때문에 희소 그래프에서는 불필요한 탐색이 발생할 수 있습니다. 이 경우 크루스칼 알고리즘이 더 효율적일 수 있습니다.

• 우선순위 큐 사용 필요: 프림 알고리즘에서는 노드와 연결된 간선 중에서 최소 가중치의 간선을 찾아야 합니다. 이를 위해서 우선순위 큐(Priority Queue)를 사용해야 하며, 우선순위 큐의 구현에 따라 성능이 달라질 수 있습니다.

• 시작 노드에 따라 결과가 달라질 수 있다: 프림 알고리즘은 임의의 시작 노드를 선택하여 MST를 구합니다. 따라서 시작 노드에 따라 최종적인 MST의 구성이 달라질 수 있습니다. 이를 보완하기 위해 여러 번 실행하여 결과를 평균화하는 방법을 사용하기도 합니다.

구현

import heapq

def prim_mst(graph):
    # 시작 노드를 임의로 선택합니다.
    start_node = list(graph.keys())[0]
    
    # 방문한 노드와 방문하지 않은 노드를 저장하는 변수를 초기화합니다.
    visited = set([start_node])
    not_visited = [(cost, start_node, neighbor) for neighbor, cost in graph[start_node].items()]
    heapq.heapify(not_visited)
    
    # 최소신장트리의 간선들을 저장하는 변수를 초기화합니다.
    mst_edges = []
    
    while not_visited:
        # 아직 방문하지 않은 노드 중에서 최소 가중치의 간선을 선택합니다.
        cost, node, neighbor = heapq.heappop(not_visited)
        
        if neighbor not in visited:
            # 선택한 간선을 최소신장트리에 추가합니다.
            mst_edges.append((node, neighbor, cost))
            visited.add(neighbor)
            
            # 새로 추가된 노드의 인접 간선들을 not_visited에 추가합니다.
            for next_neighbor, next_cost in graph[neighbor].items():
                if next_neighbor not in visited:
                    heapq.heappush(not_visited, (next_cost, neighbor, next_neighbor))
    
    return mst_edges

graph = {
    'A': {'B': 3, 'C': 1},
    'B': {'A': 3, 'C': 3, 'D': 6},
    'C': {'A': 1, 'B': 3, 'D': 4},
    'D': {'B': 6, 'C': 4}
}

mst = prim_mst(graph)
print("Minimum Spanning Tree:")
for edge in mst:
    print(f"{edge[0]} - {edge[1]}: {edge[2]}")