프림 알고리즘 (Prim Algorithm)

👉 크루스칼 알고리즘과 같은 원리로 동작하는 또 다른 스패닝 트리 알고리즘이다.

 

💡 크루스칼 알고리즘이란?

참고 : https://withseungryu.tistory.com/70?category=753127

크루스칼 알고리즘 (Kruskal Algorithm)

프림 알고리즘과 크루스칼 알고리즘의 큰 차이는 진행 방식입니다.

 

크루스칼 알고리즘은 여기저기서 산발적으로 만들어진 트리의 조각들을 합쳐 스피닝 트리를 만드는 방법이고,

프림 알고리즘은 하나의 시작점으로 트리에 간선을 하나씩 추가하며 스패닝 트리가 될 때까지 키우는 방식입니다.

 

 

위 그림을 보면 간선 (a,b)는 이미 트리에 속한 두 정점들을 연결하기 때문에 후 간선이 아닙니다. (사이클 방지)

이처럼 스패닝 트리를 찾아낼 때까지 후보 간선들 중 가중치가 가장 작은 간선을 추가하며 반복합니다.

 

📄 구현

구현 시 중요한 포인트는 한 정점에 닿는 간선이 두 개 이상일 경우 이들을 하나하나 검사하는 과정이

시간 낭비임을 깨달아야 합니다!

 

즉, 트리에 속하지 않는 정점에 대한 정보를 저장하고, 각 정점을 순회하면서 다음에 추가할 정점을 찾으며,

이를 위해 트리와 정점을 연결하는 간선의 최소 가중치를 저장하는 minWeight[] 배열을 활용 할 수 있습니다.

 

minWeight[]는 트리에 정점을 새로 추가할 때마다 이 정점에 인접한 간선들을 순회하면서 갱신합니다.

이렇게 하면 새정점을 찾는 작업 O(V)이 걸리며 따라서 전체 시간 복잡도는 O(V^2 + E)가 됩니다.

 

👉 구현 코드

const int MAX_V = 100; //문제마다 다르다.
const int INF = 987654321;

int V; //정점의 개수

vector<pair<int, int>> adj[MAX_V]; // 그래프의 인접 리스트

int prim(vector<pair<int, int>> selected) {
	selected.clear();

	vector<bool> added(V, false);//해당 정점이 트리에 포함되어 있는지

	vector<int> minWeight(V, INF), parent(V, -1); 

	int ret = 0;

	minWeight[0] = parent[0] = 0; //0번 정점을 시작점으로, 항상 트리에 가장 먼저 추가

	for (int iter = 0; iter < V; ++iter) {
		int u = -1;
		for (int v = 0; v < V; ++v)
			if (!added[v] && (u == -1 || minWeight[u] > minWeight[v]))
				u = v;

		if (parent[u] != u)
			selected.push_back(make_pair(parent[u], u));
		ret += minWeight[u];
		added[u] = true;

		for (int i = 0; i < adj[u].size(); ++i) {
			int v = adj[u][i].first, weight = adj[u][i].second;
			if (!added[v] && minWeight[v] > weight) {
				parent[v] = u;
				minWeight[v] = weight;
			}
		}
	}
	return ret;
}

 

 

💡 시간 복잡도 : O(|V|^2 + |E|) (크루스칼 알고리즘보다 빠르게 동작한다.)

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!