Kruska Algorithm

정의

탐욕적인 방법(Greedy Method)을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

개념

1. 최소 비용의 간선으로 구성됨

2. 사이클을 포함하지 않음

구현

1. 처음에 모든 간선을 가중치에 따라 오름차순으로 정렬

2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
1. 사이클이 존재하면, 남아 있는 간선 중 그 다음으로 가중치가 낮은 간선 선택

3. n - 1개의 간선이 선택될 때까지 2를 반복

코드

package org.example.tree.spanningtree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Edge {
    int from;
    int to;
    int weight;

    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

public class MinimumSpanningTree {
    private static int V, E;
    static Edge[] edgeList;
    private static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        edgeList = new Edge[E];
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            edgeList[i] = new Edge(from, to, weight);
        }

        // 간선 리스트를 가중치 기준으로 오름차순 정렬
        Arrays.sort(edgeList);

        // V개의 정점으로 make set 작업
        make();

        int result = 0;
        int count = 0;

        for (Edge edge : edgeList) {
            if (union(edge.from, edge.to)) {
                result += edge.weight;

                if (++count == V - 1) {
                    break;
                }
            }
        }

        System.out.println(result);
    }

    private static void make() {
        parents = new int[V];

        for (int i = 0; i < V; i++) {
            parents[i] = i;
        }
    }

    private static int find(int target) {
        if (parents[target] == target) {
            return target;
        }

        return parents[target] = find(parents[target]);
    }

    private static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);

        if (aRoot == bRoot) {
            return false;
        }

        parents[bRoot] = aRoot;

        return true;
    }
}

출처