[C++] 최소 신장 트리(MST)

 

 

 

최소 신장 트리(MST: Minimum spanning tree)는 그래프에서 모든 노드를 연결할 때 사용된 Edges의 가중치의 합을 최소로 하는 트리를 의미한다. MST의 특징은 다음과 같다.

• 사이클을 포함하지 않는다. (사이클이 포함되면 가중치의 합이 최소가 될 수 없는 모순 발생)
• N개의 노드가 있다면 Edge의 개수는 N-1개다.

 

 

MST를 구할 때 사용하는 알고리즘은 다음과 같다.

1. 크루스칼(kruskal) 알고리즘
2. 프림(Prim) 알고리즘

이 포스터에선 크루스칼 알고리즘으로 MST를 구현해보도록 하겠다.

 

 

 

 

 

MST: 크루스칼 알고리즘

크루스칼 알고리즘으로 MST를 구할 땐 Union-Find 알고리즘을 사용한다.

Union-Find 알고리즘에 대해 익숙하지 않다면 아래 포스터를 참고하자.

 

https://gus6615.tistory.com/60

[C++] Union-Find

 

 

 

 

크루스칼 알고리즘에 사용되는 자료구조는 다음과 같다.

• 엣지 리스트: 그래프를 표현하기 위한 자료구조
• 유니온 파인드 리스트: 유니온 파인드를 위한 자료구조

※ Union-Find를 사용하는 이유는 사이클 판별을 위해서 사용한다.

 

가장 먼저 해야 할 일은 엣지 리스트와 유니온 파인드 리스트 초기화이다.

그 후 엣지 리스트를 오림차순 정렬을 수행한다.

정렬이 끝나고 다음 작업을 수행한다.

 

 

 

1. 가중치가 가장 적은 Edge를 선택한다.
2. 시작점과 끝점을 Find한다. 만약 시작점의 대표 노드와 끝점의 대표 노드가 동일하다면 사이클이 발생하는 것이기 때문에 연결하지 않는다. 즉, Find(start) != Find(end)일 경우에 Union으로 연결한다.
3. 연결한 Edge 개수가 N - 1이 될 때까지 위 과정을 반복한다.

 

 

 

 

 

MST: 크루스칼 알고리즘 코드 (백준 1197: 최소 스패닝 트리)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int P[10001];

struct Edge
{
	int start, end, weight;

	Edge(int _s, int _e, int _w)
	{
		start = _s;
		end = _e;
		weight = _w;
	}
};

int Find(int x)
{
	if (P[x] == x) return x;
	else return (P[x] = Find(P[x]));
}

void Union(int x, int y)
{
	int start = Find(x);
	int end = Find(y);

	if (start < end)
		P[end] = start;
	else
		P[start] = end;
}

int cmp(Edge a, Edge b)
{
	return a.weight < b.weight;
}

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

	int V, E, count = 0, total = 0;
	vector<Edge> edge_list;
	cin >> V >> E;

	for (int i = 1; i <= V; i++)
		P[i] = i;

	for (int i = 0; i < E; i++)
	{
		int start, end, weight;
		cin >> start >> end >> weight;
		edge_list.emplace_back(Edge(start, end, weight));
	}

	sort(edge_list.begin(), edge_list.end(), cmp);

	for (auto p : edge_list)
	{
		int start = Find(p.start);
		int end = Find(p.end);

		if (start != end)
		{
			Union(start, end);
			total += p.weight;
			count++;
			if (count == V - 1)
				break;
		}
	}

	cout << total << endl;

	return 0;
}