[C++ 자/알 Note] Kruskal 알고리즘

스패닝트리(ST)

최소의 간선으로 모든 정점을 연결하겠다는 것을 의미한다
사이클이 발생하지 않는 것이 특징이고
간선 개수는 정점개수-1이 된다

최소스패닝트리(MST)

가중치(비용)가 최소로 되는 스패닝트리를 의미한다

KRUSKAL MST 알고리즘

Kruskal 알고리즘이란 그리디를 이용하는 것이 특징이다
지금 이 순간에 최적인 답을 선택해 결과 도출한다는 것이다

 

Kruskal 알고리즘의 특징은 아래와 같다

1) 지금 이 순간에 가장 작은 비용들을 선택하기

2) 사이클은 발생하지 않도록 해야 한다

 

Kruskal 알고리즘의 내부 동작은 아래와 같다

가장 작은 비용들을 선택하기 위해서

가중치값이 작은 순으로 정렬을 해놓고 하나씩 선택을 하면 된다

사이클 발생 여부를 확인하는 방법은 그룹화(집합) 개념을 이용하면 된다
간선 및 정점이 추가되는 경우에서

다른 그룹끼리는 사이클이 발생하지 않는다

반면, 같은 그룹끼리는 사이클이 발생한다
따라서, 상호배타적 집합(Disjoint Set)을 활용해 해당 부분을 해결하면 된다

 

개념 추천 영상: https://www.youtube.com/watch?v=KN7kPliKn5g

 

KRUSKAL MST 알고리즘 구현

1) Disjoint Set 구현

class DisjointSet
{
public:
	DisjointSet(int n) : _parent(n), _rank(n, 1)
	{
		for (int i = 0; i < n; i++)
			_parent[i] = i;
	}

	int Find(int u)
	{
		if (u == _parent[u])
			return u;

		return _parent[u] = Find(_parent[u]);
	}

	void Merge(int u, int v)
	{
		u = Find(u);
		v = Find(v);

		if (u == v)
			return;

		if (_rank[u] > _rank[v])
			swap(u, v);

		_parent[u] = v;

		if (_rank[u] == _rank[v])
			_rank[v]++;
	}

private:
	vector<int> _parent;
	vector<int> _rank;
};

 

2) 그래프 생성

struct Vertex
{
	// int data;
};

vector<Vertex> vertices;
vector<vector<int>> adjacent; // 인접 행렬

void CreateGraph_Kruskal()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1));

	adjacent[0][1] = adjacent[1][0] = 15;
	adjacent[0][3] = adjacent[3][0] = 35;
	adjacent[1][2] = adjacent[2][1] = 5;
	adjacent[1][3] = adjacent[3][1] = 10;
	adjacent[3][4] = adjacent[4][3] = 5;
	adjacent[3][5] = adjacent[5][3] = 10;
	adjacent[5][4] = adjacent[4][5] = 5;
}

 

3) 가중치(비용)를 위한 구조체 생성

struct CostEdge
{
	int cost;
	int u;
	int v;

	bool operator<(CostEdge& other)
	{
		return cost < other.cost;
	}
};

 

4) KRUSKAL 적용

int Kruskal(vector<CostEdge>& selected)
{
	int ret = 0;

	selected.clear();

	vector<CostEdge> edges;

	for (int u = 0; u < adjacent.size(); u++)
	{
		for (int v = 0; v < adjacent[u].size(); v++)
		{
			if (u > v) // 중복 스킵
				continue;

			int cost = adjacent[u][v];
			if (cost == -1) // 미연결 스킵
				continue;

			edges.push_back(CostEdge{ cost, u, v });
		}
	}

	std::sort(edges.begin(), edges.end()); // 최소 가중치를 선택하기위한 정렬

	DisjointSet sets(vertices.size());

	for (CostEdge& edge : edges)
	{
		// 같은 그룹이면 스킵 (사이클 발생 막기)
		if (sets.Find(edge.u) == sets.Find(edge.v))
			continue;

		// 두 그룹 합치기
		sets.Merge(edge.u, edge.v);
		selected.push_back(edge);
		ret += edge.cost;
	}

	return ret;
}