[Algorithm] 크러스컬 알고리즘 (Kruskal’s algorithm)

크러스컬 알고리즘

크루스컬 알고리즘(Kruskal’s algorithm)은 최소 비용 신장 트리를 찾는 알고리즘 입니다.
변의 개수를 E라고 하고 꼭지점의 개수를 V라고 하면 O(ELogV)의 시간복잡도를 가진 알고리즘 입니다.

최소 비용 신장 트리(minimum spanning tree, MST)란
신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프입니다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타냅니다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리입니다.

개요

크러스컬 알고리즘은 두가지 형태가 있습니다.(위키디피아 설명)

아래의 순서대로 작동합니다.

1.그래프의 각 꼭짓점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F을 만듭니다.
2.모든 변을 원소로 갖는 집합 S를 만듭니다.(우선순위 큐에 담습니다).
3.S가 비어있지 않는 동안 가장 작은 가중치의 변을 S에서 하나 빼냅니다.
4.그 변이 어떤 두 개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만듭니다.(Union Find를 사용해서 두 나무의 뿌리가 서로 다르면 합칩니다)
5.그렇지 않다면 그 변은 버립니다.
6.알고리즘이 종료됐을 때 숲 F는 하나의 최소 비용 신장 부분 그래프만을 가지게 됩니다.

크러스컬 알고리즘의 나머지 형태는 그래프에서 변을 제거하는 방식입니다.

1.그래프에서 꼭짓점 또는 나무를 분리해 내지 않는 최대 가중치의 변을 제거합니다.
2.그래프에 n-1개의 변만 남을 때까지 1을 반복합니다.
3.그래프에 n-1개의 변이 남으면 최소 비용 신장 트리 입니다.

탐욕적인 방법(greedy method) 을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최소 비용을 구하는 것입니다.(이삭이의 토스트 공장 블로그 설명)

1.그래프의 간선들을 가중치의 오름차순으로 정렬합니다.
2.정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택합니다. (Union Find를 이용해서 서로 다른 집합이면서 사이클이 형성되지 않는지 확인하여 선택합니다)
3.해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가합니다.

Union Find란

Union-Find(혹은 Disjoint Set)은 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조입니다. 이 자료구조가 서로 다른 두 개의 집합을 병합하는 Union 연산과 집합의 원소가 어떠한 집합에 속해있는지 판단하는 Find 연산을 지원하기 때문에 Union-Find라는 이름이 붙게 되었습니다. 1964년 처음 고안되었고 크러스컬 알고리즘에서 원소 간의 연결 여부를 판단하는 데에 사용합니다.

구현 (java)

   ArrayList<Integer> list = new ArrayList<Integer>();
   public void addItem(){
       list.add(list.size());
   }

   public int find(int index){
       if(list.get(index) == index){
           return index;
       }else{
           return find(list.get(index));
       }
   }

   public void union(int a, int b){
       int rootA = find(a);
       int rootB = find(b);
       list.set(rootA,rootB);
   }

찾아보면서 느낀점

처음엔 작년 12월쯤 '프로그래머스 - 고득점 kit - 탐욕범 - 섬 연결하기' 문제를 풀다가 도저히 모르겠어서 다른사람들이 푼 풀이를 찾았는데 이때 크루스컬 알고리즘을 처음 알게 됐었습니다.

그 당시는 문제를 풀고 다음문제로 넘어가기 위해서 간단하게 다른사람이 작성한 코드를 보고 이해하면서
이렇게 짜면 되는거구나 라고 읽고만 넘어갔엇는데 2개월 후 다시 이 문제를 풀어봤을땐
알고리즘 이름만 기억나고 사용하는 방법을 잊어버려서 다시 다른 사람의 코드를 확인했었습니다.

이런 상황을 방지하기 위해서 제대로 배워보고자 찾아보게 되었습니다.

크루스컬 알고리즘에 대한 설명을 읽으면서 또 깨닳은게 있는데, 설명에 사용되는 단어 중에 제가 모르는게 있으면 거기에 대해서도 찾아보며 이해하는게 중요한데 이전에는 이것을 간과했었던 것 같습니다. 저에겐 정확히 개념이 잡혀있지 않았던 '최소 비용 신장 트리란 무엇인지', 'Union Find는 무엇인지'를 찾아보면서 제가 이해하고싶은 내용을 정확하게 이해하는데에 도움이 된다고 생각하니까 이러한 내용을 찾아보는데에 필요한 시간이 정확한 이해를 위해 걸리는 시간을 줄여주는 값진 시간이라고 생각됩니다.

참고사이트

나무위키 - 크루스칼 알고리즘
위키디피아 - 크러스컬_알고리즘
이삭이의 토스트 공장-Kruskal 알고리즘 [크루스칼][MST][JAVA]
나무위키 - UnionFind
나무위키 - 최소 비용 신장 트리