[ 알고리즘 ]최소 비용 신장 트리(MST, Minimum Spanning Tree)

코딩테스트(C++)/자료구조, 알고리즘

[ 알고리즘 ]최소 비용 신장 트리(MST, Minimum Spanning Tree)

후르트링 2021. 10. 25. 17:18

728x90

[ 신장트리(Spanning Tree) ]

주어진 방향성이 없는 그래프의 서브 그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리
사이클이 존재하지 않습니다.

[ MST ]

그래프의 신장 트리 중에서 간선들의 가중치 합이 최소인 신장트리를 MST(최소 비용 신장 트리,Minimum Spanning Tree)라고 합니다.

간선들의 가중치의 합이 최소
V개의 정점 그래프는 V-1개의 간선
사이클 존재 X

총 3가지의 특징을 가지고 있어야 합니다.

최소 비용 신장트리를 찾는 방법은 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 대표적입니다.

두 가지 모두 그리디 방식으로 구현합니다.

최소 비용 신장 트리는 통신 네트워크 구축, 배관 파이프 건설 등에서 사용될 수 있습니다.

[ 크루스칼(Kruskal) ]

간선 기반의 알고리즘 입니다.
시간 복잡도 O(ElgE), 간선을 정렬하는 시간에 비례합니다.
알고리즘 과정

간선의 크기를 오름차순으로 정렬. 제일 낮은 비용 간선을 선택합니다.
현재 선택한 간선의 정점 u,v가 다른 그룹이면 같은 그룹으로 만들고, 현재 선택한 간선을 최소 신장 트리에 추가합니다. ※같은 그룹인지 판별하는 것과 그룹을 합치는 것은 Union-find 알고리즘을 사용합니다.
최소 신장 트리에 V-1개의 간선이 있다면 종료합니다.

//cost, v1, v2
vector<pair<int, pair<int, int> >> edge;

for (int i = 0; i < e; i++) {
    cost = edge[i].first;
    v1 = edge[i].second.first;
    v2 = edge[i].second.second;
    if (!unionFind(v1, v2)) continue;
    ans += cost;
    cnt++;
    if (cnt == v - 1) break;
}

[ Union - find ]

Union( x, y ) : 집합을 합치는 함수
find(x) : 원소 x가 속한 집합을 반환

각 노드의 부모에 대한 포인터를 저장합니다.

//부모 index 값을 저장한다. 처음에 -1로 초기화.
int p[100001];

//최고 부모를 찾는 함수
int find(int x) {
    if (p[x] ==-1) return x;
    return p[x] = find(p[x]);
}

bool unionFind(int v1, int v2) {
    int root1 = find(v1); 
    int root2 = find(v2);
    if (root1 == root2) return false;        //같은 집합에 속한다.
    p[root1] = root2;                    //다른 집합에 속하면 집합을 합쳐준다.
    return true;
}

[ 프림(Prim) ]

정점 기반의 알고리즘입니다. 한 정점에서 시작해 확장하는 알고리즘입니다.
시간 복잡도 O(ElgE)
알고리즘 과정
1. 하나의 정점을 선택해 최소 신장트리에 추가합니다.
2. 신장트리 집합에 인접한 최소 신장트리에 포함되지 않은 정점들 중에 최저 간선으로 연결된 정점을 선택하여 트리를 확장합니다.
3. 최소 신장 트리에 V-1 개 간선이 생기면 종료합니다.

Heap을 이용한 Prim 알고리즘 구현
1. 하나의 정점을 MST에 추가하고 해당 정점과 연결된 모든 간선을 Heap에 추가
2. Heap에서 비용이 가장 작은 간선을 꺼낸다.
3. -1 해당 간선이 MST에 포함된 두 정점을 연결하면 Continue;
4. -2 해당 간선이 MST에 포함된 정점 u와 포함되지 않는 정점 v를 연결하면 해당 간선과 정점 v를 MST에 추가,
5. 정점 v에서 연결된 모든 간선 중 MST에 포함되지 않는 간선을 힙에 추가
6. 최소 신장트리의 간선이 V-1개 이면 종료합니다.