크루스칼 (최소 스패닝 트리)

최소 스패닝 트리(최소 비용 신장 트리) 문제를 풀때 사용하는 알고리즘

최소한의 간선을 사용하여 모든 정점을 잇는 트리를 찾는 경우이다.

 

최소 스패닝 트리를 검사할때는 Union Find 알고리즘이 보조적으로 사용된다.
연결 유무를 같은 집합인지 아닌지로 생각할 수 있기 때문이다!
따라서 find_parent, update_parent, is_same_parent와 같은 분리 집합에 사용되는 함수들을 활용해야한다.

 

정렬된 간선들을 반복문으로 돌면서 same_parent가 아닐 시 추가하는 방법을 사용한다.
이때, 종료조건은 간선 갯수가 정점 갯수 - 1 인 경우이다!
최소 스패닝 트리는 정점 갯수 - 1 개의 간선들로 이루어지기 때문이다!

 

    for (int i = 0; i < routes.size(); i++)
    {
        // 간선 갯수가 집개수 - 1이면
        if (edge == M - 1)
        {
            break;
        }
        
        auto [cost, start, end] = routes[i];

        if (!is_same_parent(start, end))
        {
            update_parent(start, end);
            edge++;
            ans += cost;
        }
    }

 

---

[신장 트리 (Spanning Tree)]

 

N개의 정점으로 이어진 무방향그래프에서 N개의 정점과 N-1개의 간선으로 만들어진 트리

→ 최소한의 간선을 사용하여 모든 정점을 연결하는 트리

 

[최소 신장 트리 (Minimum Spanning Tree)]

 

무방향 가중치 그래프에서 신장트리를 구성하는 간선들의 가중치 합이 최소인 신장트리

1. N-1 개의 간선으로 구성
2. 간선들의 가중치 합이 최소

 

---

[Kruskal 알고리즘 구현 방법]

 

1. 간선 오름차순 구성 O(E*logE)
   1. 간선을 하나씩 추가한다
   2. 하나의 간선을 구성하는 노드들이 같은 집합이 아닌 경우에만 추가한다.
   3. 만약 간선이 N-1개라면 종료한다.
2. 간선 내림차순 구성 O(E*O(V+E))
   1. 간선을 하나씩 뺀다
   2. 정점을 분리시키는 간선이면 놔둔다.
   3. 만약 간선이 N-1개라면 종료한다.

 

1번 2번 모두 사용할 수 있지만 1번이 훨씬 직관적이고 구현하기 쉽다.

또한, 2번은 정점을 분리시키는 간선인지 확인하기 위해서는 DFS 또는 BFS를 사용하는데

그로 인해 시간복잡도가 각 간선마다 O(V+E)만큼 추가된다.

 

따라서 1번을 사용하는게 더 좋다.

 

 

---

[Kruskal Algorithm]

 

1. 전체 간선 오름차순 정렬
   • tuple<cost, start, end> 순서로 저장 후 오름차순 정렬
2. is_same_parent가 아니라면 추가
   • 추가하면서 구성 간선 갯수 + 1 (종료조건을 위해)
3. 간선이 N-1개이면 종료
   • 최소 신장 트리를 구성하는 간선 갯수는 N-1개 이므로

int solve()
{
    for (int i = 0; i < M; i++)
    {
        parent[i] = i;
    }

    int ans = 0;
    int edge = 0;

    for (int i = 0; i < v.size(); i++)
    {
        // 간선 갯수가 집개수 - 1이면
        if (edge == M - 1)
        {
            break;
        }
        auto [cost, start, end] = v[i];

        if (!is_same_parent(start, end))
        {
            update_parent(start, end);
            edge++;
            ans += cost;
        }
    }

    return ans;
}

 

---

#include <iostream>
#include <vector>
#include <algorithm>

#define SIZE 1001

using namespace std;

int M, N;
int parent[SIZE];
vector<tuple<int, int, int>> v;

int find_parent(int x)
{
    if (parent[x] == x)
    {
        return x;
    }

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

void update_parent(int x, int y)
{
    x = find_parent(x);
    y = find_parent(y);

    parent[y] = x;
}

bool is_same_parent(int x, int y)
{
    x = find_parent(x);
    y = find_parent(y);

    return x == y;
}

// 최단경로 값 구하기
int solve()
{
    for (int i = 0; i < M; i++)
    {
        parent[i] = i;
    }

    int ans = 0;
    int edge = 0;

    for (int i = 0; i < v.size(); i++)
    {
        // 간선 갯수가 집개수 - 1이면
        if (edge == M - 1)
        {
            break;
        }
        auto [cost, start, end] = v[i];

        if (!is_same_parent(start, end))
        {
            update_parent(start, end);
            edge++;
            ans += cost;
        }
    }

    return ans;
}

// cost 순으로 오름차순 정렬
bool comp(tuple<int, int, int> x, tuple<int, int, int> y)
{
    auto [c1, s1, e1] = x;
    auto [c2, s2, e2] = y;

    return c1 < c2;
}

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

    cin >> M >> N;

    int start, end, cost;
    for (int i = 0; i < N; i++)
    {
        cin >> start >> end >> cost;
        // cost 먼저 넣기
        v.push_back({cost, start, end});
    }

    // cost 순으로 오름차순 정렬
    sort(v.begin(), v.end(), comp);

    int ans = solve();

    cout << ans;

    return 0;
}