[C++] 최소 신장 트리(크루스칼)

최소 신장 트리(Minimum Spanning Tree)

모든 정점을 연결하는 트리를 신장 트리라고 하는데 가중치를 갖는 신장 트리 중 가중치의 합이 가장 작은 신장 트리를 최소 신장 트리라고 한다.

 

대표적으로 크루스칼 알고리즘이 있으며, 그 외에도 프림 알고리즘과 솔린 알고리즘이 있다.

• 프림 알고리즘: 임의의 정점을 루트 노드로 삽입한 후 인접한 정점의 간선 중 가장 작은 정점을 트리에 삽입하며 최소 신장 트리를 만든다.
• 솔린 알고리즘

 

1. 크루스칼 알고리즘(Kruskal's algorithm)

1) 기본 원리

모든 간선의 가중치를 오름차순으로 정렬한 후 그 목록을 차례대로 순회하며 사이클이 생기지 않도록 최소 신장 트리에 삽입하며 최소 신장 트리를 만든다.

 

2) 문제

 

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

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

vector<int> parent;
vector<pair<int, pair<int, int>>> graph;	// {가중치, {정점A, 정점B}}

int Find(int v)
{
	if (parent[v] != v)
		parent[v] = Find(parent[v]);
	return parent[v];
}

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int V, E;
	cin >> V >> E;

	parent.resize(V + 1);
	for (int i = 1; i <= V; i++)
		parent[i] = i;

	int A, B, C;
	for (int i = 0; i < E; i++)
	{
		cin >> A >> B >> C;
		graph.push_back({ C, {A,B} });
	}

	sort(graph.begin(), graph.end());	// 가중치를 기준으로 오름차순 정렬

	int ans = 0;
	for (int i = 0; i < E; i++)
	{
		int parentA = Find(graph[i].second.first);
		int parentB = Find(graph[i].second.second);
		if (parentA != parentB)	// 사이클 방지
		{
			parent[parentA] = parentB;
			ans += graph[i].first;
		}
	}
	cout << ans;
}

 

https://www.acmicpc.net/problem/13418

13418번: 학교 탐방하기

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

int n, m;
vector<pair<int, pair<int, int>>> graph; 
vector<int> parent;

int Find(int v)
{
	if (parent[v] != v)
		parent[v] = Find(parent[v]);
	return parent[v];
}

int GetAnswer(bool min)
{
	for (int i = 0; i <= n; i++)
		parent[i] = i;

	if (min)
		sort(graph.begin(), graph.end());
	else
		sort(graph.rbegin(), graph.rend());

	int answer = 0;
	for (int i = 0; i <= m; i++)
	{
		int parentA = Find(graph[i].second.first), parentB = Find(graph[i].second.second);
		if (parentA != parentB)
		{
			parent[parentA] = parentB;
			answer += graph[i].first;
		}
	}

	return answer * answer;
}

int main()
{
	cin >> n >> m;
	for (int i = 0, a, b, c; i <= m; i++)
	{
		cin >> a >> b >> c;
		graph.push_back({ c == 0 ? 1 : 0, {a,b} });
	}

	parent.resize(n + 1);
	cout << GetAnswer(false) - GetAnswer(true);
}