[Algorithm/Graph] 프림의 최소 신장 트리 알고리즘(prim's algorithm)

MST 문제란?

정점 집합 V와 가중치를 갖는 에지 집합 E로 구성된 그래프 G = <V, E>가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하는 문제

 

Cf) 크루스칼 알고리즘

그래프의 모든 에지를 최소 힙에 추가하고 사이클을 만들지 않는 최소 가중치의 에지를 이용하여 MST를 구성한다

 

프림 알고리즘은?

• BFS의 동작 방식과 유사하다.
• 먼저 시작 정점을 이용하여 경계를 구성한다
  • 경계는 이전에 방문했던 정점들에 의해 구성된다
• 현재 경계에 인접한 정점을 반복적으로 탐색한다
  • 이 때 경계를 관통하는 에지 중에서 가장 가중치가 적은 에지를 선택하고, 이 에지이 연결된 정점을 방문한다'
• 프림 알고리즘을 구현하려면 그래프의 각 정점에 경계로부터의 거리(distance)정보를 기록해야 한다.

 

프림 알고리즘의 구현

1. 모든 정점의 거리 값을 무한대로 초기화한다. 시작 정점에서 자기 자신까지의 거리는 0이므로 시작 정점의 거리 값은 0으로 설정한다. 그리고 모든 거리 값을 최소 힙 H에 추가한다.
2. 최소 힙 H로부터 정점을 하나 꺼낸다. 이 정점을 U라고 하면, 정점 U는 경계에서 가장 가까이 있는 정점이다. 이 정점을 MST에 추가하고, 이 정점을 포함하도록 경계를 새로 설정한다
3. U와 인접한 모든 정점 V에 대해, 만약 V의 거리 값이 (U, V)의 에지 가중치보다 크면 V의 거리 값을 (U, V)의 에지 가중치로 설정한다. 이러한 과정을 정점 U에 안착(settle)했다고 한다.
4. 방문하지 않은 정점이 있다면 2단계로 이동한다.
5. 모든 정점에 대해 안착하면, MST가 생성된다

template <typename T>
auto prim_MST(const Graph<T>& G, unsigned src)
{
	// 최소 힙
	priority_queue<Label<T>, vector<Label<T>>, greater<Label<T>>> heap;

	// 모든 정점에서 거리 값을 최대로 설정
	vector<T> distance(G.vertices(), numeric_limits<T>::max());

	set<unsigned> visited;	// 방문한 정점
	vector<unsigned> MST;	// 최소 신장 트리

	heap.emplace(Label<T>{src, 0});

	while (!heap.empty())
	{
		auto current_vertex = heap.top();
		heap.pop();

		// 현재 정점을 이전에 방문하지 않았다면
		if (visited.find(current_vertex.ID) == visited.end())
		{
			MST.push_back(current_vertex.ID);

			for (auto& e : G.edges(current_vertex.ID))
			{
				auto neighbor = e.dst;
				auto new_distance = e.weight;

				// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
				// 힙에 추가하고, 거리 값을 업데이트함.
				if (new_distance < distance[neighbor])
				{
					heap.emplace(Label<T>{neighbor, new_distance});
					distance[neighbor] = new_distance;
				}
			}

			visited.insert(current_vertex.ID);
		}
	}

	return MST;
}

 

시간 복잡도

MST 저장을 위해 인접 리스트를 사용하여 구현한 프림 알고리즘의 시간 복잡도는 O(ElogV)이다. 피보나치 최소 힙 구조를 사용하면 시간 복잡도는 O(E + VlogV)로 향상된다