[고급 알고리즘] Graph(MST): Kruskal Algorithm

1. Kruskal Algorithm

• MST 알고리즘 입니다.
• Union-Find, 정렬된 Edge set을 사용합니다.

 

Greedy

• 인접한 최소 비용의 간선을 선택하여 MST를 만듭니다.

 

2. 동작 순서

1. 나무 초기화

• 그래프의 각 꼭짓점을 각각 하나의 나무로 초기화합니다.,

 

2. 정렬된 간선 집합 S 생성

3. 숲 F 갱신

• S에서 가장 작은 가중치의 변을 뽑습니다.
  • 변의 꼭짓점이 이미 하나의 나무로 구성되어 있으면 버립니다. (사이클 방지)
• 그 변에 연결된 두 나무를 하나의 나무로 만듭니다.
• 전체적으로 하나의 숲을 만듭니다.

 

S가 비어있지 않을 때까지 반복하여 모든 정점을 포함하는 최소 신장 트리를 만듭니다.

 

3. 예시

 

 

4. 구현

static class Edge implements Comparable<Edge> {
    final int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.weight, o.weight);
    }
}

static class UnionFind {
    final int size;

    int[] root, rank;

    public UnionFind(int size) {
        this.size = size;
        this.root = new int[size+1];
        this.rank = new int[size+1];
        makeSet();
    }

    private void makeSet() {
        for (int i = 1; i <= size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    private int find(int x) {
        if (root[x] == x) return x;

        return root[x] = find(root[x]);
    }
    
    public boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);

        if (rootX == rootY) return false;

        if (rank[rootX] > rank[rootY]) root[rootY] = root[rootX];
        else root[rootX] = root[rootY];

        if (rank[rootX] == rank[rootY]) rank[rootY]++;

        return true;
    }
}

public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    V = Integer.parseInt(st.nextToken());
    E = Integer.parseInt(st.nextToken());
    edges = new Edge[E];

    for (int i = 0; i < E; i++) {
        st = new StringTokenizer(br.readLine());
        src = Integer.parseInt(st.nextToken());
        dest = Integer.parseInt(st.nextToken());
        weight = Integer.parseInt(st.nextToken());
        edges[i] = new Edge(src, dest, weight); // 무방향. 간선 기준. 사이클 발생
    }

    Arrays.sort(edges);

    unionFind = new UnionFind(V);

    for (Edge edge : edges) {
        if (!unionFind.union(edge.src, edge.dest)) continue;

        sumW += edge.weight;
        if (++cnt==V-1) break;
    }

    System.out.println(sumW);
}

Time Complexity: $O(E\log V)$

간선 정렬 + 전체 숲 만들기 

 

간선 정렬 (가중치 오름차순): $O(E\log V)$

• $O(E\log E)$
• 최대 $E = V^2$
• 간선의 수가 적을수록 효율적입니다.

 

숲 만들기: $O(E\log V)$

• 간선에 연결된 모든 나무들을 하나의 숲으로 만듭니다.
• union 연산 시, 두번의 find 연산과 한번의 union 연산이 수행됩니다.
• (최적화) rank-based Union-Find 자료구조 사용
  • 낮은 rank의 트리를 높은 rank의 트리에 붙임
  • 높이가 한쪽의 트리로 치우치지 않게 함으로써 find 연산이 효율적으로 동작하도록 하기 위함
  • 한번 연산할 때 최악의 경우로 $O(\log V)$가 소요됩니다.
• $O(E\log V)$ = $E * O(\log V)$

 

 

 

출처

• Wiki - Kruskal Algorithm