[Algorithm] 최소 신장 트리

[Algorithm] 최소 신장 트리 (Minimum Spanning Tree)

최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다. (Spanning Tree란, 그래프 내의 모든 정점을 포함하는 트리이다.) 즉, MST는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다.

최소 신장 트리 (Minimum Spanning Tree) 특징

사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로, 사이클은 포함하지 않는다. *
N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다.
간선의 가중치의 합이 최소가 되어야 한다.

최소 신장 트리의 핵심 이론

최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.

최소 신장 트리는 다른 그래프 알고리즘과는 달리, 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있다. 그 이유는 에지를 기준으로 하는 알고리즘이기 때문이다. 또한 사이클이 존재하면 안된다는 특징이 있기 때문에, 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 한다.

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화 하기

에지 리스트를 노드 변수 2개와 가중치 변수로 구성한다. 그리고 사이클 처리를 위한 유니온 파인드 배열도 초기화 해야 한다. 배열의 인덱스를 해당 자리의 값으로 초기화 하면 된다.

2. 그래프 데이터를 가중치 기준으로 정렬하기

에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.

3. 가중치가 낮은 에지부터 연결 시도하기

가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다. 이때 바로 연결하지 않고 이 에지를 연결했을 때, 그래프 사이클 형성 유무를 find 연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union연산을 이용해 두 노드를 연결한다.

가중치가 낮은 에지부터 차례대로 연결을 시도한다. find() 연산을 시도해서 대표 노드가 다를 경우, 연결 한다. ( 만약 대표 노드가 같을 경우, 연결했을때 사이클이 형성된다. )

4. 과정 3번 반복하기

전체 노드의 개수가 N개이면, 연결한 에지의 개수가 N-1개가 될때까지 과정 3을 반복한다.

총 에지의 비용은 2+3+4+8 = 17이므로, 17을 출력한다.

5. 총 에지 비용 출력하기

에지의 개수가 N-1개가 되면 알고리즘을 종료하고, 완성된 최소 신장 트리의 총 에지 비용을 출력한다.

백준 p1197 최소 스패닝 트리

최소 신장 트리를 구하는 가장 기본적인 문제이다. 크루스칼 알고리즘을 수행한다. 미사용 에지 중 가중치가 가장 작은 에지를 선택하고, ( 우선순위 큐 사용 )이 에지를 연결했을때 사이클의 발생 유무를 판단한다. ( 유니온 파인드 연산 사용 ) 사이클이 발생하면 생략하고, 발생하지 않으면 에지값을 더한다.

  
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class p1197 {
    static int V;
    static int E;
    static int[] parent;
    static PriorityQueue<pEdge> queue;

    static class pEdge implements Comparable<pEdge>{
        int start, end, cost;
        pEdge(int start, int end, int cost){
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(pEdge o) {
            return this.cost-o.cost;
        }
    }
    //유니온 파인드 연산
    public static void union(int a, int b){
        a = find(a);
        b=find(b);
        if(a!=b){
            parent[b] =a;
        }
    }
    public static int find(int a){
        if ( parent[a]==a)
            return a;
        else return parent[a] = find(parent[a]);
    }
    //최소 신장 트리 구하기
    public static void MST(){
        int result=0;
        int useEdge=1;
        while(useEdge<V){
            pEdge nowNode = queue.poll();
            if(find(nowNode.start)!=find(nowNode.end)){
                union(nowNode.start,nowNode.end);
                result = result + nowNode.cost;
                useEdge++;
            }
        }
        System.out.println(result);
    }
    public static void main(String[]args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        parent = new int[V+1];
        for(int i=0;i<V+1;i++){
            parent[i] = i;
        }
        queue = new PriorityQueue<>();
        for(int i=0;i<E;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            queue.add(new pEdge(start,end,cost));
        }
        MST();
    }
}

Reference

Do it! 알고리즘 코딩 테스트 자바 편 (김종관 저, 이지스퍼블리싱)

[Algorithm] 최소 신장 트리