[PS] MST

MST 개념과 종류

MST : Min Spanning Tree - 하나의 그래프에서 최소한의 간선으로 모든 node를 연결하는 트리로 그리디 기반으로 최소비용을 구하는 것

종류
1. Kruskal(크루스칼) 알고리즘
2. Prime 알고리즘

Kruskal 알고리즘 (시간복잡도 : NlogN)

1. Sort 혹은 PQ를 이용하여 가장 cost가 작은 간선부터 선택
2. Union-Find를 통해 Cycle 판정

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

struct Edge
{
	int from;
	int to;
	int cost;
};

vector<int> parents;

// 우선순위 : cost가 최소
int cmp(Edge left, Edge right)
{
	// true(1)을 반환하면 그대로, false(0)을 반환하면 swap
	return left.cost < right.cost;
}
// 보스 찾기
int Find(int x)
{
	if (x == parents[x]) return x;

	return parents[x] = Find(parents[x]);
}

// 그룹화
void Union(int a, int b)
{
	int pa = Find(a);
	int pb = Find(b);

	parents[pa] = pb;
}

int main()
{
	int n, e;
	cin >> n >> e;
	parents = vector<int>(n + 1);
	for (int i = 0; i <= n; i++)
	{
		parents[i] = i;
	}
	vector<Edge> edge;

	// 간선 갯수 만큼 출발지,목적지,비용 입력받기
	for (int i = 0; i < e; i++)
	{
		int from, to, cost;
		cin >> from >> to >> cost;
		edge.push_back({ from,to,cost });
	}
	// edge vector 우선순위 : cost 최소
	sort(edge.begin(), edge.end(), cmp);

	int sum = 0;
	for (int i = 0; i < e; i++)
	{
		Edge now = edge[i];

		// Cycle 판정
		if (Find(now.from) == Find(now.to)) continue;

		Union(now.from, now.to);
		sum += now.cost;
	}

	cout << sum;

	return 0;
}

Prim 알고리즘

인접행렬 및 인접리스트로 데이터를 input하고, 선택 가능한 간선 정보를 Priority_Queue에 추가합니다.
간선의 선택 조건
1. PQ에서 꺼낼 우선순위
2. 목적지가 이미 그룹으로 합쳐졌는지 used[ ]를 통해 판별한다.

Union-Find는 여러 개의 그룹이 있을 때 사용한다.

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

struct Edge
{
	int to;
	int cost;
};
// 우선순위 : cost 최소
int operator< (Edge left, Edge right)
{	
	// true(1)이면 SWAP false(0)이면 유지
	return left.cost > right.cost;
}

void prim()
{
	int n, e;
	cin >> n >> e;
	vector<vector<Edge>> v(n + 1, vector<Edge>());
	vector<int> used(n + 1, 0);
	for (int i = 0; i < e; i++)
	{
		int from, to, cost;
		cin >> from >> to >> cost;
		v[from].push_back({ to,cost });
		v[to].push_back({ from,cost });
	}
	// 우선순위 : cost 최소
	priority_queue<Edge> pq;
	// 초기 셋팅 : 1에서 시작하는 모든 경로를 pq에 입력
	for (int i = 0; i < v[1].size(); i++)
	{
		int to = v[1][i].to;
		int cost = v[1][i].cost;
		pq.push({ to,cost });
	}
	used[1] = 1;
	int sum = 0;
	
	while (!pq.empty())
	{
		Edge now = pq.top();
		pq.pop();
		int to = now.to;
		int cost = now.cost;
		// 이미 왔던 경로 피하기
		if (used[to] == 1) continue;
		used[to] = 1;
		sum += cost;

		// 다음 위치에서 갈 수 있는 경로들 push하기
		for (int i = 0; i < v[to].size(); i++)
		{
			int t = v[to][i].to;
			int d = v[to][i].cost;
			pq.push({ t,d });
		}
	}
	cout << sum;
}

int main()
{
	prim();

	return 0;
}