[Java] Kruskal's Algorithm 크루스칼 알고리즘 - 최소 신장 트리(MST)

최소 신장 트리 MST(Minimun Spanning Tree) - 크루스칼 알고리즘 자바 구현

🧐 최소 신장 트리 MST(Minimun Spanning Tree)란?

최소한의 가중치를 사용하여 모든 정점이 연결되어 있을 수 있게하는 기법이다.

 

예시)

도시들은 모두 다리로 연결되어있을 때, 모든 도시를 갈 수 있게 다리를 연결하되 최소한의 다리 길이만을 사용하는 방법

(도시가 가로등으로 다리가 전선으로 바뀔수도 있다.)

네비게이션의 최단 경로

Minimun Spanning Tree

모든 정점(node 혹은 vortex)가 연결될 수 있는 경로 중 가장 적은 가중치(여기선 거리)를 사용하는 경로

 

주의사항

여기서 연결이란 다른 노드를 거쳐서 가는 것을 포함한다.

간선 혹은 브랜치(노드를 이어주는 선, 거리)는 방향성을 갖지 않는다.(연결만 되어있을 뿐, 출발과 도착지점이 고정된 것은 아니다.)

🧐 크루스칼 알고리즘 로직(Kruskal's Algorithm Logic)

1. 가장 적은 가중치를 오름차순으로 나열한다.

2. 가중치가 적은 순서대로 경로를 선택해서 노드들을 이어준다.

3. 서클(circle)이 생기지 않게 주의한다.

4. 모든 노드의 탐색이  끝나면 종료한다.

 

가정 적은 가중치를 오름차순으로 나열한다.

위 그림에서 가중치는 "거리"이므로 가장 작은 경로부터 순서대로 나열한다.(같은 가중치는 순서가 상관 없다.)

연결된 노드	A, D	B, D	B, E	A, E	A, C	C, E	C, D	A, B
거리(가중치)	1	2	2	3	3	3	3	5

가중치가 적은 순서대로 경로를 선택해서 노드들을 이어준다.

거리 1 선택 후 연결

거리 2 선택 후 연결

 

거리 2 선택 후 연결

서클(circle)이 생기지 않게 주의한다.

거리 3인 A, E 선택

이때, 가중치 3을 가지는 [A, E]를 연결하는 간선을 선택하면 서클(circle)이 발생한다.

서클이란, 위 그림과 같이 노드들이 순환하는 형태가 되는 것을 의미한다.

A노드에서 E노드로가는 경우가 두 개 이상(A->B->E, A->E)으로 중복되므로 해당 간선은 선택하지 않는다.

거리 3 선택 후 연결

마지막 거리인 5를 선택하면 서클을 생성하므로 연결하지 않는다.

모든 노드의 탐색이 끝나면 종료한다.

🧐 크루스칼 알고리즘 구현을 위한 기법(union-find, union-by-rank, path-compression)

union-find

• find: 서클을 이루는지 확인한다.
• union: 서클을 이루지 않는다면 연결한다.

find

서클을 이루는지 어떻게 확인할까?

=> 연결할 node와 연결된 또 다른 node가 자신이 연결된 또 다른 node와 일치한다면 서클일 이룬다.

예를 들어 이번에 선택된 간선은 B-C 이다.

이때, B 노드는 A노드와 연결되어 있는데 C노드가 A노드와 연결되어 있다면 서클이 이룬다.

이는 마치 B 노드와 C노드의 부모 노드가 A인 트리구조와 유사하다.

 

find 기법은 모든 노드의 부모 노드를 입력시켜 선택된 간선의 두 노드의 부모노드가 일치하는지 확인하는 것이다.

위 경우는 B노드와 C노드가 A노드와 연결되어 있기에 바로 서클임을 확인할 수 있지만 실제로 더 많은 노드가 있다면 부모노드의 부모노드 또 그 부모노드까지 계속해서 확인해야한다.

위 그림처럼 B노드의 부모인 D의 부모인 E와 서클을 이룰 수 있기 때문이다.

 

모든 부모노드들의 대해서 비교를하면 더 많은 반복횟수를 가지게 된다. 횟수를 줄이기 위해서 모든 부모 노드를 최종 root노드로 갱신해가는 방법을 이용한다.

 // find: 루트 노드를 찾아내는 함수
    public String find(String node) {
        // parh compression 기법을 이용(루트를 같게 만듦)
        if(parentNode.get(node) != node) {  // 부모가 자신과 같지 않다면, 루트가 아님
            parentNode.put(node, find(parentNode.get(node)));   // 재귀를 통해 부모의 부모로 갱신 => 루트 노드가 같아짐
        }
        return parentNode.get(node);    // 최종 부모 노드는 루트
    }

비교하고하는 노드들 부모노드는 최종적인 root노드가 되고 추후 비교할때 root노드가 동일한지만 한번 비교하면 되기에 탐색횟수를 줄 일 수 있다. 이 처럼 한번 거처간 루트를 갱신해 반복 확인을 줄이는 것이 path compression이다.

 

union

서클을 이루지 않는다면, 연결해줄 단계

 // 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)){ // 랭크가 높은 곳에 낮은 랭크를 연결
            parentNode.put(rootE, rootS);
        } else {
            parentNode.put(rootS, rootE);   // 랭크가 같다면, 한쪽의 랭크를 올리고 연결
            rank.put(rootE, rank.get(rootE) + 1);
        }
    }

