그래프 알고리즘(MST, 크루스칼, 프림)

작성일 | In

그리디 알고리즘 - 최소 신장 트리

최소신장 트리에서 크루스칼과 프림을 알아보자

MST(최소 신장 트리)

정점(vertex)의 집합 V와 가중치를 갖는 에지(edge)의 집합 E로 구성된 그래프 G = <V,E>가 주어질때,

모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리

  • 사이클X
  • 예를 들어 상수도관 네트워크 설계의 경우 모든 사람에게 수돗물이 전달되어야 하고 전체 상수도관의 길이는 최소가 되는 것이 좋다.

최소 신장 트리 T를 구하는 그리디 알고리즘

  1. 그래프 G의 모든 에지를 최소 힙 H에 추가합니다
  2. H로부터 에지 e를 하나 꺼냅니다.(모든 에지중에서 가장 가중치가 작은 에지)
  3. e의 양 끝 정점이 이미 T에 있을경우, e로 인해 T에서 사이클이 발생할 수 있다, 그러므로 이런경우 e를 버리고 2단계로 이동
  4. 최소 신장 트리 T에 e를 추가하고 2단계로 이동

⇒ 2단계부터 4단계까지를 반복하면서 가장 작은 가중치의 에지를 찾고, 이 에지에 의해 사이클이 발생하지 않으면 해당 에지와 양 끝 정점을 최종 솔루션에 추가한다.

크루스칼 MST 알고리즘 구현 방법

3단계가 좀 복잡 : 그래프 에지 정보를 저장할 자료 구조가 필요하고, 새로운 에지를 추가할 때 사이클이 발생하는지를 판단하는 기능이 필요

이 문제는 디스조인트-셋 자료구조로 해결 가능

디스조인트-셋 자료 구조 (union-find)

  • 디스조인트-셋 또는 유니온-파인드 자료구조는 트리 형태의 원소로 구성된 포레스트(트리들의 집합)이다.
  • 각각의 원소는 1. 숫자 ID에 의해 표현되며, 2. 랭크(rank)와 부모에 대한 포인터를 가진다.
  • 이 자료구조가 초기화 되면 랭크가 0인 N개의 독립적인 원소가 생성됨, 각각의 원소는 하나의 트리를 나타냄

이 자료구조가 지원하는 연산

  • make-set(x) : x를 ID로 갖는 원소를 유니온-파인드 자료구조에 추가한다.
    • 처음 추가하면 그 원소의 랭크는 0
    • 원소의 부모 포인터는 자기 자신

    Untitled

    i는 노드 번호 p[i]는 부모 노드 번호

  • find(x) : 원소 x에서 시작해서 부모 포인터를 따라 반복적으로 이동하여 트리의 루트를 반환한다.
  • union(x, y)
    1. 두 개의 원소 x와 y에 대해 union()연산을 수행하면 x와 y의 루트를 찾는다.
    2. 만약 두 루트가 같다면 x와 y가 같은 트리에 속해 있음을 의미 ⇒ 아무런 작업X

    3. 만약 두 루트가 다르다면 높은 랭크 루트를 낮은 랭크 루트의 부모로 설정

      1
      2
      3
      4
      5
       if(nodes[root_x].rank > nodes[root_y].rank){
 	swap(root_x,root_y); //nodes[root_y].parent = nodes[root_x].parent; 같은 의미
 }
        
 nodes[root_x].parent = nodes[root_y].parent;

    계속 연산을 거듭할수록 더 많은 트리가 병합되어 전체 트리 개수는 줄어들고, 대신 각 트리의 크기는 점점 거대해짐

다시 돌아와서 이 유니온-파인드 자료구조를 사용하여 크루스칼 MST 알고리즘을 구현해보자

  1. 그래프 정점 개수가 N이라면, 먼저 N개의 원소를 갖는 디스조인트-셋 자료 구조를 초기화
  2. 사이클 발생 여부를 판단(MST 3단계)해야 한다고 했는데 union(x,y)연산을 활용
    • 두 트리를 병합하여 MST 4단계 수행
    • x와 y의 루트가 같다는 것은 사이클이 발생한다는 뜻 ⇒ 그래서 union연산 종료
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//최대 가중치로 연결 되어있는 도시를 빼면 됨
int N, M;
vector<pair<int,pair<int,int>>> edges; //<가중치,<정점,정점>>
int parent[100001];

int find(int x){
    if(x==parent[x])
        return x;
    return parent[x]=find(parent[x]);
}
void Union(int x,int y){
    int px = find(x);
    int py = find(y);
    if(px==py)
        return;
    else{
        parent[y] = px;
    }
}
int main(){
    cin>>N>>M;
    int a,b,c;
    //1. 최소 힙에 추가
    for (int i = 0; i < M; i++) {
        cin>>a>>b>>c;
        edges.push_back({c,{a,b}});
    }

    //가중치를 오름차순으로 정렬
    sort(edges.begin(),edges.end());

    //2. 유니온 파인드 자료 구조 시작
    //make-set
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
    int maxCost=0;
    int result=0;
    //union-find
    for (auto & edge : edges) {
        int cost = edge.first;
        int x = edge.second.first;
        int y = edge.second.second;

        if(find(x) != find(y)) {
            maxCost = max(maxCost, cost);
            result += cost;
            Union(x,y);
        }
    }

    cout<<result-maxCost;
    return 0;
}

프림 MST 알고리즘

프림 알고리즘은 BFS의 동작 방식과 유사

  1. 시작 정점을 이용하여 경계를 구성
  2. 현재 경계에 인접한 정점을 반복적으로 탐색, 그중 가중치가 가장 작은 에지를 선택하고, 이 에지에 연결된 정점을 방문

각 정점에 경계로부터의 거리 정보를 기록해야 함

  1. 모든 정점의 거리 값을 무한대로 초기화, 시작정점은 자기 자신까지의 거리는 0이므로 시작정점의 거리값은0 그리고 모든 거리값을 최소 힙 H에 추가
  2. 최소 힙 H로부터 정점을 하나 꺼낸다(U)(경계에서 가장 가까운 정점) 이 정점을 MST에 추가하고, 이 정점을 포함하도록 경계를 새로 설정
  3. U와 인접한 모든 정점 V에 대해, 만약 V의 거리값이 (U, V)의 에지 가중치보다 크면 V의 거리값을 (U, V)의 에지 가중치로 설정
  4. 방문하지 않은 정점이 남아 있다면 2단계로 이동