Kruskal 알고리즘

Kruskal 알고리즘

컴퓨터 과학에서 크러스컬 알고리즘은 최소 비용 신장 부분 트리를 찾는 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.
노드는 정점과 같고 간선은 거리와 같다.

유니온파인드 알고리즘

find 함수 : 문자열에 특정 문자를 포함하고 있는지 확인하는
put 함수 : 값 추가

횟수를 줄이기 위해서 모든 부모 노드를 최종 root노드로 갱신해가는 방법을 이용, 처음 node의 rank는 0으로 시작한다.
1. find : 루트 노드를 찾아내는 함수

public String find(String node) {
	// root를 같게 만든다
	if(parentNode.get(node) != node) {     // 부모가 자신과 같지 않다면, 루트가 아님
	parentNode.put(node, find(parentNode.get(node)));  // 재귀를 통해 부모의 부모로 갱신 → 루트 노드가 같아짐
}
return parentNode.get(node);            // 최종 부모 노드는 root 

2. union: 서클을 이루지 않는다면 연결해줄 단계, 간선 연결

public void union(String nodeS, String nodeE) {
	String rootS = find(nodeS);
	String rootE = find(nodeE);
	// union by rank 기법을 이용
	if(rank.get(rootS) > rank.get(rootE)) {      // rank가 높은 곳에서 낮은 rank를 연결
	} else {
		parentNode.put(rootS, rootE);     // rank가 같다면, 한쪽의 rank를 올리고 연결
		rank.put(rootE, rank.get(rootE) +1);
	}
}

참고 블로그 : https://m.blog.naver.com/parkhj2416/221861837543

Kruskal 알고리즘 코드

import java.util.ArrayList;
import java.util.Collections;

class Edge implements Comparable<Edge> {
    int v1;
    int v2;
    int cost;
    Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge o) {
        if(this.cost < o.cost)
            return -1;
        else if(this.cost == o.cost)
            return 0;
        else
            return 1;
    }
}
public class Main {
    public static int[] parent;
    public static ArrayList<Edge> edgeList;
	
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x != y)
            parent[y] = x;
    }
	
    public static int find(int x) {
        if(parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    public static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return true;
        else return false;
    }
    public static void main(String[] args) {
        edgeList = new ArrayList<Edge>();
        edgeList.add(new Edge(1,4,4));
        edgeList.add(new Edge(1,2,6));
        edgeList.add(new Edge(2,3,5));
        edgeList.add(new Edge(2,4,3));
        edgeList.add(new Edge(2,5,7));
        edgeList.add(new Edge(2,6,8));
        edgeList.add(new Edge(3,6,8));
        edgeList.add(new Edge(4,5,9));
        edgeList.add(new Edge(5,6,11));
		
        parent = new int[7];
        for(int i = 1; i <= 6; i++) {
            parent[i] = i;
        }
		
        Collections.sort(edgeList);
		
        int sum = 0;
        for(int i = 0; i < edgeList.size(); i++) {
            Edge edge = edgeList.get(i);
            if(!isSameParent(edge.v1, edge.v2)) {
                sum += edge.cost;
                union(edge.v1, edge.v2);
            }
        }
		
        System.out.println(sum);
    }	
}

출처 : https://brenden.tistory.com/36