[C++] 그래프 이론 - 최소 신장 트리(크루스칼 알고리즘, Kruskal Algorithm)

1. 최소 신장 트리(MST, Minimun Spanning Tree) 란 ?

• 정의 : 그래프의 모든 정점을 연결하면서도 간선의 가중치 합이 최소가 되는 트리.
• 특징 : 
  • 사이클이 없어야 함.
  • V개의 정점을 가진 그래프라면 MST는 V-1개의 간선을 가진다.

 

2. 크루스칼 알고리즘 개요

• 정의 : 그래프 이론에서 사용되는 그리디 알고리즘 방식으로, 최소 신장 트리를 찾음.
• 작동 원리 : 간선들을 가중치 기준으로 정렬한 뒤, 사이클이 생기지 않도록 간선을 선택.
• 시간 복잡도 : O(E log E), E는 그래프의 간선의 수

 

3. 크루스칼 알고리즘의 동작 과정

• 간선 정렬 : 모든 간선을 가중치에 따라 오름차순 정렬
• 초기화 : 각 정점을 독립적인 집합으로 초기화 (Union-Find 이용)
• 간선 선택 : 
  • 가장 작은 가중치의 간선을 선택
  • 두 노드가 같은 집합에 속하지 않는 경우, 해당 간선을 MST에 추가
  • 두 노드를 같은 집합으로 병합 (Union 연산)
• 종료 조건 : V-1개의 간선이 선택되면 알고리즘 종료

 

다음과 같은 그래프가 있을때 최소 신장 트리를 찾아보자.

 

1. 첫 번째 간선(1,3 ) - 1 을 선택하고 find(1) 의 값과 find(3)의 값을 비교하여 같은 그룹에 속해 있는지 확인한다.

만약 다른 그룹이라면 MST에 추가하고, 두 정점을 같은 그룹으로 묶어 준다.

 

2. 다음 간선인 (1,4) - 2 에 대해서 1번과 같은 작업을 수행한다.

(3번과 4번이 갱신된 이유는, 1번의 부모(그룹)을 따라가면 3번이 나오기 때문에 실제로는 3번과 4번이 갱신되게 된다.)

 

다음 간선에 대해 같은 작업을 하면 아래와 같이 된다.

이후 남은 간선들에 대해 확인하더라도 두 노드가 같은 그룹에 속해있기 때문에 선택되지 않고, 이미 3번째 간선까지 확인했을때 "MST는 V-1개의 간선을 갖는다" 라는 조건을 만족하기 때문에 종료하게 된다.

 

4. 기초 예제

• 백준 1197번 : https://www.acmicpc.net/problem/1197

<소스코드>

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <string>

using namespace std;

int find(vector<int>& parent, int a)
{
	if (a == parent[a]) return a;
	else return parent[a] = find(parent, parent[a]);
}

void merge(vector<int>& parent, int a, int b)
{
	int fa = find(parent, a);
	int fb = find(parent, b);

	if (fa != fb)
	{
		if (fa < fb) parent[fa] = fb;
		else parent[fb] = fa;
	}
}

typedef struct Edge
{
	int s, e, cost;
}Edge;

bool cmp(Edge& a, Edge& b)
{
	return a.cost < b.cost;
}

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

	int n, m;
	cin >> n >> m;

	vector<Edge> edges(m);
	vector<int> group(n + 1); for (int i = 1; i <= n; i++) group[i] = i;

	for (int i = 0; i < m; i++) cin >> edges[i].s >> edges[i].e >> edges[i].cost;

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

	int edge_cnt = 0;
	int sum = 0;
	for (int i = 0; i < m; i++)
	{
		int s = edges[i].s;
		int e = edges[i].e;
		int cost = edges[i].cost;

		//같은 그룹에 속해 있다면 넘어감
		if (find(group, s) == find(group, e)) continue;

		merge(group, s, e);
		edge_cnt++;
		sum += cost;

		//종료 조건
		if (edge_cnt == n - 1) break;
	}
	cout << sum;
}

 

• 백준 14621 : https://www.acmicpc.net/problem/14621

<소스 코드>

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>


using namespace std;

int find(vector<int>& parent, int a)
{
	if (a == parent[a]) return a;
	else return parent[a] = find(parent, parent[a]);
}

void merge(vector<int>& parent, int a, int b)
{
	int fa = find(parent, a);
	int fb = find(parent, b);

	if (fa != fb)
	{
		if (fa < fb) parent[fa] = fb;
		else parent[fb] = fa;
	}
}

typedef struct Edge
{
	int s, e, cost;
}Edge;

bool cmp(Edge& a, Edge& b)
{
	return a.cost < b.cost;
}

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

	int n, m;
	cin >> n >> m;

	//여초대학인지 남초대학인지 여부 저장
	vector<char> borg(n + 1);
	for (int i = 1; i <= n; i++) cin >> borg[i];

	vector<Edge> edges(m);
	for (int i = 0; i < m; i++) cin >> edges[i].s >> edges[i].e >> edges[i].cost;

	//그룹 번호 초기화
	vector<int> group(n + 1);
	for (int i = 1; i <= n; i++) group[i] = i;

	//가중치 기반 정렬
	sort(edges.begin(), edges.end(), cmp);
	
	int edge_cnt = 0;
	int sum = 0;
	for (int i = 0; i < m; i++)
	{
		int s = edges[i].s;
		int e = edges[i].e;
		int cost = edges[i].cost;

		//같은 그룹이거나 , 같은 성별의 대학일경우 넘어감
		if (find(group, s) == find(group, e)) continue;
		if (borg[s] == borg[e]) continue;

		merge(group, s, e);
		edge_cnt++;
		sum += cost;
		if (edge_cnt == n - 1) break;
	}

	if (edge_cnt == n - 1) cout << sum;
	else cout << -1;
}

 

5. 크루스칼 알고리즘의 특징

• 장점 : 
  • 구현이 비교적 간단하다.
  • 간선 수가 적을 수록 유리해진다.

 

6. 프림 알고리즘과의 비교

비교항목	크루스칼 알고리즘	프림 알고리즘
접근 방식	간선 중심	정점 중심
데이터 구조	Union-Find	우선순위 큐
시간 복잡도	O(E log E)	O(E log V)