[알고리즘] 크루스칼 알고리즘

jaehyeonLee·2024년 11월 25일

알고리즘

그래프

목록 보기

4/5

신장트리

신장트리란 n 개의 정점으로 이루어진 무방향 그래프 G에서 n 개의 모든정점과 n-1개의 간선으로 만들어진 트리이다

깊이 우선 신장트리

깊이 우선 탐색을 이용하여 생성된 신장트리

너비 우선 신장 트리

너비 우선 탐색을 이용하여 생성된 신장 트리

최소 비용 신장 트리 (MST)

무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중 치 합이 최소 인 신장트리라고 한다

가중치 그래프의 간선에 주어진 가중치
-비용이나 거리 , 시간을 의미하는 값이다

최소비용 신장트리를 만드는 알고리즘

크루스칼 알고리즘
프림 알고리즘

크루스칼 알고리즘

크루스칼 알고리즘이란 가중치가 높은 간선을 제거하면서 최소 비용신장트리르 만드는 방법이다

현재 내가 대학교 에서 듣는 수업에서는 크루스칼 알고리즘을 1 과 2로 나누어서 표현해주었지만 내가 주로 사용하고 있는 방법은 2와 유사하다고 생각되어 2를 위주로 설명을 하겠다

가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 방법

그래프 G의 모든간선을 가중치에 따라 오름차순으로 정리
그래프 G에 가중치가 가장 낮은 간선을 삽입한다 . 단 이때 사이클을 형성하는 간선은 삽입할 수 없으므로 그 다음으로 가중치가 낮은 간선을 삽입한다
그래프 G에 간선이 n-1개 삽입될때까지 2번 과정을 반복한다
그래프 G의 간선이 N-1개 가 되면 MST가 완성이된다

크루스칼 과정

초기상태 : 그래프의 간선 가중치에 따라 오름차순으로 정렬되어 있고 그래프 G는 정점만 있다

가중치가 낮은 간선 E,G를 넣어준다

나머지 간선중에서 가장 가중치가 낮은 간선 (A,B를 넣어준다)

이 과정을 반복하면

이렇게 신장트리가 완성이되는데 , 중간에보면 가중치 6인 (A,D)는 간선이 생기지않은것을 확인할수가 있는데 (A,D)를 잇는 간선이 생기게 되면 사이클이 형성이 되어버리기에 간선을 삽입할수 가 없다

코드로 구현

백준 1197 번 최소스패닝 트리 문제가 크루스칼 알고리즘을 구현하기에 적합한 문제라고 생각이 되어 이번에는 이문제를 통해 크루스칼 알고리즘을 구현해보도록 하겠다

#include"bits/stdc++.h"
using namespace std;
#define LL long long 
#define SIZE 10001
int V, E;
int a, b;
LL dis;
int parent[SIZE];
LL result = 0;
struct Node
{
	int x, y;
	LL distance;
	Node(int x, int y ,LL distance)
	{
		this->x = x;
		this->y = y;
		this->distance = distance;
	}
	bool operator <(Node& edge)
	{
		return this->distance < edge.distance;
	}
};
vector<Node>vec;
int Find(int x)
{
	if (parent[x] == x)return x;
	return parent[x] = Find(parent[x]);
}
bool Same(int x, int y)
{
	x = Find(x);
	y = Find(y);
	return x == y;
}
void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
	if (x != y)
	{
		if (x < y)parent[y] = x;
		else parent[x] = y;
	}
}
void Kruskal()
{
	for (int i = 0; i < SIZE; i++)
	{
		parent[i] = i;
	}
	for (int i = 0; i < (int)vec.size(); i++)
	{
		if (!Same(vec[i].x, vec[i].y))
		{
			result += vec[i].distance;
			Union(vec[i].x, vec[i].y);
		}
	}
	cout << result << '\n';
}
void Insert()
{
	cin >> V >> E;
	for (int i = 0; i < E; i++)
	{
		cin >> a >> b >> dis;
		vec.push_back({ a,b,dis });
	}
	sort(vec.begin(), vec.end());
	Kruskal();
}

int main()
{
	Insert();
	return 0;
}

Union Find

int Find(int x)
{
	if (parent[x] == x)return x;
	return parent[x] = Find(parent[x]);
}
bool Same(int x, int y)
{
	x = Find(x);
	y = Find(y);
	return x == y;
}
void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
	if (x != y)
	{
		if (x < y)parent[y] = x;
		else parent[x] = y;
	}
}

크루스칼 알고리즘에는 유니온파인드 알고리즘이 필수적이다 유니온 파인드알고리즘은 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.
크루스칼 알고리즘에서는 이 유니온파인드를 이용해 사이클 생성을 방지해줄수있다

그림에서 보면 A와 D가 간선을 연결하려는 과정이라고 보자 허나 이미
유니온파인드로인해 parent[A]==parent[B]==parent[C]==parent[D]가 되어있다 그러다보니

void Kruskal()
{
	for (int i = 0; i < SIZE; i++)
	{
		parent[i] = i;
	}
	for (int i = 0; i < (int)vec.size(); i++)
	{
		if (!Same(vec[i].x, vec[i].y)) //<- 여기 
		{
			result += vec[i].distance;
			Union(vec[i].x, vec[i].y);
		}
	}
	cout << result << '\n';
}

위 코드에서 A와 D는 Same 함수를 통해 true 값이 나오기 때문에 간선을 삽입하지않고 넘어가게 해줄수가 있다