[자료 구조] 최소 신장 트리(MST) 개념 및 구현(Kruscal, Prim)

1.  최소 신장 트리

- 연결된 그래프 G(V.E)의 신장 트리란, 그래프 내의 모든 정점을 포함하는 트리다.

- 이 트리는 모든 정점들이 연결되어 있어야 하고, 사이클이 없어야 한다.

- 에지에 가중치가 주어진 그래프 G에서 G의 신장 트리 중에 에지 가중치 합이 최소가 되는 신장 트리를 

  최소 신장트리라고 한다.

 

2. 최소 신장 트리 알고리즘

1) 크루스칼(Kruskal)의 알고리즘

- 크루스칼의 알고리즘은 탐욕적인(greedy method) 방법을 이용한다. 

- 탐욕적인 방법이란 선택할 때마다 그 순간 가장 좋다고 생각 되는 것을 선택함으로써 최종적인 해답에 도달하는 방법

 

👉 알고리즘

- 가중치가 최소인 간선을 추가해가며 트리를 만들어 간다.

- 만약에 간선을 추가해서 사이클이 만들어 진다면 그 간선은 제외한다.

- 간선의 개수가 N - 1(N은 노드의 개수)이되면 모든 노드가 연결이 된 것이므로 종료한다.

 

- 그림을 보면서 이해하면 쉽다.

 

- 이 알고리즘을 구현하기 위해선 유니온 파인드 자료구조와 힙을 이용해야 한다.

=> [Algorithm] 유니온 파인드(Union-Find) 개념, 코드(C++) (tistory.com)

 

 

👉 구현

- 최소 힙과 유니온파인드를 이용하여 구현함.

- 최소 힙은 직접 구현하지 않고 STL을 이용함

#include <iostream>
#include <algorithm> 
#include <queue>
#include <vector>
using namespace std;

int parent[3001];

struct element {
	int v1, v2, key;
};

//가중치를 기준으로 오름차순으로 정렬해주는 오퍼레이터
struct cmp {
	bool operator()(element x, element y) {
		return x.key > y.key;
	}
};
int myfind(int x) {
	if (parent[x] == x) return x;
	return parent[x] = myfind(parent[x]);
}

void myunion(int a, int b) {
	a = myfind(a);
	b = myfind(b);
	if (a != b) {
		parent[b] = a;
	}
}

bool same_parent(int x, int y) {
	x = myfind(x);
	y = myfind(y);
	if (x == y) return true;
	else return false;
}


int main() {
	priority_queue<element, vector<element>, cmp>arr;
	int n, m; //정점, 엣지
	cin >> n >>m;
	for (int i = 0; i < m; i++) {
		int a, b, c; //v1, v2, key
		cin >> a >> b >> c;
		arr.push({ a, b, c});
	}
	
	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}

	int ans = 0; //가중치합
	while (!arr.empty()) {
		if (!same_parent(arr.top().v1, arr.top().v2)) {
			ans += arr.top().key;
			myunion(arr.top().v1, arr.top().v2);
		}
		arr.pop();
	}

	cout << ans;
	return 0;

}

- 시간 복잡도 :  O(mlogm) // 가중치를 정렬하는데 걸리는 시간(힙정렬) + 유니온 파인드 시간

 

2) 프림(Prim) 알고리즘

- 그래프 𝐺의 정점 하나로 이루어진 부분 트리에서 시작하여, 각 반복 과정마다 이미 구성된 부분 트리에 정점과 에지를 하나씩 추가한다.

- 이 때 부분 트리에 속한 정점과 인접한 정점 사이의 에지 중 가중치가 최소인 에지를 선택한다.

 

- 그림을 보면 이해하기 쉽다.

 

👉 알고리즘

1 임의의 정점을 선택하여 비어있는 T 에 포함 (이제 T 는 노드가 한개인 트리) 

2 T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다. 

3 찾은 간선이 연결하는 두 노드중, T 에 없던 노드를 T 에 포함시킨다.

4 모든 노드가 T 에 포함될때 까지 2,3 을 반복 해준다

 

👉 구현

- 우선순위 큐(stl)을 이용하여 구현함

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> p; //인접정점, 가중치 저장하는 페어

bool visited[3001];
vector<p> v[3001];

void prim(int start){
    visited[start] = true;
    priority_queue<p, vector<p>, greater<p>> pq; //인접정점의 가중치들을 저장할 큐(오름차순)

    for (int i = 0; i < v[start].size(); i++){
        int next = v[start][i].first;
        int nextCost = v[start][i].second;
        pq.push(p(nextCost, next));
    }

    int ans = 0;

    while (!pq.empty()){
        int here = pq.top().second;
        int hereCost = pq.top().first;

        pq.pop();

        if (visited[here]) continue; //만약에 방문한거면 넘어감

        visited[here] = true;
        ans += hereCost;

        for (int i = 0; i < v[here].size(); i++){
            int next = v[here][i].first;
            int nextCost = v[here][i].second;
            pq.push(p(nextCost, next));
        }
    }

    cout << ans;
}

int main()
{
    int n, m; //정점, 엣지
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a, b, c; //u, v, 가중치
        cin >> a >> b >> c;
        v[a].push_back(p(b, c)); //정점 a의 인접정점은 b고 가중치는 c
        v[b].push_back(p(a, c)); //정점 b의 인접정점은 a고 가중치는 c
    }

    prim(1);

    return 0;
}

- 시간복잡도 : O(n^2)