📌 Kruskal 알고리즘

탐욕적인 방법 (Greedy Method)을 이용하여 그래프 내의 최소 신장 트리를 찾아내는 알고리즘 중 하나이다.

💡 알고리즘의 동작 과정

위 그림의 그래프를 통해 Kruskal 알고리즘의 동작 과정을 알아보자.

1. 간선 정렬 및 부모 노드 기록

주어진 그래프의 모든 간선들을 가중치를 기준으로 오름차순 정렬한다.
또한, 최소 신장 트리의 순환성을 확인하기 위해 부모 노드를 기록한다.
간선을 통해 연결된 두 노드의 최상위 부모 노드가 동일할 경우, 해당 간선을 이으면 순환이 생기므로 이를 방지하기 위함이다.

초기 상태에서는 각 노드들이 이어져 있지 않은 상태를 상정하고 있기 때문에 각 노드들의 부모 노드는 자기 자신을 가리킨다.

2. 간선 순회

정렬된 간선들을 처음부터 차례대로 순회하면서 연결을 시도한다.
첫 번째 간선과 연결된 두 개의 노드는 0과 1이고, 각각 자기 자신을 부모 노드로 가리키고 있기 때문에 순환이 발생하지 않는다고 판단할 수 있다.
따라서 해당 간선을 사용하여 두 노드를 연결한다.

노드 0과 노드 1이 연결되었기 때문에 연결된 노드의 부모 노드를 갱신한다.
이 때, 부모 노드는 두 노드 중 인덱스 값이 더 적은 노드의 부모를 따라가기로 결정한다.

두 번째 간선과 세 번째 간선을 순회하고 난 다음의 그래프의 상태는 다음과 같다.

해당 상태에서 4번째 간선을 순회하는 경우, 간선을 통해 연결되어 있는 노드 1과 노드 2의 부모 노드는 둘 다 노드 0이기 때문에 해당 간선을 연결하면 그래프에 순환이 발생하게 되므로 해당 간선을 연결하지 않는다.

해당 과정을 모든 간선마다 수행한 뒤 만들어지는 최종 그래프는 최소 신장 트리가 된다.

💡 시간 복잡도

간선의 갯수가 E , 노드의 갯수가 V 일 때의 시간 복잡도는 O(E log V) 이다.

💡 구현 코드

#include <vector>
#include <tuple>
#include <iostream>

using namespace std;

vector<int> parents;

//주어진 노드의 최상위 부모 노드를 찾는 함수
int FindParent(int node)
{
	//해당 노드의 부모가 자기 자신인 경우, 해당 노드가 최상위 부모 노드라는 뜻
	if (node == parents[node])
	{
		return node;
	}

	return FindParent(parents[node]);
}

//노드의 갯수와 간선들을 매개변수로 받아 그래프를 만들고, 해당 그래프의 최소 비용을 반환하는 함수
int Kruskal(int nodes, vector<tuple<int, int, int>>& edges)
{
	int cost = 0;

	//부모 노드 초기값 설정
	parents.resize(nodes);
	for (int i = 0;i < parents.size();i++)
	{
		parents[i] = i;
	}

	for (tuple<int, int, int> edge : edges)
	{
		//간선을 연결했을 때 순환이 발생하는지 체크
		int parentA = FindParent(get<0>(edge));
		int parentB = FindParent(get<1>(edge));

		if (parentA == parentB)
		{
			continue;
		}

		//순환이 발생하지 않는 경우, 간선이 연결되므로 해당 간선의 가중치 값을 비용에 더함
		cost += get<2>(edge);

		//구한 두 노드의 부모 중 인덱스 값이 더 작은 부모 노드로 갱신
		if (parentA < parentB)
		{
			parents[parentB] = parentA;
		}
		else
		{
			parents[parentA] = parentB;
		}
	}

	return cost;
}

int main()
{
	//간선 정보 삽입
	vector<tuple<int, int, int>> edges;
	edges.push_back({ 0, 1, 1 });
	edges.push_back({ 0, 2, 2 });
	edges.push_back({ 1, 2, 5 });
	edges.push_back({ 1, 3, 1 });
	edges.push_back({ 2, 3, 8 });

	cout << Kruskal(4, edges);
}

---

Reference

크러스컬 알고리즘 - 위키백과
[알고리즘] Kruskal 알고리즘 이란
[그래프 알고리즘] 크루스칼 알고리즘 Kruskal Algorithm
[Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