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

크루스칼 알고리즘

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 다시 말해 최소 비용 신장트리를 만들기 위한 대표적인 알고리즘!

핵심 개념

간선을 거리가 짧은 순서대로 그래프에 포함시켜야 한다!

일단 모든 노드를 최대한 적은 비용으로 '연결만' 시키면 되기 때문에 모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함시키면 된다! (그래프에 포함 시킬 때 사이클이 발생하면 안되는 것을 기억하자!)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 부모 노드를 찾는 함수
int getParent(int parent[], int x)
{
    if (parent[x] == x)
        return x;
    return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수
void unionParent(int parent[], int a, int b)
{
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a < b)
        parent[b] = a;
    else
        parent[a] = b;
}

// 같은 부모를 가지는지 확인
int findParent(int parent[], int a, int b)
{
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a == b)
        return 1;
    return 0;
}

// 간선 클래스 선언
class Edge
{
public:
    int node[2];
    int distance;
    Edge(int a, int b, int distance)
    {
        this->node[0] = a;
        this->node[1] = a;
        this->distance = distance;
    }
    bool operator<(Edge &edge)
    {
        return this->distance < edge.distance;
    }
};

int main(void)
{
    int n = 7;
    int m = 11;

    vector<Edge> v;
    v.push_back(Edge(1, 7, 12));
    v.push_back(Edge(1, 4, 18));
    v.push_back(Edge(1, 2, 67));
    v.push_back(Edge(1, 5, 17));
    v.push_back(Edge(2, 4, 24));
    v.push_back(Edge(2, 5, 62));
    v.push_back(Edge(3, 5, 20));
    v.push_back(Edge(3, 6, 37));
    v.push_back(Edge(4, 7, 13));
    v.push_back(Edge(5, 6, 45));
    v.push_back(Edge(5, 7, 73));

    // 간선의 비용을 기준으로 오름차순 정렬
    sort(v.begin(), v.end());

    // 각 정점이 포함된 그래프가 어디인지 저장
    int parent[n];
    for (int i = 0; i < n; i++)
    {
        parent[i] = i;
    }

    int sum = 0; // 거리의 합을 0으로 초기화
    for (int i = 0; i < v.size(); i++)
    {
        // 사이클이 발생하지 않는 경우 그래프에 포함
        if (!findParent(parent, v[i].node[0] - 1, v[i].node[1] - 1))
        {
            sum += v[i].distance;
            unionParent(parent, v[i].node[0] - 1, v[i].node[1] - 1);
        }
    }
    cout << sum;
}