최소 신장 트리 (MST , Minium Spanning Tree)

최소 신장 트리(MST, Minium Spanning Tree)

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

 

---

신장 트리(Spanning Tree)

그래프 내의 모든 정점을 연결한 트리

신장 트리의 특징

• 모든 노드는 서로 연결되어 있다.
• 간선(edge)의 수 E는 노드의 수 V에서 1을 뺀 것과 같다.

---

트리(Tree)

그래프의 일종으로 사이클이 없는 연결그래프이다.

트리의 특징

• root node를 제외한 모든 node는 단 하나의 부모 node만 가진다.
• 임의의 노드에서 다른 노드로 가는 경로는 유일하다.
• 회로(cycle)가 존재하지 않는다.
• 간선(edge)를 하나 자르면 트리가 두 개로 분리된다.

---

최소 신장 트리 구현 방법

Kruskal 알고리즘

탐욕적인 방법(greedy method)을 이용해 MST를 찾는 알고리즘

특징

• 간선(Edge) 선택 기반
• 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.

과정

1. 그래프의 간선들을 오름차순으로 정렬
2. 사이클을 형성하지 않는 가장 낮은 가중치를 갖는 간선(간선 배열의 첫인덱스)부터 선택한다.
3. 모든 간선탐색이 끝날때까지 2를 반복한다.

시간복잡도

E를 간선의 갯수라 할 때 O(ElogE)의 시간복잡도를 갖는다.

1. 정렬 → O(logN)
2. 사이클을 판별하는 Union-Find 알고리즘을 사용한다. → O(a(N))

Union-Find알고리즘은 경로압축을 수행할 경우 Find (O(logN)), Merge(O(logN)), 총 O(logN)이지만 연산을 호출할 때마다 트리의 크기가 달라지기 때문에 평균 O(a(N))로 정의된다.

여기서, a는 에커만 함수를 이용해 정의 되는 함수이다. a(2^65536)= 대략 5정도로 거의 모든 수가 상수시간에 작동하는 것을 알 수 있다.

따라서 E를 간선의 갯수라 할 때 O(ElogE)의 시간복잡도를 갖는다.

구현

여기서는 직접정렬 대신 우선순위큐를 사용해 간접정렬하였습니다.

1197번: 최소 스패닝 트리

#include <iostream>
#include <queue>
#include <functional>

using namespace std;
typedef struct edge
{
    int f, s, val;
    bool operator < (const edge &o)const{
        return val > o.val;
    }
};

priority_queue<edge, vector<edge> > pq;
int V, E,ans,parent[10001];
int find(int x)
{
    if (!parent[x]) return x;

    return parent[x] = find(parent[x]);
}

bool merge(int u, int v)
{
    u = find(u);
    v = find(v);

    if (u == v) return false;

    parent[u] = v;
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> V >> E;
    for (int i = 0; i < E; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        pq.push({ a, b, c });
    }

    while (!pq.empty())
    {
        edge t = pq.top();
        pq.pop();
        if (merge(t.f, t.s)) ans += t.val;

    }
    cout << ans;
    return 0;
}

---

Prim 알고리즘

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법

특징

• 정점(Vertex) 선택 기반
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.

과정

1. 방문한 정점으로부터(처음엔 임의의 정점 삽입) 인접한 정점들을 탐색해 최소 가중치를 갖는 간선을 선택한다.
2. 해당 간선과 연결된 정점을 방문표시하고 해당 정점과 연결된 간선을 탐색해 정점을 추가한다. 이때 방문한 정점으로 가는 간선은 제외한다.
3. 모든 정점을 방문할때까지 1,2를 반복한다.

시간복잡도

E를 간선의 갯수, V를 정점의 갯수라 할때 O(ElogV)

방문한 정점과 연결된 간선을 우선순위 큐를 사용하여 정렬하고 탐색하면 O(ElogE)의 시간복잡도를 갖는다.

구현

1197번: 최소 스패닝 트리

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAXV 10001

int V, E, ans;
vector<pair<int, int> >adj[MAXV];
int vertexVisit[MAXV];

typedef struct Ver{
    int node, val;
    bool operator <(const Ver &o)const{
        return val < o.val;
    }
};

int sol()
{
    priority_queue <Ver> pq;
    pq.push({ 1,0 });

    while (!pq.empty())
    {
        int cur = pq.top().node;
        int v = -pq.top().val;
        pq.pop();

        if (vertexVisit[cur])continue;
        vertexVisit[cur] = 1;
        ans += v;

        for (int i = 0; i < adj[cur].size(); i++)
        {
            int next = adj[cur][i].first;
            int val = adj[cur][i].second;
            if (vertexVisit[next])continue;
            pq.push({ next, -val });
        }

    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> V >> E;

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

    cout << sol();
    return 0;
}