MST(Minimum Spanning Tree) 최소 신장 트리

신장 트리 (Spanning Tree)

    - 그래프 내의 모든 정점을 연결하는 트리

    - 사이클은 없음

    - N개의 정점과 N-1개의 간선

 

    - 왼쪽 그래프는 오른쪽의 총 8개의 신장 트리를 가짐

https://ko.wikipedia.org/wiki/%EC%8B%A0%EC%9E%A5_%EB%B6%80%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

 

 

 

최소 신장 트리 (Minimum Spanning Tree)

    - 신장 트리 중에서 간선들의 가중치 합이 최소인 트리

 

    - 아래 그래프에서 굵은 간선으로 이루어진 트리가 최소 신장 트리

https://ko.wikipedia.org/wiki/%EC%8B%A0%EC%9E%A5_%EB%B6%80%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

 

 

 

 

최소 신장 트리 알고리즘

    - 최소 신장 트리를 찾을 수 있는 알고리즘

 

1) 크루스칼 알고리즘 (Kruskal's algorithm)

    - 탐욕적인 방법을 이용하여 모든 정점을 최소 비용으로 연결하는 방법

    - 간선 선택 기반

 

    - 동작

        * 간선들을 가중치 오름차순으로 정렬

        * 가중치가 작은 간선을 순서대로 선택하여 사이클을 이루는지 확인

        * 사이클을 형성하지 않으면, 최소 신장 트리 집합에 추가

 

        * 예시

            + 붉은 색 선은 최소 신장 트리의 간선

            + 검은 색 선은 사이클을 형성하기 때문에 선택하지 않은 간선

 

 

    - 구현

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
int parents[7];
vector<pair<pair<int, int>, int> > edges;
 
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    return a.second < b.second;
}
 
int getParent(int x){
    if(parents[x] == x) return x;
    return parents[x] = getParent(parents[x]);
}
 
void union_parents(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(b > a) parents[b] = a;
    else parents[a] = b;
}
 
void kruskal(){
    
    sort(edges.begin(), edges.end(), cmp);
    
    for(int i=1; i<=n; i++) parents[i] = i;
    
    int sum = 0;
    for(int i=0; i<edges.size(); i++){
        if(getParent(edges[i].first.first) != getParent(edges[i].first.second)){
            sum += edges[i].second;
            union_parents(edges[i].first.first, edges[i].first.second);
        }
    }
    
    cout << sum << endl;
}
 
int main(void){
    
    n = 6;
    m = 10;
    
    edges.push_back({{1,2}, 3});
    edges.push_back({{1,3}, 5});
    edges.push_back({{2,5}, 1});
    edges.push_back({{2,4}, 11});
    edges.push_back({{2,6}, 7});
    edges.push_back({{3,4}, 12});
    edges.push_back({{3,5}, 23});
    edges.push_back({{4,5}, 10});
    edges.push_back({{4,6}, 6});
    edges.push_back({{5,6}, 17});
    
    kruskal();
    
} 

 

    - 사이클 여부 확인 방법 : Union-Find 알고리즘

        * 두 정점의 부모 노드가 같다면 사이클

 

    - 시간복잡도

        + 정렬 단계(가장 빠른 퀵 정렬) 시간복잡도 : O(ElogE)

        + Union-Find 시간복잡도 : O(logE)

        + 크루스칼 알고리즘의 시간복잡도는 정렬 단계에 의해 결정되기 때문에 O(ElogE)

 

    - 사용

        + 간선의 개수에 의해 시간이 결정되기 때문에 간선이 적은 희소 그래프에서 사용하기 적합

 

 

 

2) 프림 알고리즘(Prim algorithm)

    - 시작 정점에서 출발하여 인접한 정점으로 단계적으로 확장해 나가는 방법

    - 정점 선택 기반

 

    - 동작

        * 시작 정점을 집합에  MST 집합에 포함

        * MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점 선택

        * MST 집합에 선택한 정점이 없으면 포함

        * MST 집합이 N-1개의 간선을 가질 때까지 반복

 

        * 예시

 

 

    - 시간복잡도

        + 모든 정점을 순회하기 때문에 시간복잡도는 O(n^2)

 

    - 사용

        + 정점 개수에 의해서 시간이 결정되기 때문에 정점에 비해 간선이 많은 밀집 그래프에서 적합

 

참조

    - 블로그 1  

    - 블로그 2

    - 블로그 3

    - 위키피디아