그래프의 최소 비용 문제

1. 최소 신장 트리(MST, Minimum Spanning Tree) 구하기

   • 크루스칼(Kruskal) 알고리즘
     : 간선이 적고 노드가 많을 때 유리하다.
   • 프림(Prim) 알고리즘
     : 간선이 많을 때 유리하다.

2. 최단 경로 구하기

   • 다익스트라(Dijkstra) 알고리즘

프림(Prim) 알고리즘

그리디(Greedy) 알고리즘 사용

특징

서로소인 2개의 집합 정보를 유지한다. 즉, 트리 정점들(MST를 만들기 위해 선택된 정점들)과 비트리 정점들(선택되지 않은 정점들) 집합이 있다.

방법

선택된 노드 집합에서 선택되지 않은 노드와 연결되는 간선 중에 하나씩 선택하면서 MST를 만들어 가는 방식

1. 임의의 정점을 하나 선택한다.
2. 선택한 정점을 선택된 노드 집합에 추가한다.
3. 선택된 정점에 연결된 간선들 중 선택되지 않은 노드와 연결되고, 그 중에서 가장 작은 가중치를 가진 간선과 연결된 다음 정점을 선택한다.
4. 모든 정점이 선택될 때까지 2~3 과정을 반복한다.

코드

def Prim(graph):
  visited = [] # 정점(index)이 신장 트리에 포함되었는지 여부 저장
  min_costs = [] # 다른 정점에서 해당 정점(index)로 올 수 있는 최소 비용
  
  mst_cost = 0 # 최소신장트리 비용
  min_costs[start_node] = 0 # 임의의 시작점의 간선 비용을 0으로 세팅
  
  # 4. 모든 정점이 선택될 때까지 반복한다.
  for _ in graph:
    # 1. 신장트리에 포함되지 않은 정점 중 최소간선비용의 정점을 찾는다.
    for node in graph:
      if not visited[node] and min_cost > min_costs[node]:
        min_cost = min_costs[node]
        min_node = node
    
    # 2. 찾은 정점을 선택된 정점 집합(신장 트리)에 추가한다(포함시킨다).
    visited[min_node] = true;
    mst_cost = mst_cost + min_cost
    
    # 3. 선택된 정점 기준으로 신장트리에 연결되지 않은 타 정점과의 간선 비용을 최소로 업데이트한다.
    for node, cost in graph[min_node]:
      if not visited[node] and cost < min_costs[node]:
        min_costs[node] = cost
        
  return mst_cost