MST(최소 스패닝 트리)

최소 스패닝 트리

 

개념

그래프 내의 모든 정점을 포함하는 트리를 스패닝 트리라고 하는데

이러한 스패닝 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 최소 스패닝 트리라고 합니다.

 

특징

1. 간선의 가중치 합이 최소

2. n개의 정점을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용해야 함

3. 사이클이 없어야 함

 

최소 스패닝 트리 관련 알고리즘

최소 스패닝 트리르 구하는 알고리즘에는 대표적으로 크루스칼과 프림이 있습니다.

 

크루스칼

그리디하게 모든 정점들을 최소 비용으로 연결해서 구하는 간선 선택 기반의 크루스칼 알고리즘은

가중치 값을 기준으로 오름차순 정렬하고 유니온파인드를 사용해서 사이클을 확인하는 것이 핵심입니다.

시간 복잡도는 O(ElogE) 입니다.

 

다음은 크루스칼 알고리즘을 자바로 구현한 코드입니다.

import java.io.*;
import java.util.*;
public class _kruskal {
    static int N, M;
    static int[] parents;
    static List<Node> list;
    static class Node implements Comparable<Node>{
        int s;
        int e;
        int d;
        public Node(int s, int e, int d){
            this.s = s;
            this.e = e;
            this.d = d;
        }

        @Override
        public int compareTo(Node o){
            return this.d - o.d;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        parents = new int[N+1];
        for(int i = 1 ; i <= N ; i ++) parents[i] = i;

        list = new ArrayList<>();
        for(int i = 1 ; i <= M ; i ++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            list.add(new Node(a, b, d));
        }

        Collections.sort(list);

        int listSize = list.size();
        int ans = 0;
        for(int i = 0 ; i < listSize ; i ++){
            Node curr = list.get(i);
            if(find(curr.s) != find(curr.e)){
                union(curr.s, curr.e);
                ans += curr.d;
            }
        }
        System.out.println(ans);
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if(x != y) parents[y] = x;
    }

    private static int find(int x) {
        if(x == parents[x]) return x;
        else return parents[x] = find(parents[x]);
    }

}

 

프림

임의의 정점에서 시작하여, 현재까지 연결된 정점들에 대해

가장 가중치가 작은 정점을 연결하는 정점 선택 기반의 알고리즘입니다.

 

트리의 집합을 단계적으로 확장하는 방식으로 구하며

최소힙을 이용해 구하는 방식이 다익스트라 알고리즘과 유사합니다.

우선순위 큐를 이용하여 가중치 값을 기준으로 오름차순 정렬합니다.

 

시간 복잡도는 O(N^2) 입니다.

 

다음은 프림 알고리즘을 자바로 구현한 코드입니다.

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static List<Node>[] graph;
    static boolean[] v;
    static class Node implements Comparable<Node>{
        int end;
        int dist;
        public Node(int end, int dist){
            this.end = end;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o){
            return o.dist - this.dist;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N+1];
        for(int i = 1 ; i <= N ; i ++) graph[i] = new ArrayList<>();

        for(int i = 1 ; i <= M ; i ++){
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            graph[s].add(new Node(e, d));
            graph[e].add(new Node(s, d));
        }

        int res = Integer.MIN_VALUE;
        res = Math.max(res, prim(1));

        boolean flag = true;
        for(int i = 1 ; i <= N ; i ++){
            if(!v[i]){
                flag = false;
                break;
            }
        }

        System.out.println(flag ? res : -1);
    }

    private static int prim(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        v = new boolean[N+1];
        int ans = 0;

        while(!pq.isEmpty()){
            Node currNode = pq.poll();
            int curr = currNode.end;

            if(v[curr]) continue;
            v[curr] = true;
            ans += currNode.dist;

            for(Node next: graph[curr]){
                if(!v[next.end]){
                    pq.offer(next);
                }
            }
        }
        return ans;
    }
}

 

크루스칼 VS 프림

크루스칼 알고리즘은 간선 선택 기반의 알고리즘이므로

간선의 수가 적은 희소 그래프에서 프림보다 유리합니다.

간선의 수가 적으면, 간선을 정렬하고 사이클 체크하는 과정에서 효율적이기 때문입니다.

 

여기서 희소그래프는 간선(E)의 수가 정점(V)의 수와 비슷한 정도인 그래프를 의미합니다.

대략 V <= E <= VlogV 정도.

 

이 경우가 아니라면, 정점 선택 기반의 프림 알고리즘이 유리합니다.