[알고리즘] MST (최소 신장 트리, Minimum Spanning Tree)

MST (최소 신장 트리, Minimum Spanning Tree)

 

 

1. MST

그래프의 모든 정점을 연결할 때, 모든 정점을 간선으로 연결하며 싸이클은 존재하지 않고, 연결된 간선들의 가중치의 합은 최소가 되는 것을 말한다.

 

+) Spanning Tree : 그래프 내 모든 정점을 포함하는 트리

+) 정점 : V ,  간선 : E

 

 

2. Kruskal's Algorithm | 크루스칼 알고리즘

- 간선 선택 기반

- 시간복잡도 : O(ElogV)

    ㄴ 간선 정렬 : O(ElogE)

    ㄴ Unifon Find : O(1) * E = O(E)

    O(ElogE + E) => O(ElogV^2),  (E <= V^2, fully connected graph) => O(ElogV)

 

 

1) 간선 리스트의 가중치들을 오름차순으로 정렬

2) 가중치가 작은 간선 선택

3) union-find를 이용하여 부모가 같지 않으면 연결 (싸이클이 생기지 않도록)

 

 

+) Union-Find

https://void2017.tistory.com/304

[알고리즘] Union-Find (유니온 파인드)

 

 

예시 코드 - [프로그래머스] 섬 연결하기

import java.util.*;
class Solution {
   static int[] parent;
    static int find(int x) {
        if(x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
 
    static void union(int x, int y) { // y > x
        x = find(x);
        y = find(y);
 
        if(x != y) parent[y] = x;
    }
 
    static int solution(int n, int[][] costs) {
        int answer = 0;
        // 1) 간선 리스트의 가중치를 기준으로 오름차순 정렬
        Arrays.sort(costs, Comparator.comparingInt(o -> o[2]));
 
        // union-find (parent[] init)
        parent = new int[n];
        for(int i = 0; i < n; i++) parent[i] = i;
 
        // 2) 가중치가 작은 간선부터 선택
        for(int i = 0; i < costs.length; i++) {
            int start = costs[i][0];
            int end = costs[i][1];
            int weight = costs[i][2];
 
            // 3) 부모노드가 같지 않은 경우 연결
            if(find(start) != find(end)) {
                if(start > end) {
                    int tmp = end;
                    end = start;
                    start = tmp;
                }
                union(start, end);
                answer += weight;
            }
        }
 
        return answer;
    }
}

+) 간선이 적으면 크루스칼!

 

 

3. Prim's Algorithm | 프림 알고리즘

- 정점 선택 기반 

- 시간복잡도 : O(ElogV) - 이진 힙 // 배열을 사용한다면 O(V^2)

    ㄴ 모든 정점 우선 순위 큐로 확인 : O(logV)

    ㄴ 간선 확인 : O(E)

    ㄴ O(ElogV)

 

 

1) 임의의 정점을 하나 선택

2) 정점에서 가중치가 낮은 간선을 선택

3) 모든 정점을 방문할 때까지 반복

 

 

예시 코드 - [프로그래머스] 섬 연결하기

import java.util.*;
class Solution {
 static class Edge {
        int target;
        int weight;
 
        public Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }
    static int solution(int n, int[][] costs) {
       int answer = 0;
        // 가중치 오름차순 정렬
        PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        List<List<Edge>> list = new ArrayList<>();
 
        // init
        for(int i = 0; i <= n; i++) list.add(new ArrayList<>());
 
        for(int i = 0; i < costs.length; i++) {
            list.get(costs[i][0]).add(new Edge(costs[i][1], costs[i][2]));
            list.get(costs[i][1]).add(new Edge(costs[i][0], costs[i][2]));
        }
 
        boolean[] vtd = new boolean[n];
 
        //임의의 정점 하나 선택
        pq.add(new Edge(0,0));
        
        while(!pq.isEmpty()) {
            Edge e = pq.poll();
            if(vtd[e.target]) continue;
            vtd[e.target] = true;
            answer += e.weight;
 
            for(Edge edge: list.get(e.target)) {
                if(!vtd[edge.target]) pq.add(new Edge(edge.target, edge.weight));
            }
        }
 
        return answer;
    }
 
}

+) 간선이 많으면 프림!

 

 

4. 참고 문제

1) [백준] 최소 스패닝 트리

https://void2017.tistory.com/100

[백준] 1197 최소 스패닝 트리

 

2) [프로그래머스] 섬 연결하기

https://void2017.tistory.com/306

[프로그래머스] 섬 연결하기