본문 바로가기
Competitive Programming 3rd(Uva Judge)

최소 스패닝 트리(MST, Minimum Spanning Tree)

by Haeine 2018. 1. 26.

최소 스패닝 트리(MST)


  스패닝 트리란 그래프에 모든정점을 연결하는 트리이다. 스패닝 트리 중, 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 스패닝 트리가 최소 스패닝 트리가 된다. 정점의 갯수가 V개인 그래프의 최소 스패닝 트리는 V - 1개의 간선을 갖는다. 최소 스패닝 트리를 구하는 알고리즘은 크루스칼 알고리즘, 프림 알고리즘이 있다. 두 알고리즘에 대해서 설명할 것이다.



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


  크루스칼 알고리즘은 첫번째로 그래프의 간선 리스트를 구성한다. 간선 리스트를 간선의 가중치를 기준으로 오름 차순으로 정렬하고 가중치가 가장 작은 간선부터 스패닝 트리에 해당되는 간선에 추가한다. 이때 사이클이 발생하는 간선은 추가 하지 않고 무시한다. 사이클의 여부는 UnionFind DisjointSet(유니온 파인드 상호배타적 집합)를 이용하여 O(1)에 확인한다. 해당 알고리즘을 통해 스패닝 트리중 간선의 가중치가 최소가 되는 합을 구할 수 있다.



Kruskal Algorithm's Code


typedef pair<int, int> ii;

vector<pair<int, ii> > EdgeList;    //<가중치, 간선정보>


int main() {

//EdgeList에 간선을 추가한다.

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

UnionFind UF(V);    //각 정점을 상호 배타적인 집합으로 선언

int mst_cost = 0;

for(int i = 0; i < E; ++i) {

if(!UF.isSameSet(EdgeList[i].second.first, EdgeList[i].second.second)){

mst_cost += EdgeList[i].first;

UF.unionSet(EdgeList[i].second.first, EdgeList[i].second.second);

}

}

printf("Sum of edge's load included MST is %d\n" mst_cost);

}



Time Complexity of the Kruskal Algorithm


  해당 알고리즘은 간선을 정렬하는데 O(ElogE)의 시간복잡도가 소요된다. 그리고 정렬된 간선을 순회하며 UnionFind연산을 한번씩 수행한다. 이에 O(1) * E 즉, O(E)의 시간복잡도가 발생한다. 결과적으로 O(ElogE + E)이다. 이는 O(ElogE) = O(ElogV^2) = O(2*ElogV) = O(ElogV)가 된다. 최종 시간복잡도는 O(ElogV)이다.



프림 알고리즘(Prim Algorithm)


  MST를 구하는 또 하나의 알고리즘이다. 우선 첫번째 임의의 시작점을 설정한다. 시작점으로 부터 인접한 정점을 Priority Queue(pq)에 저장하는데 이때 해당 정점과 시작점 사이 간선의 가중치를 같이 저장한다. 흔히 그래프를 표현하는 방식인 인접 리스트를 사용하면 이러한 저장 방식은 직관적 이다. 즉 pq에는 vector<ii>가 저정된다. 

(typedef pair<int, int> ii;)    //간선의 가중치, 인접한 정점번호

pq에 저장된 정점과 가중치 쌍은 가중치의 오름차순으로 정렬되고 가중치가 같으면 정점 번호의 오름차순으로 정렬된다. 이때 pq에 저장되는 정점은 아직 스패닝 트리를 구성하는데 있어서 포함되지 않은 정점이다. 이는 스패닝 트리에 사이클이 생기는 것을 방지한다. 시작점과 인접한 정정을 pq에 삽입하는 작업이 끝나면 pq가 빌때까지 아래작업을 반복한다.

1. pq.top()의 값을 추출하고 pq에서 제거한다.

2. 추출된 것은 정점번호와 가중치이다. 즉 가중치가 가장 작으면서 정점 번호가 가장 빠른 정점이 추출된 것이다.

3. 해당 정점이 구성중인 스패닝 트리에 포함되어 있지 않다면 해당 정점의 가중치를 결과값에 더하고 해당정점에 방문 했다고 표시해둔다.(사이클이 발생하지 않게 하기 위하여)

4. 해당 정점과 인접한 정점중 아직 스패닝 트리에 고려되지 않은 정점들을 pq에 삽입한다.(사이클 방지)

pq가 비고 반복문이 종료되고 나면 MST의 간선 가중치 합은 구해져 있다.



Prim Algorithm's Code


typedef pair<int, int> ii;

typedef vector<int> vi;

vi taken;

priority_queue<ii> pq;


void process (int vtx) {

taken[vtx] = 1;

for(int i = 0 ; i < (int)AdjList[vtx].size(); ++i) {

ii v = AdjList[vtx][i];

if(!taken[v.first])    pq.push(ii(-v.second, -v.first));

//pq는 기본적으로 최대힙이므로 오름차순 정렬을 위해

//부호 역전

}    }

int main() {

//해당 정점이 MST구성에 사용 되었는지 여부를 저장

taken.assign(V, 0);

//시작점을 설정하고 시작점과 인접한 정점, 가중치 쌍을 pq에 삽입

process(0);

int mst_cost = 0;

while(!pq.empty()) {

//pq에서 가중치가 가장 작고 번호가 빠른

ii front = pq.top();    pq.pop();

int w = -front.first, u = -front.second;

if(!taken[u]){

mst_cost += w;

process(u);

}

}

printf("MST value: %d\n", mst_cost);

}



Time Complexity of The Prim Algorithm


  해당 알고리즘은 각 간선이 한번씩 pq에 삽입되고 제거된다. 이에 해당하는 시간복잡도는 O(ElogE)이다. 결과적으로 크루스칼 알고리즘과 같은 O(ElogV)가 최종 시간복잡도가 된다. 




PS. 위에서 설명한 두 알고리즘 모두 그리디한 알고리즘이다. 두 알고리즘의 차이는 간선의 리스트를 만들고 이를 정렬하여 가장 낮은 가중치의 간선부터 방문하는지(kruskal) 아니면 우선순위 큐를 활용하여 임의의 시작점으로 부터 연결되는 가장 가중치가 낮은 간선부터 방문 하는지(Prim)의 차이가 있다.