MST(Minimum Spanning Tree) Kruskal Algorithm

 

 

MST 는 Minimum Spanning Tree (최소신장트리)의 약자로 가중치가 있는 그래프에서 모든 가중치의 합이 최소가 되도록 하는 어떤 트리(정점이 $V$개일 때 간선이 $V-1$ 인 연결그래프)를 의미한다. 예를 들어서 아래의 그래프에서는 찐하게 칠해진 트리가 가능한 모든 트리 중에서 가중치의 합이 최소이므로 MST 가 된다.

출처 : Wikipidia; Minimum Spanning Tree

 

주어진 그래프에서 MST 를 구하는 알고리즘은 대표적으로 $Prim's\space Algorithm$ 과 $Kruskal\space Algorithm$ 이 있다. $Kruskal\space Algorithm$ 에 대해 알아보자.

 

1) $Kruskal\space Algorithm$  의 동작

 Kruskal 알고리즘은 다음과 같이 동작한다.

1) 모든 간선을 가중치를 기준하여 오름차순으로 정렬한다.
2) 가중치가 낮은 간선 순서대로 선택을 하는데 기존에 선택한 간선들과 cycle을 이룬다면 선택하지 않는다.

 

2) $Kruskal\space Algorithm$  의 구현

 Kruskal 알고리즘은 union find를 이용하면 쉽게 구현할 수 있다. 

 

 기존 그래프에서 $A$랑 $B$를 잇는 간선을 추가하는 것은 Union알고리즘을 이용하면 구현할 수 있고, 간선을 이었을 때 $cycle$이 생기는 지를 판단하려면 이전에 $A$와 $B$를 잇는 경로가 존재했는지를 알면 된다. 이는 Find알고리즘을 이용하면 된다.

//Union-Find
int getParent(int parent[],int x)
{
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent,parent[x]);
}
void unionParent(int parent[], int x, int y)
{
    x = getParent(parent, x);
    y = getParent(parent, y);
    if(x>y) parent[x] = y;
    else parent[y] = x;
}
int findParent(int parent[], int x, int y)
{
    x = getParent(parent, x);
    y = getParent(parent, y);
    if(x==y)return true;
    return false;
}

 

백준 1197번 최소 스패닝 트리 :  https://www.acmicpc.net/problem/1197

 

백준 1197번을 기준으로 설명해보면 먼저 $graph$를 받아야한다.

vector<pair<int,pair<int,int>>> graph;
int V,E;
cin>>V>>E;
for(int i=0;i<E;i++)
{
    int u,v,w;
    cin>>u>>v>>w;
    graph.push_back({w,{v,u}});
}

 가중치를 기준으로 오름차순 정렬해야하므로 $w$를 가장 앞에 저장해주었다.

sort(graph.begin(),graph.end());

 

이제 kruskal 알고리즘이 동작하는 그대로 코딩을 해주면 된다.

for(int i=0;i<graph.size();i++)
{
    int w = graph[i].first;
    int v = graph[i].second.first;
    int u = graph[i].second.second;
    if(findParent(parent,v,u))continue;
    unionParent(parent,v,u);
    W += w;
}

 여기서 $W$는 $MST$의 모든 가중치의 합을 의미한다.

 

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int VMAX = 10000;
vector<pair<int,pair<int,int>>> graph;
int V,E,parent[VMAX+1],W;
int getParent(int parent[],int x)
{
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent,parent[x]);
}
void unionParent(int parent[], int x, int y)
{
    x = getParent(parent, x);
    y = getParent(parent, y);
    if(x>y) parent[x] = y;
    else parent[y] = x;
}
int findParent(int parent[], int x, int y)
{
    x = getParent(parent, x);
    y = getParent(parent, y);
    if(x==y)return true;
    return false;
}
void init(){
    for(int i=1;i<=V;i++) parent[i] = i;
    W = 0;
}
void input(){
    cin>>V>>E;
    for(int i=0;i<E;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        graph.push_back({w,{v,u}});
    }
    sort(graph.begin(),graph.end());
}
void Kruskal(){
    for(int i=0;i<graph.size();i++)
    {
        int w = graph[i].first;
        int v = graph[i].second.first;
        int u = graph[i].second.second;
        if(findParent(parent,v,u))continue;
        unionParent(parent,v,u);
        W += w;
    }
}
void output(){
    cout<<W;
}
int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    input();
    init();
    Kruskal();
    output();
}