[알고리즘/C++] 최소 신장 트리 (Minimum Spanning Tree) & Kruskal, Prim

Spanning Tree

• 신장 트리라고도 한다.
• 그래프가 n개의 정점을 가질 때, (n-1)개의 간선으로 이루어진 트리를 말한다.
• 이때 n개의 정점을 가진 그래프에서 (n-1)개의 간선을 선택하면 무조건 트리의 형태가 된다.
• 그래프에서 간선을 선택하여 만들어진 트리를 신장 트리(Spanning Tree)라고 한다.

Minimum Spanning Tree

• 간선간에 가중치가 존재한다고 가정하였을 때, 신장 트리 중에 가중치의 합이 가장 작은 신장트리를 Minumum Spanning Tree (최소 신장 트리)라고 한다.
• 최소 스패닝 트리를 구하는 알고리즘은 크게 Kruskal, Prim 알고리즘이 있다.

Kruskal Algorithm

• 그리디 알고리즘을 사용하여 가장 작은 가중치를 선택하며 진행되는 알고리즘이다.

1. 간선들을 가중치의 오름차순으로 정렬한다.
2. 가중치가 작은 순으로 간선들을 선택한다. 만약 선택한 간선으로 사이클이 형성되어 트리가 아니게 된다면 해당 간선은 선택하지 않는다.
3. 선택한 간선의 개수가 (n-1)개가 된다면 종료한다.

• 사이클이 형성되는지의 여부는 노드의 개수만큼의 parent 배열을 통해 판단한다. (union find 알고리즘이라고도 불린다.)
  • parent배열은 i번째 노드의 최상위 부모(=root)를 의미한다.
  • 즉, parent의 초기화는 parent[i] = i로 할 수 있다. (자기 자신이 부모노드가 된다는 뜻이다.)
  • a, b간에 간선이 존재하여 이를 선택할 때, unionParent라는 함수로 두 노드가 연결됨을(즉, 집합이 됨) 표현한다. 두 노드의 값을 비교하여 번호가 작은 노드가 부모노드가 되도록 한다. 구현 메서드는 다음과 같다.

    void unionParent(int vertex1, int vertex2) {
        vertex1 = getParent(vertex1);
        vertex2 = getParent(vertex2);
    
        if(vertex1 < vertex2) parent[vertex2] = vertex1;
        else parent[vertex1] = vertex2;
    }

  • getParent함수는 vertex번호를 가진 노드의 부모 노드를 리턴한다. 이는 재귀함수로 부모노드를 타고 올라갈 수 있으며, 최상위 부모노드에 다다르면 parent[i] = i 을 만족하므로 i를 리턴하면 된다.

    int getParent(int vertex) {
        if (parent[vertex] == vertex) return vertex;
        return getParent(parent[vertex]);
    }

  • 위에 두 함수로 사이클의 유무를 판단 가능하다. a, b의 간선을 연결하였다고 가정했을 때, 사이클이 존재한다면 a와 b의 부모노드를 구하면 같을것이다. 사이클이 존재하지 않는다면 a, b을 연결하는 간선 이외의 연결되는 간선들이 없다는 뜻이므로 a, b의 부모노드는 다를거라고 유추 가능하다.

    bool isCycle(int vertex1, int vertex2) {
        vertex1 = getParent(vertex1);
        vertex2 = getParent(vertex2);
    
        if(vertex1 == vertex2) return true;
        else return false;
    }

구현

백준 1197번 문제 최소 스패닝 트리 가 최소 스패닝 트리를 구현하는 문제이다.

#include <bits/stdc++.h>
#define MAX 100001
using namespace std;

int v, e;
//          weight, (start, end)
vector<pair<int, pair<int, int>>> edge;
int parent[MAX];

int getParent(int vertex) {
    if (parent[vertex] = vertex) return vertex;
    return getParent(parent[vertex]);
}

void unionParent(int vertex1, int vertex2) {
    vertex1 = getParent(vertex1);
    vertex2 = getParent(vertex2);

    if(vertex1 < vertex2) parent[vertex2] = vertex1;
    else parent[vertex1] = vertex2;
}

bool isCycle(int vertex1, int vertex2) {
    vertex1 = getParent(vertex1);
    vertex2 = getParent(vertex2);

    if(vertex1 == vertex2) return true;
    else return false;
}

