최소 스패닝 트리(Minimum Spanning Tree, MST)

---

목록

1. 최소 스패닝 트리(Minimum Spanning Tree, MST)란?

2. 최소 스패닝 트리(Minimum Spanning Tree, MST) 알고리즘- Kruskal's Algorithm

3. Kruskal's Algorithm Source Code

4. 최소 스패닝 트리(Minimum Spanning Tree, MST) 알고리즘- Prim's Algorithm

5. Prim's Algorithm Source Code

6. 크루스칼 알고리즘 vs 프림 알고리즘

---

1. 최소 스패닝 트리(Minimum Spanning Tree, MST)란?

최소 스패닝 트리의 정의는 그래프에서 그래프의 모든 정점을 연결하되, 

사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것을 의미한다. 

이때, 간선의 가중치 합을 최소로 하며 연결하여야 한다.

이때 생성되는 최소 스패닝 트리는 무조건 하나의 그래프에서 하나만 생성된다고는 보장하지 못한다.

위의 두 그래프는 같은 그래프이지만, 두가지의 서로 다른 최소 스패닝 트리를 가질 수 있다.

2. 최소 스패닝 트리(Minimum Spanning Tree, MST) 알고리즘

- 크루스칼 알고리즘(Kruskal's Algorithm) 

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

크루스칼 알고리즘은 모든 간선에 대해 가장 가중치가 작은 간선부터 연결해주면서 

최소 스패닝 트리를 만들어 나가는 알고리즘을 의미한다. 

이때 가장 작은 간선부터 간선을 연결하되, 연결하는 도중 사이클이 생기게 된다면 가중치가 작은 간선이어도 무시하여야 한다.

그림을 통해 크루스칼 알고리즘이 어떻게 진행되는지 알아보자.

위와 같은 그래프가 있을 때, 크루스칼 알고리즘이 어떻게 동작하는지 확인해 보자.

가장 가중치가 작은 간선은 6이다. 따라서 6을 처음으로 연결한다.

그 후 가중치가 작은 간선은 7이다. 따라서 7을 연결한다.

같은 방식으로 9를 연결해준다.(위의 3개 9중 하나를 선택하여 연결하면 된다.)

이때 위의 붉은선 9를 연결하게되면 아래 3개의 정점이 사이클이 생기게 되므로, 붉은선 9는 무시하고 넘어간다.

이렇게 최종적으로 완성된 그래프의 최소 신장 트리를 표현 할 수 있다.

3. 크루스칼 알고리즘 소스 코드(Kruskal's Algorithm Source Code)

[1197번] 최소 스패닝 트리 :: https://www.acmicpc.net/problem/1197 문제를 이용하여 소스 코드를 작성 하였습니다.

크루스칼 알고리즘을 더 유연하게 이해하기 위해서는 다음 자료구조에 대해 공부하고 코드를 보면 좋다.

왜냐면 크루스칼 알고리즘 자체가 유니온 파인드 자료구조를 기반으로 생성되기 때문이다.

유니온 파인드(Union Find, Disjoint Set) :: http://www.crocus.co.kr/683

크루스칼 알고리즘의 시간 복잡도 분석

크루스칼 알고리즘의 시간 복잡도는

for (int i = 0; i < E; i++)
{
    merge(edge[i].from, edge[i].to);

    if(chk)
      res += edge[i].val;
}

다음 코드에 의해 결정되는데 E번 for문 * merge의 시간 복잡도 lgV에 의해

O(ElgV)가 된다.

merge부분이 애크만 정리에 의해 O(1)이라 정렬과정에서 시간 복잡도가 판결나는데 간선을 정렬하는것이기에 O(ElgE)이다. 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef struct kruskal {
    int from;
    int to;
    int val;
}KS;
 
vector<KS> edge;
 
int parent[10002];
int res;
bool chk;
 
bool comp(KS d1, KS d2)
{
    return d1.val < d2.val;
}
 
// 파인드
int find(int u)
{
    if (u == parent[u])
        return u;
 
    return parent[u] = find(parent[u]);
}
 
// 유니온
void merge(int u, int v)
{
    chk = false;
    u = find(u);
    v = find(v);
 
    // 사이클 존재 여부 확인 코드
    if (u == v)
        return;
 
    parent[u] = v;
    chk = true;
}
 
int main()
{
    int V, E;
 
    scanf("%d %d", &V, &E);
 
    // 부모를 자기 자신으로 초기화
    for (int i = 1; i <= V; i++)
        parent[i] = i;
 
    // 그래프 형성
    for (int i = 0; i < E; i++)
    {
        KS ks;
        scanf("%d %d %d", &ks.from, &ks.to, &ks.val);
        edge.push_back(ks);
    }
 
    // 크루스칼 알고리즘에 의해 간선을 오름차순 정렬
    sort(edge.begin(), edge.end(), comp);
 
    // 간선 union, 사이클이 존재하지 않도록
    for (int i = 0; i < E; i++)
    {
        merge(edge[i].from, edge[i].to);
        
        if(chk)
            res += edge[i].val;
    }
 
    printf("%d", res);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

4. 최소 스패닝 트리(Minimum Spanning Tree, MST) 알고리즘

- 프림 알고리즘(Prim's Algorithm)

프림 알고리즘(Prim's Algorithm)

프림 알고리즘은 하나의 시작점을 잡고 시작점과 연결된 정점들에 대해 가장 가중치가 작은 간선부터 연결해주면서 

최소 스패닝 트리를 만들어 나가는 알고리즘을 의미한다. 

이때 가장 작은 간선부터 간선을 연결하되, 연결하는 도중 사이클이 생기게 된다면 가중치가 작은 간선이어도 무시하여야 한다.

그림을 통해 프림 알고리즘이 어떻게 진행되는지 알아보자.

위의 그래프가 존재할때 프림 알고리즘을 알아보자.

첫 기준점을 잡아준다.

첫 기준점과 가장 최단 거리인 정점은 9이다. 따라서 9와 연결을 해준다.

0, 9인 정점중 가장 최단 거리를 가지는 정점은 10이다. 따라서 10을 연결해준다.

0, 9, 10중 가장 최단 거리를 가지는 정점은 6이다. 따라서 6을 연결한다.

0, 9, 10, 6중 가장 최단 거리를 가지는 정점은 12이다. 따라서 12를 연결한다.

0, 9, 10, 6, 12중 가장 최단 거리를 가지는 정점은 9이다. 따라서 9를 연결한다.(이때 위의 9를 연결해도 된다.)

0, 9, 10, 6, 12, 9중 가장 최단 거리를 가지는 정점은 7이다. 따라서 7을 연결한다.

이렇게 최종적으로 프림 알고리즘에 의한 최소 스패닝 트리가 완성된다.

5. 프림 알고리즘 소스 코드(Prim's Algorithm Source Code)

[1197번] 최소 스패닝 트리 :: https://www.acmicpc.net/problem/1197 문제를 이용하여 소스 코드를 작성 하였습니다.

프림 알고리즘을 더 유연하게 이해하기 위해서는 다음 자료구조에 대해 공부하고 코드를 보면 좋다.

왜냐면 프림 알고리즘은 우선순위 큐를 기반으로 제작되고, 우선순위 큐 다익스트라와 매우 비슷하기 때문이다.

우선순위 큐 :: http://www.crocus.co.kr/693

우선순위 큐 다익스트라 :: http://www.crocus.co.kr/546

프림 알고리즘의 시간 복잡도 분석

프림 알고리즘의 시간 복잡도는

    while (!pq.empty())
    {
        int here = pq.top().second;
        int hereCost = pq.top().first;
 
        pq.pop();
 
        // 이미 방문한 정점은 무시한다.
        if (visit[here])
            continue;
 
        visit[here] = true;
 
        ans += hereCost;
 
        // 다음 정점을 우선순위 큐에 넣어준다.
        for (int i = 0; i < vc[here].size(); i++)
        {
            int there = vc[here][i].first;
            int thereCost = vc[here][i].second;
 
            pq.push(pii(thereCost, there));
        }
    }

위의 코드에 의해 정해지는데, 모든 정점을 우선 순위 큐로 확인하니 lgV,

그 정점들에 대해 간선을 확인하니 E, 따라서 O(ElgV)가 된다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
 
#define MAX_NODE 10001
 
using namespace std;
 
typedef pair<int, int> pii;
 
bool visit[MAX_NODE];
vector<pii> vc[MAX_NODE];
 
void prim(int start)
{
    visit[start] = true;
 
    // 우선 순위 큐(최소 힙)
    priority_queue<pii, vector<pii>, greater<pii>> pq;
 
    // 1번 정점을 시작점으로 한다.
    for (int i = 0; i < vc[start].size(); i++)
    {
        // 정점과 가중치를 priority_queue에 넣어준다.
        int next = vc[start][i].first;
        int nextCost = vc[start][i].second;
 
        pq.push(pii(nextCost, next));
    }
 
    int ans = 0;
 
    while (!pq.empty())
    {
        int here = pq.top().second;
        int hereCost = pq.top().first;
 
        pq.pop();
 
        // 이미 방문한 정점은 무시한다.
        if (visit[here])
            continue;
 
        visit[here] = true;
 
        ans += hereCost;
 
        // 다음 정점을 우선순위 큐에 넣어준다.
        for (int i = 0; i < vc[here].size(); i++)
        {
            int there = vc[here][i].first;
            int thereCost = vc[here][i].second;
 
            pq.push(pii(thereCost, there));
        }
    }
 
    printf("%d", ans);
}
 
int main()
{
    int V, E;
    scanf("%d %d", &V, &E);
 
    for (int i = 0; i < E; i++)
    {
        int from, to, val;
        scanf("%d %d %d", &from, &to, &val);
 
        vc[from].push_back(pii(to, val));
        vc[to].push_back(pii(from, val));
    }
 
    prim(1);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

6. 크루스칼 알고리즘 vs 프림 알고리즘

그렇다면 언제 크루스칼 알고리즘을 쓰고, 언제 프림 알고리즘을 쓰면 좋을까?

이에따른 정답은 시간 복잡도로 생각해 보면 좋을 것 같다.

크루스칼 알고리즘 시간 복잡도 :: O(ElgE)

프림 알고리즘 시간 복잡도 :: O(ElgV)

결국, 간선의 개수가 작은 경우에는 크루스칼 알고리즘을, 간선의 개수가 많은 경우에는 프림 알고리즘이 더 좋다는 것이 자명하다.