크루스칼의 최소 스패닝 트리 알고리즘_2

크루스칼 알고리즘 코드

정점의 배열과 간선 그래프를 먼저 구성한다

모든 노드들에 대한 배열을 하나 선언
char[] vertices = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

모든 간선들에 대한 그래프를 선언
List<Edge_kruskal> list = new ArrayList<>();

list.add(new Edge_kruskal(7, 'A', 'B'));
list.add(new Edge_kruskal(7, 'A', 'B'));
list.add(new Edge_kruskal(5, 'A', 'D'));
list.add(new Edge_kruskal(7, 'B', 'A'));
list.add(new Edge_kruskal(8, 'B', 'C'));
list.add(new Edge_kruskal(9, 'B', 'D'));
list.add(new Edge_kruskal(7, 'B', 'E'));
list.add(new Edge_kruskal(8, 'C', 'B'));
list.add(new Edge_kruskal(5, 'C', 'E'));
list.add(new Edge_kruskal(5, 'D', 'A'));
list.add(new Edge_kruskal(9, 'D', 'B'));
list.add(new Edge_kruskal(7, 'D', 'E'));
list.add(new Edge_kruskal(6, 'D', 'F'));
list.add(new Edge_kruskal(7, 'E', 'B'));
list.add(new Edge_kruskal(5, 'E', 'C'));
list.add(new Edge_kruskal(7, 'E', 'D'));
list.add(new Edge_kruskal(8, 'E', 'F'));
list.add(new Edge_kruskal(9, 'E', 'G'));
list.add(new Edge_kruskal(6, 'F', 'D'));
list.add(new Edge_kruskal(8, 'F', 'E'));
list.add(new Edge_kruskal(11, 'F', 'G'));
list.add(new Edge_kruskal(9, 'G', 'E'));
list.add(new Edge_kruskal(11, 'G', 'F'));

정점들의 배열과 그래프를 이용하여 크루스컬 알고리즘 진행
List<Edge_kruskal> result = kruskal(vertices, list);
result.forEach(System.out::println);

출력
5, A - D
5, C - E
6, D - F
7, A - B
7, B - E
9, E - G

//노드 클래스
class Edge_kruskal implements Comparable<Edge_kruskal>
{
    int weigh;
    char from;
    char to;
    Edge_kruskal(int weigh, char from, char to)
    {
        this.weigh = weigh;
        this.from = from;
        this.to = to;
    }

    @Override
    public int compareTo(Edge_kruskal o) {
        return this.weigh < o.weigh ? -1 : 1;
    }

    @Override
    public String toString() {
        return this.weigh+", " +this.from+" - "+this.to;
    }
}

집합을 만들고, 가중치를 기준으로 정렬하기 이후 싸이클을 체크하며 합친다

private static List<Edge_kruskal> kruskal(char[] vertices , List<Edge_kruskal> list
{
Min Spannig Tree를 담을 리스트를 하나 선언한다
List<Edge_kruskal> MST = new ArrayList<>();

모든 정점에 대해 각각의 집합을 만들어 준다 -> 이후 각 집합들을 find/union하는 것
for (char node : vertices){
    make_set(node);
}

간선 그래프들의 가중치를 기준으로 정렬
Collections.sort(list);

싸이클 없는 간선 연결하여 그래프 만들기
for (Edge_kruskal edge : list) {
    char node_v = edge.from;
    char node_u = edge.to;

    만약 출발과 끝의 루트노드가 다르다면 이는 다른 집합이라는 의미이므로
    합쳐도 싸이클이 발생하지 않을 것이므로 합쳐준다
    if (find(node_v) != find(node_u)){
        union(node_v, node_u);
        MST.add(edge);
    }
}

return MST;
}

make_set(), find(), union() 함수

union-by-rank 기법
union : 각 노드가 서로 다른 set이라면, 같은 그래프에 속하지 않는다면, 합쳐준다
private static void union(char node_v, char node_u) {
    char root1 = find(node_v);
    char root2 = find(node_u);
    
    root1이 더 rank가 높다면 root2를 root1의 자식노드로 붙여준다
    if (rank.get(root1) > rank.get(root2))
        parent.put(root2, root1);
    else {
        parent.put(root1, root2);
        높이가 같다면 root가 된 집합의 높이를 1 올려준다
        if (rank.get(root1) == rank.get(root2)) {
            rank.put(root2, rank.get(root2)+1);
        }
    }
}

path compression 기법
find : 각 노드의 루트 노드를 비교하는 함수
private static char find(char node) {
    부모노드를 찾아 올라가면서 만나는 노드들을 모두 루트 노드의 자식노드로 만들어준다
    if (parent.get(node) != node){
        parent.put(node, find(parent.get(node)));
    }
    return parent.get(node);
}

각각의 노드들이 부모노드로 자기자신을 갖고, 높이는 0으로 초기화
private static void make_set(char node) {
    parent.put(node, node);
    rank.put(node, 0);
}

시간복잡도

크루스컬 알고리즘의 시간복잡도는 O(E log E)이다

1. 노드의 수 만큼 부분집합을 만드므로 O(V) 소요

2. 간선들의 가중치를 기준으로 정렬을 하므로 O(E log E) 소요된다

3. path compression 기법과 union by rank 기법을 이용하여 find, union을 수행한 시간
   은 O(E) 와 O(1)이다. 따라서 O(E)

결과적으로 O(E log E)의 시간복잡도를 갖는다