kruskal 알고리즘

최소 신장 트리 (MST)를 구할 때 사용하는 알고리즘

최소 신장 트리 : 그래프의 모든 정점이 연결된 서브 그래프, 그 중 모든 가중치의 합이 최소인 트리

Union & Find 연산은 제외한 코드입니다. 

(Union : 집합 A와 집합 B를 합침, Find : 원소 A를 가지고 있는 집합을 찾음)

간선(edge)은 오름차순으로 정렬되 있다. 

정점 v가 정점 w와 이미 같은 집합에 있다면 cycle을 형성하므로 최소 신장 트리가 되지 않는다. 

같은 집합에 없다면 집합을 합친다. 

public void kruskal(){
        Edge k[] = new Edge[size];    //신장트리 간선 정보
        int count = 0;    //트리의 선분 개수 (n-1)
        int i = 0;
        int j = 0;
        
    while( i < edge.length){
            Edge tmp = edge[i];
            
        if(collapsingFind(tmp.v) != collapsingFind(tmp.w)){    //cycle 유무
            weightedUnion(tmp.v, tmp.w);    //cycle이 아니라면 union
            k[j] = new Edge(tmp.v, tmp.w, tmp.weight);    
            j++; 
            count++;
            minCost+=tmp.weight;
            edge[i] = null; i++;
            continue;
        }
        else {
            edge[i] = null;    i++;continue;
        }
    }
        if(count != size-1 ){
            System.out.println(+count+"최소 신장 트리가 아닙니다. ");
        }
        else{
        System.out.println("최소 신장 트리에 포함된 간선");
        for(int l = 0; l<count; l++){
            System.out.print("("+k[l].v+","+k[l].w+") ");
        }
        System.out.println("\n"+minCost);
        
    }
}
class Edge implements Comparable<Edge>{
        int v;
        int w;
        int weight;
        
        Edge(int v, int w, int weight){
            this.v = v;
            this.w = w;
            this.weight = weight;
            
        }
        @Override        //sorting
        public int compareTo(Edge o) {
            Edge e = o;
            if(weight < e.weight) return -1;
            else if(weight > e.weight) return 1;
            
            return 0;
        }