[Algorithm] 크루스칼(Kruskal)

크루스칼 알고리즘에 대한 내용을 정리해보려고 합니다.

잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다!

 

 

 

크루스칼 알고리즘이란?

 

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다.

그리디 알고리즘으로 분류됩니다.

 

 

그렇다면 크루스칼 알고리즘에 대해서 생각해봅시다.

아래 그림과 같은 그래프를 가장 적은 비용으로 모든 노드를 연결하기 위해선 어떻게 해야할까요?

 

 

 

의외로 간단합니다.

간선의 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다.

↪ 간선 정보를 오름 차순으로 정렬하고 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다.

 

 

 

일단 위 그림과 같이 모든 간선 정보를 저장합니다.

노드 1번부터 7번까지의 모든 간선 정보를 저장한 것이고, 노드6, 7번에 대한 간선 정보가 없는 이유는 다른 노드들의 간선 정보에 포함되어 있기 떄문입니다.

 

 

다음은 위 노드들의 간선 정보를 비용(거리)을 오름 차순으로 정렬합니다.

 

이제는 아래와 같은 동작 과정에 맞게 노드를 연결시켜 최소 비용으로 모든 노드를 연결하면 됩니다

 

 

🌟 동작 과정 🌟

1. 정렬된 순서에 맞게 간선을 그래프에 포함시킵니다.

2. 간선을 포함시키 전에 사이클 여부를 확인합니다.

3. 사이클이 형성된 경우 그래프에 포함시키지 않습니다.

 

 

여기서 사이클이 형성되었다는 것은 특정 노드에서 시작해서 어떤 경로를 거쳐 다시 그 노드로 되돌아 올 수 있는 경로가 존재하는 것을 의미합니다.

 

 

 

사이클이 발생하는지 여부를 확인하기 위해선 Union-Find 알고리즘을 사용하면 됩니다.

아래 포스트를 참고해주세요

[Algorithm] 유니온 파인드(Union-Find)

 

 

그렇다면 바로 설명해보도록 하겠습니다.

아래 그림은 초기 상태입니다.

 

첫번째 간선부터 선택합니다.

 

2번째 간선을 선택합니다.

 

3번째 간선을 선택합니다.

 

4번째 간선을 선택합니다.

 

5번째 간선을 선택합니다.

 

 

6번째 간선을 선택합니다.

여기서 2와 3을 연결할 경우 사이클이 발생하기 때문에 연결하지 않습니다.

 

7번째 간선을 선택합니다.

 

8번째 간선을 선택합니다.

여기서 1과 5를 연결하게 되는 경우 사이클이 발생하기 때문에 연결하지 않습니다.

 

모든 노드를 최소 비용(거리)로 연결하기 위해선 총 비용은 159이 발생합니다.

 

 

 

크루스칼 알고리즘 구현(C++)

위 내용을 토대로 C++코드로 구현하면 아래와 같습니다.

#include <bits/stdc++.h>
using namespace std;

// 크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘

// 간선의 개수는 노드의 개수 - 1
// 간선을 거리가 짧은 순서대로 포함
// 모든 노드를 최대한 적은 비용으로 연결만 시키면 되기때문에 모든 간선 정보를 오름 차순으로 정렬 비용이 적은 간선부터 차근차근 연결

// 정렬된 순서에 맞게 간선을 그래프에 포함
// 간선을 포함시키기 전 사이클 테이블 확인 (Union - Find 사용)
// 사이클이 형성된 경우 포함시키지 않음
// 부모 노드를 찾는다.
int getParent(vector<int>& parent, int a) {
    if(parent[a] == a) return a;
    else return parent[a] = getParent(parent, parent[a]);
}

void unionParent(vector<int>& parent, int a, int b) {
    int node1 = getParent(parent, a);
    int node2 = getParent(parent, b);

    // 같은 부모 노드면 패스
    if(node1 == node2) return;

    // 더 작은 값의 노드로 합친다.
    if(node1 < node2) parent[node2]  = node1;
    else parent[node1] = node2;
}

// 같은 그래프인지 확인
bool findParent(vector<int>& parent, int a, int b) {
    int node1 = getParent(parent, a);
    int node2 = getParent(parent, b);

    if(node1 == node2) return true;
    else return false;
}

// 간선 클래스 선언
class Edge {
    public:
        int node[2]; // 노드 정보
        int distance; // 거리
        Edge(int a, int b, int distance) {
            this->node[0] = a;
            this->node[1] = b;
            this->distance = distance;
        }

        bool operator <(Edge &edge) {
            return this->distance < edge.distance;
        }
};

void printParent(vector<int>& parent) {
    int len = parent.size();
    for(int i = 0; i < len; ++i) {
        cout << i << ' ' << parent[i] << '\n';
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 7; // 노드 개수
    int m = 8; // 간선 개수
    vector<Edge> v;

    v.push_back(Edge(3, 4, 7));
    v.push_back(Edge(4, 7, 13));
    v.push_back(Edge(4, 6, 23));
    v.push_back(Edge(1, 2, 29));
    v.push_back(Edge(2, 6, 34));
    v.push_back(Edge(2, 3, 35));
    v.push_back(Edge(5, 6, 53));
    v.push_back(Edge(1, 5, 75));

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

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

    int sum = 0;
    for(int i = 0; i < v.size(); ++i) {
        // 사이클이 발생하지 않는 경우 그래프에 포함
        if(!findParent(parent, v[i].node[0], v[i].node[1])) {
            sum += v[i].distance;
            unionParent(parent, v[i].node[0], v[i].node[1]);
        }
    }
    
    cout << sum << '\n';
    return 0;
}

 

 

같이 풀어보면 좋은 문제

 

1197번: 최소 스패닝 트리

1922번: 네트워크 연결

6497번: 전력난

1647번: 도시 분할 계획

 

 

9372번: 상근이의 여행

상근이의 여행 문제의 경우 크루스칼로도 풀 수 있지만, 그래프 기본 개념 문제에 해당됩니다.