13.3.1 가중치가 가장 작은 에지를 찾는 방법

프림 알고리즘에서 가장 중요한 연산은 트리 안 정점과 트리 밖 정점을 잇는 여러 개의 에지 중에서 가중치가 가장 작은 에지를 찾는 것입니다. 이런 발상은 어떨까요? 먼저 각 정점마다 가중치를 저장해 둘 배열 w_list를 만듭니다. 이 배열에는 트리에 이미 속해 있는 정점에서 자신과 인접한 에지의 가중치를 저장할 텐데, 트리 내 정점 여러 개와 인접할 수 있기 때문에 어떤 값을 저장해야 할지 아직은 알 수 없습니다. 게다가 트리 정점은 원래 그래프의 정점 집합과 같아질 때까지 자라야 하므로 가중치가 가장 작은 에지는 시시각각 변할 것입니다.

그렇다면 배열 w_list를 먼저 굉장히 큰 값으로 초기화한 후 어떤 정점 v를 시작으로 w_list[v]=0으로 만듭니다. 그다음 adj[v] 집합을 순회하면서 각 정점까지 가중치를 w_list에 업데이트합니다. 이제 w_list를 쭉 순회하면서 아직 트리의 정점 집합 V(T)에 포함되지 않은 정점 중에서 가중치가 가장 작은 것을 선택하면 트리 밖 정점 u를 구할 수 있습니다. 그러고 나서 에지 (u, v)를 E(T)에 포함시키고 u도 트리 정점 집합에 포함시킵니다. 트리 정점 집합의 정점 개수가 하나 늘었습니다. 이런 과정을 반복하면 될 것 같습니다.

그런데 조금만 더 생각해 보면 w_list를 쭉 순회한다는 것은 빅오가 O(|V|)를 의미합니다. |V|는 원래 그래프의 정점 집합 개수를 의미합니다. 그리고 더 고민해 보면 필요한 것은 가장 가중치가 작은 에지입니다. 가장 작은 값을 지속적으로 가져온다면 최소 우선순위 큐 만한 것이 없을 것 같군요. 최소 우선순위 큐를 사용하면 빅오를 O(log |v|)까지 줄일 수 있습니다.