int main() {
    cin >> v >> e;

    int a, b, c;
    for(int i = 0; i < e; i++) {
        cin >> a >> b >> c;
        edge.push_back({c, {a, b}});
        parent[i+1] = i+1;
    }

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

    int cnt = 0, sum = 0;

    for(auto tmp : edge) {
        if (cnt >= v) break;

        int weight = tmp.first;
        int start = tmp.second.first;
        int end = tmp.second.second;
        if (!isCycle(start, end)) {
            unionParent(start, end);
            sum += weight;
            cnt++;
        }
    }

    cout << sum;
}

• vector에서 처음 원소를 가중치로 하여 가중치에 대해 오름차순으로 정렬되도록 하였다.
• edge를 순회하며, 선택한 간선의 개수가 노드의 개수보다 크거나 같으면 break되도록 하였다.
• start, end간의 사이클이 존재하지 않는다면 (!isCycle(start, end)), unionParent(start, end)로 간선을 추가하고 가중치를 더한다.

Prim Algorithm

• 프림 알고리즘은 우선순위 큐를 사용하여 가장 작은 가중치를 지닌 간선을 선택한다. (가장 작은 가중치를 선택한다는 측면에서 그리디 알고리즘으로 볼 수도 있겠다.)

1. 임의의 노드를 선택한다. (밑에서의 구현은 1로 가정하였다.)
2. 해당 노드와 인접한 간선을 우선순위 큐에 push한다. (이때 가장 작은 가중치를 pop할 수 있도록 최소 힙을 사용한다고 가정한다.)
3. pq.pop()을 하고 pop한 노드가 이미 방문했는지 체크 후, 가중치를 더한다.
4. pop한 노드에 인접한 간선이며 방문하지 않은 노드를 우선순위 큐에 push한다.
5. 선택한 간선이 n - 1개가 되도록 반복한다.

구현

프림 알고리즘 또한 백준 1197번 문제 최소 스패닝 트리 로 구현하였다.

#include <bits/stdc++.h>
#define MAX 100001
using namespace std;

bool isSelected[MAX] = {0,};
vector<pair<int, int>> graph[MAX];

int v, e;

int main() {
    cin >> v >> e;

    int a, b, c;
    for(int i = 0; i < e; i++) {
        cin >> a >> b >> c;
        graph[a].push_back({c, b});
        graph[b].push_back({c, a});
    }

    int start = 1;
    int cnt = 0, sum = 0;
    isSelected[start] = 1;
    //                  weight, pair<start, end>
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>> pq;

    for(auto tmp : graph[start]) {
        pq.push({-tmp.first, {start, tmp.second}});
    }

    while(cnt < v - 1) {
        int w = -pq.top().first;
        int start = pq.top().second.first;
        int end = pq.top().second.second;
        pq.pop();

        if(isSelected[end]) continue;
        isSelected[end] = 1;
        sum += w;
        cnt++;

        for(auto tmp : graph[end]) {
            if (isSelected[tmp.second]) continue;
            pq.push({-tmp.first, {end, tmp.second}});
        }
    }
    cout << sum;
}

• 간선은 vector를 통해 표현하여 인접 노드에 대한 정보를 순회하기 쉽도록 하였다.
• 우선순위 큐는 최소 힙을 사용해야 오름차순 정렬이 되므로 push하거나 값을 받아올 때 가중치 부분만 음수 처리하였다.

시간복잡도

• 노드의 개수를 $n$, 간선의 개수를 $m$이라고 하자. $m$의 범위는 $n-1 ≤ m ≤ \frac{n(n-1)}{2}$가 됨은 자명하다.
• kruskal의 시간복잡도는 $O(mlogm)$이다.
• prim의 시간복잡도는 $O(m logn)$이다.
• 위에서 언급한 $m$의 범위로 정리하였을 때 다음과 같다.
  • kruskal :
    1. sparse한 그래프 : $O(n logn)$
    2. dense한 그래프 : $O(n^2logn)$
  • prim :
    1. sparse한 그래프 : $O(nlogn)$
    2. dense한 그래프 : $O(n^2)$
• 이때 dense한 그래프일수록 (간선이 더 많을수록) kruskal 알고리즘의 시간복잡도는 prim의 시간복잡도보다 커짐을 확인할 수 있다.
• 즉, 간선이 많을수록 prim알고리즘이 더 효율적임을 알 수 있다.