최소신장트리(MST)

신장트리 = Spanning Tree

- 그래프가 존재할때 모든 정점에 대하여 최소한의 연결만 남긴 그래프.

- 한 그래프에서 여러가지의 신장트리가 존재할 수 있다.

- 모든 정점을 포함해야 하며 모두 연결 되어있어야 함.(버텍스가 N개일때 간선은 N-1개)

- 사이클이 존재하면 안된다.

- DFS나 BFS로 구할 수 있다.

 

최소신장트리 = Minimum Spanning Tree

- 간선에 가중치가 있는 그래프의 신장 트리에서 간선의 가중치의 합이 최소가 되는 신장 트리.

- 주요 방법으론 Prim 알고리즘와 Kruskal 알고리즘이 있음.

 

Kruskal 알고리즘

- 간선을 가중치 기준 오름차순으로 정렬하여 순서대로 판단해나가는 알고리즘.

- 간선을 고를 때 사이클이 나오지 않는지 판단해야 함.

- 사이클 판단으론 Union-Find 알고리즘이 사용됨.

 

Union-Find 알고리즘

- 각 버텍스에 대해 부모 노드를 Find 하고 Union 하는 알고리즘.

- 두 버텍스에 대하여 각각 최종 부모노드를 Find 했을때 두 버텍스의 최종 부모노드가 같다면 해당 간선은 사이클을 발생시킨다고 판단 가능함.

- Kruskal 알고리즘에서 사용 시 두번째 버텍스의 최종 부모가 첫번째 버텍스의 최종 부모가 되도록 업데이트를 해주어야 Find가 계속 이루어질 수 있음.

 

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

class edge
{
public:
	int first_vertex;
	int second_vertex;
	int value;

	edge(int n1, int n2, int n3)
	{
		first_vertex = n1;
		second_vertex = n2;
		value = n3;
	}
};

bool edge_cmp(edge& e1, edge& e2)
{
	if (e1.value < e2.value) return true;
	else return false;
}

bool Union_Find(int parent[], int first_vertex, int second_vertex)
{
	int fv = first_vertex;
	int sv = second_vertex;
	while (!(fv == parent[fv]))
	{
		fv = parent[fv];
	}
	while (!(sv == parent[sv]))
	{
		sv = parent[sv];
	}
	if (fv == sv)
	{
		return false;
	}
	else
	{
		// 두번째 버텍스의 최종 부모가 첫번째 버텍스의 최종 부모가 됨
		parent[sv] = parent[fv];
		return true;
	}
}

int Kruskal(vector<edge> edge_vector, int vertex_number)
{
	//MST의 가중치의 합을 리턴
	int parent[10001];
	for (int i = 0; i < 10001; i++)
	{
		parent[i] = i;
	}

	int rtn = 0;
	int index = 0;
	int edge_count = 0;
	int cmd = edge_vector.size();
	while (cmd--)
	{
		edge current_edge = edge_vector[index++];
		if (Union_Find(parent, current_edge.first_vertex, current_edge.second_vertex))
		{
			edge_count++;
			rtn += current_edge.value;
		}
	}

	return rtn;
}

int main()
{
	int vertex_number;
	int edge_number;
	vector<edge> edge_vector;

	cin >> vertex_number >> edge_number;

	int cmd = edge_number;

	while (cmd--)
	{
		int n1;
		int n2;
		int n3;

		cin >> n1 >> n2 >> n3;

		if (n1 > n2)
		{
			int tmp = n1;
			n1 = n2;
			n2 = tmp;
		}

		edge_vector.push_back(edge(n1, n2, n3));
	}

	sort(edge_vector.begin(), edge_vector.end(), edge_cmp);

	cout << Kruskal(edge_vector, vertex_number) << endl;
}

백준 1197번 문제(https://www.acmicpc.net/problem/1197)