C YC

IT Dev who working in Republic Of Korea

3 minute read

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

크루스칼 알고리즘은 가중치가 있는 연결된 무방향 그래프에서 최소 신장 트리를 찾는 알고리즘입니다.
탐욕 알고리즘(Greedy Algorithm)의 한 종류로, 각 단계에서 최소 비용의 간선을 선택하여 MST를 구성해 나갑니다. 중요한 점은 사이클을 형성하지 않는 간선만 선택한다는 것입니다.

kruskal
(출처 : https://www.oreilly.com/library/view/c-data-structures/9781788833738/a2714e77-af8c-494a-a485-df5521ced3f0.xhtml)

특징

  • 탐욕 알고리즘: 각 단계에서 최적의 선택을 합니다.
  • 사이클 방지: 선택한 간선들이 사이클을 형성하지 않도록 관리합니다.
  • 분리 집합(Disjoint Set) 자료구조 활용: 사이클 형성을 효율적으로 확인하기 위해 분리 집합 자료구조를 사용합니다.



동작 방식

  1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬합니다.
  2. 각 정점을 각각의 집합으로 초기화합니다. (분리 집합)
  3. 정렬된 간선 목록을 순회하면서 다음을 반복합니다. a. 현재 간선의 두 정점이 서로 다른 집합에 속해 있다면, i. 간선을 MST에 추가합니다. ii. 두 정점의 집합을 합칩니다 (Union).
  4. 모든 정점이 하나의 집합으로 합쳐지거나, 모든 간선을 확인하면 알고리즘을 종료합니다.

프림 알고리즘과의 비교

크루스칼 알고리즘과 함께 최소 신장 트리를 찾는 대표적인 알고리즘으로 프림 알고리즘(Prim’s Algorithm)이 있습니다.

  • 크루스칼 알고리즘: 간선 중심, 분리 집합 사용, 희소 그래프에 효율적
  • 프림 알고리즘: 정점 중심, 우선순위 큐 사용, 밀집 그래프에 효율적

어떤 알고리즘을 사용할지는 그래프의 특성 (간선의 개수, 밀집도 등)에 따라 결정해야 합니다. 일반적으로 간선의 개수가 적은 희소 그래프의 경우 크루스칼 알고리즘이 효율적이고, 간선의 개수가 많은 밀집 그래프의 경우 프림 알고리즘이 효율적입니다.



장단점

장점

  • 구현이 비교적 간단: 프림 알고리즘(Prim’s Algorithm)에 비해 구현이 직관적이고 간단합니다. 특히 분리 집합(Disjoint Set) 자료구조를 활용하면 코드의 간결성이 더욱 높아집니다.
  • 희소 그래프(Sparse Graph)에 효율적: 간선의 수가 정점 수에 비해 적은 그래프에서 특히 효율적인 성능을 보입니다. 간선을 정렬하는 데 O(E log E)의 시간이 걸리지만, 희소 그래프의 경우 E가 V^2보다 훨씬 작기 때문에 빠른 속도를 나타냅니다. (E는 간선 수, V는 정점 수)
  • 사이클 검사 용이: 분리 집합 자료구조를 사용하여 사이클 형성을 매우 효율적으로 검사할 수 있습니다. 각 간선을 확인할 때, 두 정점이 같은 집합에 속해 있는지 확인하는 것으로 사이클 여부를 O(1)에 가깝게 확인할 수 있습니다.
  • 전역적인 관점: 프림 알고리즘은 시작 정점에서부터 트리를 확장해나가는 지역적인 관점을 가지는 반면, 크루스칼 알고리즘은 그래프의 모든 간선을 고려하는 전역적인 관점을 가집니다. 이는 특정 상황에서 더 나은 해를 찾을 수 있는 가능성을 제공합니다.

단점

  • 밀집 그래프(Dense Graph)에 비효율적: 간선의 수가 많은 그래프에서는 정렬에 필요한 시간(O(E log E))이 크게 증가하여 프림 알고리즘보다 성능이 떨어질 수 있습니다. 밀집 그래프의 경우 E가 V^2에 가까워지므로, O(V^2 log V^2)의 시간이 소요될 수 있습니다.
  • 정렬 필요: 간선들을 가중치에 따라 정렬해야 하므로, 정렬에 필요한 추가적인 메모리와 시간이 필요합니다.
  • 중간 단계의 트리 형태를 제공하지 않음: 프림 알고리즘은 알고리즘 진행 과정에서 항상 하나의 연결된 트리를 유지하는 반면, 크루스칼 알고리즘은 여러 개의 분리된 트리(숲)으로 시작하여 최종적으로 하나의 트리로 합쳐지는 과정을 거칩니다. 따라서 중간 단계의 트리 형태를 확인하기 어렵습니다.



예제

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

using namespace std;

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const { // 간선 정렬을 위한 비교 연산자
        return weight < other.weight;
    }
};

class DisjointSet { // 분리 집합 자료구조
private:
    vector<int> parent;

public:
    DisjointSet(int n) : parent(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int i) { // 대표 원소 찾기 (경로 압축 최적화)
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) { // 두 집합 합치기
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j)
            parent[root_i] = root_j;
    }
};

int main() {
    int numVertices = 4;
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    sort(edges.begin(), edges.end()); // 간선 정렬

    DisjointSet ds(numVertices);
    vector<Edge> mst;
    int mstWeight = 0;

    for (const auto& edge : edges) {
        if (ds.find(edge.u) != ds.find(edge.v)) { // 사이클을 형성하지 않는 경우
            mst.push_back(edge); // MST에 추가
            ds.unite(edge.u, edge.v); // 두 정점의 집합 합치기
            mstWeight += edge.weight;
        }
    }

    cout << "Minimum Spanning Tree:" << endl;
    for (const auto& edge : mst) {
        cout << "(" << edge.u << ", " << edge.v << ") Weight: " << edge.weight << endl;
    }
    cout << "Total MST weight: " << mstWeight << endl;

    return 0;
}


Top

You May Also Enjoy

1 minute read