알고리즘 & 자료구조 복기글 (4) - 최소 스패닝 트리

이번에는 최소 스패닝 트리 (Minimum Spanning Tree 약칭 MST)에 대해 이야기 해보려고 한다.

MST란?

최소 스패닝 트리로 스패닝 트리 중 간선의 가중치의 합이 최소인 트리이다. 그럼 스패닝 트리는 무엇일까? 그래프에 n개의 정점이 있을때 n-1개의 간선으로 모든 점을 이은 트리이다. 사이클이 존재하지 않으며, 임의의 두 정점에 대해서 이동할 수 있는 경로가 유일하다. 
다시 말하자면 그래프에서 n-1개의 간선을 뽑아내 사이클이 없는 트리를 완성하고 이때의 간선의 가중치의 합이 최소이면 이를 최소 스패닝 트리, 즉 MST라고 한다.

MST를 구하는 방법

그래프에서 MST를 구하는 방법에는 크게 두가지가 있다. 바로 크루스칼 알고리즘과 프림 알고리즘이다. 둘 다 그리디를 기반으로 하고 있으며, 둘 중에 대중적인 것은 크루스칼 알고리즘이다. 크루스칼 알고리즘만 알고 있어도 MST를 구하는 데에 아무런 문제가 없기 때문에 크루스칼 알고리즘에 대해서만 이야기 하려고 한다.

Kruskal 알고리즘의 개요

그래프에 간선들이 있을 것이다. 이 중 가중치가 가장 작은 간선부터 보며 두 가지 중 한 가지 행동을 한다. 만약 그 간선이 현재의 MST 그룹에 추가되었을 때 사이클을 이루지 않는다면 MST 그룹에 추가한다. 그렇지 않다면 추가하지 않는다.
이것이 끝이다. 매우 간단하며 이 것이 크루스칼 알고리즘이 많이 사랑받는 이유이다. 그럼 아래의 예시를 통해 추가적인 이야기를 풀어나가려고 한다. 

왼쪽과 같은 그래프가 있다고 하자. 이 때 가장 작은 가중치의 간선은 1이기 때문에 (A,C)를 잇는 간선을  MST 그룹에 추가한다.

마찬가지로 그 다음으로 가중치가 작은 간선인 (B,E),(B,C) 를 MST 그룹에 추가한다. 

그 다름으로 가중치가 간선은 (C,E)이지만, 이 간선을 추가한다면 사이클이 생기기 때문에 포기하고, 다음 간선을 본다.

위의 두 간선은 모두 MST 그룹에 추가하면 사이클이 생기는 간선들이기 때문에 추가를 할 수 없다. 

왼쪽 과정을 마치면 n-1개의 간선이 모두 나오기 때문에 바로 종료를 해도 되고, 아니면 나머지 간선들에 대해 사이클이 생긴다는 것을 확인하면 된다. 

아무튼 간선을 계속 확인하면서 사이클이 생기는지를 판단하고 그렇지 않으면 그룹에 추가하는 일련의 과정을 통해 위와 같은 Spanning Tree를 얻을 수 있다. 이 Spanning Tree는 Minimum Spanning Tree임이 증명되어있다.

Kruskal Algorithm 과 Union & Find 

위의 과정에서 우리는 계속해서 사이클이 생기는지 안 생기는지에 대한 것을 판단해야한다. 이때 필요한 개념이 Union & Find 이다. 이 개념과 코딩과정에 대한 설명은 이글 에 나와있다. 간선을 추가할 때 마다 두 노드를 Union 해주고, 어떤 간선에 대해 양 끝점이 같은 그룹이면 그 간선은 사이클을 만드는 간선이다. 따라서 log 스케일에 한번의 작업을 완료할 수 있다. 
따라서 총 시간복잡도는 그래프의 간선의 수 E에 대해서 O(ElogE) 이다.

코드

보통의 MST 문제는 가중치의 합을 구하는 경우가 많고 아래의 코드도 그러하다.

 

#include<bits/stdc++.h>
using namespace std;
 
const int maxn=1e5+5;
const int maxm=1e6+5;
 
struct node{
    int u,v,c;
}edg[maxm];
 
bool sf(node a, node b)
{
    return a.c<b.c;
}
 
int n,m;
int parent[maxn];
int num[maxn];
 
int uf(int a)
{
   if(parent[a]==a) return a;
   if(parent[a]==0)
   {
       parent[a]=a;
       return a;
   }
   parent[a]=uf(parent[a]);
   return parent[a];
}
 
bool mergee(int a, int b)
{
   a=uf(a);
   b=uf(b);
   if(a==b)
   {
       return false;
   }
   if(num[a]>num[b])
       parent[b]=a;
   else if(num[b]>num[a])
       parent[a]=b;
  
   if(num[a]==num[b]){
       num[b]++;
       parent[a]=b;
   }
   return true;
}
 
int main()
{
   int i,j,k;
   scanf("%d %d",&n,&m);
   for(i=1;i<=m;i++)
   {
       scanf("%d %d %d",&edg[i].u,&edg[i].v,&edg[i].c);
   }
   sort(edg+1,edg+m+1,sf);
  
   long long ans=0;
   for(i=1;i<=n;i++)
   {
       parent[i]=i;
       num[i]=0;
   }
  
   for(i=1;i<=m;i++)
   {
       int u=edg[i].u;
       int v=edg[i].v;
       if(uf(u)==uf(v)) continue;
       mergee(u,v);
       ans+=edg[i].c;
   }
  
   printf("%lld",ans);
}
 

추천 문제들

BOJ 1197 최소 스패닝 트리
BOJ 1922 네트워크 연결
BOJ 6497 전력난
BOJ 2887 행성터널
BOJ 1647 도시 분할 계획
BOJ 2211 네트워크 복구