목록


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


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


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


1
2
3
4
5
6
7
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)이다. 



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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#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 >>
Crocus






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


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


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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    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)가 된다.


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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
 
#define MAX_NODE 10001
 
using namespace std;
 
typedef pair<intint> 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 >>
Crocus





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


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

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

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

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



  1. NEwBie 2018.03.10 21:21

    크루스칼을 구성하는
    알고리즘을 짤 때 사용하는 유니온파인드를
    블로그포스팅에 올렸던
    유니온파인드보다 naive하게 구성한이유가있나요?

  2. 가누 2018.03.10 21:38 신고

    랭크는필요가무의미합니다 사실

  3. NEwBie 2018.03.10 21:44

    랭크가 그
    유니온파인드 합칠때
    균형있게? 옆으로펴지게?그런역할아닌가요?
    여기선필요가..없으려나요

  4. 가누 2018.03.10 21:56 신고

    보통랭크를 안ㅆㅓ도괜찮아요

  5. 가누 2018.03.10 21:57 신고

    그거에대한증명이있는데 한번찾아볼수있을거에요

  6. NEwBie 2018.03.10 22:01

    음한번찾아볼게요
    종만북에서 랭크가 나오길래
    저걸써야 평평한구조가되나싶어서 물어본거였습니ㄷ ㅣ

  7. J 2018.03.21 20:06

    굿!

  8. 2영재 2018.04.19 18:50 신고

    안녕하세요 궁금한 점이 있어 질문글 남깁니다.
    Union-Find 에서 parents의 크기가 V인데 왜 merge의 시간복잡도가 logV가 아닌 logE 인건가요?

    • 2영재 2018.04.19 18:53 신고

      제 생각에 간선을 정렬하는 과정에서의 시간복잡도가 ElogE 이기 때문에 크루스칼의 전체 시간복잡도가 ElogE 인거 같은데 아닌가요 ㅠㅠ

    • 가누 2018.04.19 19:07 신고

      예.. 제가 O(ElgE)라 적어뒀는데..
      아마 프림알고리즘 O(ElgV)를 보고 착각하신듯하네요!

    • 2영재 2018.04.19 19:11 신고

      먼저 답글 감사드립니다.

      그치만 저는 마지막 부분을 말씀드린게 아니구 중간에 중간에 크루스칼 알고리즘 시간복잡도 분석 하시는 부분을 말씀드린거였습니다.


      크루스칼 알고리즘의 시간복잡도는 다음 코드에 의해 결정되는데 E번 for문 * merge의 시간 복잡도 lgE에 의해

      O(ElgE)가 된다.

      라고 적혀있습니다.
      저는 저부분에서 merge의 시간복잡도가 logV이지 않나요? 라고 질문 드린거에요 ㅎㅎ

    • 가누 2018.04.19 19:22 신고

      그러네요! 감사합니다!

      제가 포스팅한 유니온 파인드에서 merge도 O(lgN)이고, 위키에도 O(ElgV)라고 돼있네요! 정정하겠습니다~

    • 가누 2018.04.19 19:26 신고

      근데 아마 크루스칼은 보통 O(ElgE)라고 제가 들은것같긴한데.. 사실상 머지는 신경안써도 되고(O(1)이라서요)

      사실상 정렬만 신경쓰면 되는데 그 부분이 O(VlgV)이기도 하네요

    • 2영재 2018.04.19 19:34 신고

      우선 답변 감사드립니다. 댓글은 처음 남겼지만 블로그에서 많이 배우고 있었습니다 ㅎㅎㅎ

      답변해주신 내용 중에서
      머지에서도 파인드 연산을 하기때문에 logV 가 맞지 않나요...???

      그리고 일반적인 경우 V <= E <= V^2 이고 sort할때 E개의 원소를 정렬하는 거여서 ElogE가 맞지 않나요...???

    • 가누 2018.04.19 19:34 신고

      아 정정합니다...

      크루스칼은 O(ElgE)가 맞구요

      머지부분이 O(1)이라 정렬과정에서 관건인데

      그 정렬과정이 간선을 정렬하는것이기에
      O(ElgE)입니다.