크루스칼(Kruskal) 알고리즘 & 합집합 찾기(Union-Find) 알고리즘

Union-Find algorithm

• Union-Find는 합집합 찾기 알고리즘으로 불린다.
• 원소들이 어떤 집합(그래프)에 속하는지 판별하는 데에 활용된다.
• Kruskal에서 선택된 edge들이 cycle을 형성하는지 검증하는 방법 중 하나로 Union-Find 알고리즘을 사용할 수 있다.

• 배열에 각 node의 parent node를 저장한다.
• 재귀적으로 최상위 parent node를 탐색하고 이를 바탕으로 집합을 구분한다.

구현

class UnionFind {

    public boolean hasSameParent(int[] parentNodes, int a, int b) {
        return findParent(parentNodes, a) == findParent(parentNodes, b);
    }

    public void union(int[] parentNodes, int a, int b) {
        int parentA = findParent(parentNodes, a);
        int parentB = findParent(parentNodes, b);
        if (parentA > parentB) parentNodes[parentA] = parentB;
        else parentNodes[parentB] = parentA;
    }
    
    private int findParent(int[] parentNodes, int node) {
        if (parentNodes[node] == node) return node;
        return findParent(parentNodes, parentNodes[node]);
    }
}

---

Kruskal algorithm

• cost가 할당된 edge로 연결된 그래프가 주어질 때, edge를 연결하여 최소 신장 부분 트리(MST)를 완성하는 알고리즘이다.
• 이 때 MST의 조건은 다음과 같다.
  1. 최소 비용의 edge로만 구성된다.
  2. cycle을 포함하지 않는다.
• Greedy한 방식으로 최소 비용 edge를 추가하며 전체 그래프를 얻는다.
• Union-Find 알고리즘으로 cycle 형성을 체크하는 경우, edge의 개수 e에 대해 O(eloge)의 시간복잡도를 가진다.
  

알고리즘의 흐름은 아래와 같다.

1. edge들을 cost의 오름차순으로 정렬한다.
2. 정렬된 edge 순서대로 cycle을 형성하지 않는 edge를 선택하여 MST에 추가한다.
3. 모든 node가 같은 node를 parent로 가지면 MST가 완성된 것이므로 알고리즘을 종료한다.

구현

public int kruskal(int n, int[][] costs) {
    Arrays.sort(costs, (Comparator.comparingInt(o -> o[COST])));
    int[] parentNodes = createCycleTable(n);
    int answer = 0;
    for (int[] edge : costs) {
        if (!hasSameParent(parentNodes, edge[0], edge[1])) {
            union(parentNodes, edge[0], edge[1]);
            answer += edge[COST];
        }
        if (pathCreated(parentNodes)) break;
    }
    return answer;
}