[알고리즘] 크루스칼(Kruskal)과 최소 신장 트리(MST, Minimum Spanning Tree)

[신장 트리(Spanning Tree)]

 

크루스칼 알고리즘에 대해 알아보기 전에 신장 트리를 먼저 알아보도록 하겠습니다. 신장 트리란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 뜻합니다. 

 

위와 같은 그래프가 존재할 경우, 간선을 초록색, 보라색으로 나누면 신장 트리가 만들어집니다. 그래프 내에 신장 트리는 여러 개 존재할 수 있습니다.

 

 

[최소 신장 트리(Minimum Spanning Tree)]

 

간선에는 가중치(Weight)가 존재합니다. 최소 신장 트리(MST)는 신장 트리들 중, 간선들의 가중치 합이 최소가 되는 신장 트리를 뜻합니다.

 

보라색 간선으로 이루어지는 신장 트리와 초록색 간선으로 이루어지는 신장 트리들의 가중치 합은 각각 10(2+2+3+3), 11(1+1+4+5)입니다. 그렇다면 최소 신장 트리는 가중치의 합이 10인 보라색 간선 신장 트리가 됩니다.

 

 

[크루스칼 알고리즘(Kruskal Algorithm)]

 

그렇다면 그래프에서 최소 신장 트리는 어떻게 찾을까요? 여기서 크루스칼 알고리즘을 사용할 수 있습니다. 크루스칼 알고리즘은 간선들을 이용해서 모든 노드를 연결하되, 전체 비용이 최소가 되도록 선택하는 방법을 제공해줍니다. 알고리즘 절차는 다음과 같습니다.

1. 모든 간선을 가중치(비용) 기준으로 오름차순 정렬
2. 정렬된 간선을 하나씩 확인
	2-1. 두 정점이 아직 연결되지 않았다면 → 선택
	2-2. 이미 연결되어 있다면(사이클 발생) → 무시
3. 모든 정점이 연결되면 종료

 

여기서 두 정점이 연결되어 있는지 확인하는 방법으로 Union-Find(서로소 집합) 자료구조를 활용합니다.

Find(x) : x가 속한 그룹(대표 노드) 검색
Union(x, y) : 두 그룹 합치기

 

 

위에서 살펴봤던 그래프를 기준으로 크루스칼이 어떻게 진행되는지 확인해보겠습니다.

// 간선 목록(오름차순 정렬)
1: (1–3), (3–5)
2: (1–5), (4–5)
3: (2–3), (2–4)
4: (1–2)
5: (3–4)

// 초기 집합 : {1}, {2}, {3}, {4}, {5}
parent[1] = 1
parent[2] = 2
parent[3] = 3
parent[4] = 4
parent[5] = 5

 

간선을 하나씩 살펴보면서 Union-Find로 사이클을 체크합니다.

 

> 1단계

: [1-3] 간선은 가중치가 1입니다. find(1)과 find(3)을 실행하면 서로 다른 집합으로 판단되기 때문에, Union(1, 3)을 통해 3의 대표를 1로 설정합니다(노드를 오름차순으로 정렬하기).

// 집합 : {1, 3} {2} {4} {5}
parent[1] = 1
parent[2] = 2
parent[3] = 1 // << 변경
parent[4] = 4
parent[5] = 5

 

> 2단계

: [3-5] 간선은 가중치가 1입니다. find(3)은 parent[3] = 1로, 1이 나옵니다. find(5)는 5가 나오기 때문에 서로 다른 집합으로 판단하여, Union(3, 5)를 통해 5의 대표를 1로 설정해줍니다.

// 집합 : {1, 3, 5} {2} {4}
parent[1] = 1
parent[2] = 2
parent[3] = 1
parent[4] = 4
parent[5] = 1 // << 변경

 

> 3단계

: [1-5] 간선은 가중치가 2입니다. find(1)은 1이고, find(5)는 1이 나타나기 때문에, 이미 같은 집합 내에 있어 추가 시 사이클이 발생하게 됩니다. 해당 노드 간의 Union은 실시해주지 않습니다.

 

> 4단계

: [4-5] 간선은 가중치가 2입니다. find시 4와 5는 각각 4, 1이 나오기 때문에 다른 집합으로 판단되어 Union(4, 5)를 실시합니다. 이때 집합이 변경됩니다.

// 집합 : {1, 3, 4, 5} {2}
parent[1] = 1
parent[2] = 2
parent[3] = 1
parent[4] = 1 // << 변경
parent[5] = 1

 

> 5단계

: [2-3] 간선은 가중치가 3입니다. find시 2와 3은 각각 2, 1이 나오기 때문에 다른 집합으로 판단되어 Union(2, 3)을 실시합니다.

// 집합 : {1, 2, 3, 4, 5}
parent[1] = 1
parent[2] = 1
parent[3] = 1
parent[4] = 1
parent[5] = 1

 

여기까지 진행할 경우, 모든 노드가 하나의 집합으로 이루어지게 되며 가중치를 오름차순으로 하여 알고리즘을 수행했기 때문에 비용이 7로 작업이 마무리됩니다.

 

 

[코드로 알아보기]

 

크루스칼 알고리즘에 대한 문제도 다익스트라 문제와 마찬가지로 백준에 존재합니다.

https://www.acmicpc.net/problem/1197

 

아래는 문제에 대한 풀이 소스 코드입니다.

// 백준 [골드4] [1197] [최소 스패닝 트리]
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct Edge
{
	int From = 0;
	int To = 0;
	int Weight = 0;
};

vector<Edge> Graph;
vector<int> Parent;

bool Compare(const Edge& _Left, const Edge& _Right)
{
	if (_Left.Weight != _Right.Weight) // 가중치가 같지 않은 경우, 가중치 오름차순 정렬
	{
		return _Left.Weight < _Right.Weight;
	}

	return _Left.To < _Right.To; // 가중치가 같은 경우에는 노드 번호 오름차순 정렬
}

int Find_Parent(int _Value) // Parent 반환하기
{
	if (Parent[_Value] != _Value)
	{
		Parent[_Value] = Find_Parent(Parent[_Value]);
	}

	return Parent[_Value];
}

void Union_Parent(int _From, int _To) // 합치기
{
	_From = Find_Parent(_From);
	_To = Find_Parent(_To);

	if (_From > _To)
	{
		Parent[_From] = _To;
	}
	else
	{
		Parent[_To] = _From;
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N = 0, M = 0; // N: 정점 수(1~N), M: 간선 수
    cin >> N >> M;

    Graph.resize(M);
    for (int i = 0; i < M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        Graph[i] = { u, v, w };
    }

    // 가중치 오름차순 정렬
    sort(Graph.begin(), Graph.end(), Compare);

    Parent.resize(N + 1);
    for (int i = 1; i <= N; i++)
    {
        Parent[i] = i;
    }

    long long Result = 0;
    int Picked = 0;
    for (const auto& Edge : Graph)
    {
    	int From = Edge.From;
        int To = Edge.To;
        int Weight = Edge.Weight;
        int From_Parent = Parent[From];
        int To_Parent = Parent[To];
    
		if (Find_Parent(From_Parent) != Find_Parent(To_Parent))
		{
			Union_Parent(From_Parent, To_Parent);
			Result += Weight;
            ++Picked;
            if (Picked == N - 1) // MST 완성되면 조기 종료
            {
                break;
            }
		}
    }

    cout << Result;
    
    return 0;
}