union하는 과정에서는 union-by-rank 기법이 사용된다.

find를 사용하기 위해서 트리구조로 node를 이해했는데 이때 노드들의 깊이를 rank로 표시해준다.

처음 node의 rank는 0으로 시작한다.

node를 연결할 때 랭크가 낮은것을 높은것 아래에 연결한다. 랭크가 같다면 한쪽의 랭크를 높이는 방법을 사용한다.

 

최종 코드

import java.util.*;

/**
 * 최소 신장 트리(minimum spanning tree) 크루스칼 알고리즘
 * union find 알고리즘 이용 => 루트 노드가 같다면 이미 연결된 노드이다.
 * union by rank 알고리즘 이용 => 노드가 연결된 트리의 높이를 랭크로 다룸.
 * path compression 이용 => 루트 노드를 한번에 찾기 위한 기법. 한번 거쳐간 루트를 갱신(부모의 부모를 자신의 루트로 갱신 => 루트가 같아짐)
 *
 */
public class Kruskal {
    Map<String, String> parentNode = new HashMap<>();   // 부모 노드를 저장
    Map<String, Integer> rank = new HashMap<>();    // 노드의 랭크를 저장

    // 간선 객체
    public static class Edge implements Comparable<Edge> {
        int weight; // 연결된 노드들의 가중치
        String nodeS;   // 연결된 2개의 노드 중 하나
        String nodeE;   // 연결된 2개의 노드 중 하나

        // 생성자
        public Edge(int weight, String nodeS, String nodeE){
            this.weight = weight;
            this.nodeS = nodeS;
            this.nodeE = nodeE;
        }
        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;  // 가중치로 오름차순
        }
    }

    /**
     * union find 알고리즘
     */
    // find: 루트 노드를 찾아내는 함수
    public String find(String node) {
        // parh compression 기법을 이용(루트를 같게 만듦)
        if(parentNode.get(node) != node) {  // 부모가 자신과 같지 않다면, 루트가 아님
            parentNode.put(node, find(parentNode.get(node)));   // 재귀를 통해 부모의 부모로 갱신 => 루트 노드가 같아짐
        }
        return parentNode.get(node);    // 최종 부모 노드는 루트
    }

    // 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)){ // 랭크가 높은 곳에 낮은 랭크를 연결
            parentNode.put(rootE, rootS);
        } else {
            parentNode.put(rootS, rootE);   // 랭크가 같다면, 한쪽의 랭크를 올리고 연결
            rank.put(rootE, rank.get(rootE) + 1);
        }
    }

    // 초기화
    public void init(String node) {
        parentNode.put(node, node); // 부모가 자신인 노드는 루트
        rank.put(node, 0);  // 초기 랭크는 0
    }


    public ArrayList<Edge> kruskalFunc(ArrayList<String> vetices, ArrayList<Edge> edgeds) {
        ArrayList<Edge> list = new ArrayList<>();

        // 초기화
        for(String item : vetices) {
            init(item);
        }

        // 정렬
        Collections.sort(edgeds);

        // 간선 연결
        for(Edge edge : edgeds) {
            if(find(edge.nodeS) != find(edge.nodeE)) {  // 루트 노드가 다르다면 서클형성을 하지않음
                union(edge.nodeS, edge.nodeE);  // 간선을 채택해서 노드를 연결
                list.add(edge); // 채택한 간선을 결과에 담기
            }
        }

        return list;
    }
}