Kruskal

Kruskal

MST를 만드는 알고리즘 중 하나이다
간선이 많을 때 사용하면 Prim 알고리즘보다 성능이 좋다

수도 코드

1.Edge 클래스 생성 & edgeList 생성

2.union-find 메서드들 생성

findSet, isSameParent, union

3.makeSet

4.간선의 가중치 기준 오름차순 정렬

5.모든 간선을 탐색하며 다른 집합에 속하면

sum갱신 & union

자바로 구현한 Kruskal

public class Kruskal {
     static class Edge implements Comparable<Edge>{
        int a, b, cost;
        public Edge(int a, int b, int cost) {
            super();
            this.a = a;
            this.b = b;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            if(this.cost>o.cost) return 1;
            return 0;
        }

    }
    static int[] root;
    static ArrayList<Edge> edgeList;

    public static void main(String[] args) {
        root = new int[7];

        // 1. makeSet
        for(int i=1; i<=6; i++) {
            root[i] = i;
        }
        // 2. 간선의 가중치 기준 오름차순 정렬
        Collections.sort(edgeList);

        // 3. 간선이 같은 집합에 없으면 추가!
        int sum = 0; // MST의 비용 
        for(int i=0; i<edgeList.size(); i++) {
            Edge edge = edgeList.get(i);
            // 같은 집합에 속하는지 확인 
            if(!isSameParent(edge.a, edge.b)) {
                // 다른 집합이면 
                sum += edge.cost; // 가중치 더해주기 
                union(edge.a, edge.b); //  union해서 같은 집합으로 만들기 
            }
        }

    }

    static int find(int a) {
        if(root[a]==a) return a;
        return root[a] = find(root[a]);
    }
    static boolean isSameParent(int a, int b) {
        a = find(a);
        b = find(b);
        if(a==b) return true;
        else return false;
    }
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a!=b) root[b] = a;
    }
}