February 12, 2022 11 min to read

mst(최소스패닝트리)

최소신장트리는 ‘그래프에서 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리’를 뜻한다. MST(minimum spanning tree)의 줄임말이다. 한마디로 모든 정점을 연결하는데 간선의 cost가 최소가 될 때를 찾는 알고리즘이다. 그렇기 때문에 방향이 없는 그래프에서 사용된다. 사용되는 경우는 다음과 같다

mst가 사용되는 경우

모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
두 정점 사이의 최소 비용 경로 찾기

신장트리

n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간서으로 이루어진 트리

mst

무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

MST 표현

그래프
간선들의 배열
인접리스트
부모 자식관계와 가중치에 대한 배열

MST 알고리즘은 Prim, Kruskal 2개가 있다. 프림, 크루스칼 알고리즘을 하나씩 살펴볼 건데 각각 어떤 차이가 있고 어떤 경우에 시간복잡도가 더 낮은지 한변 살펴보자 프림: O(ElogV) 간선 많을 때

Prim

임의 정점을 하나 선택해서 시작
선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점을 선택
모든 정점이 선택될 때 까지 1,2를 반복

핵심은 Priority Queue를 이용한 최소 합으로 구현하는 것이다. 한 정점에서 아직 연결되지 않은 정점들에 대해 간선을 pq에 추가해준다. 시간 복잡도는

모든 간선 E * 간선을 통해 삽입된 정점의 가중치 정렬 logV = O(ElogV)
프림 알고리즘은 간선의 수가 많을 때 더 효과적인 알고리즘이다.

Prim 알고리즘

Q <- G.V                    // 우선순위 Q에 모든 정점 넣는다

MST_PRIM(G, r)          // G: 그래프, r: 시작 정점
    result = 0, cnt = 0         // result: 신장트리 최소 비용,cnt: 처리한 정점 수, visited[]: 최소신장트리 구성에 포함된 정점여부
    FOR u in G.V
        minEdge[u] = INF        //minEdge[]: 각 정점기준으로 다른 정점과의 간선 중 최소비용
    minEdge[r] = 0              // 시작정점 r의 최소비용 0 처리

    WHILE Q != empty            // 빈 Q가 아닐동안 반복
        u = Extract_MIN(Q)      // 방문하지 않은(mst에 포함되지 않은 정점) 최소비용 정점 찾기
        visited[u] = true       // 방문처리
        result += minEdge[u]    // 비용누적
        if(++cnt == N)  break;  // 모든 정점이 다 연결되었으면 최소신장트리 완성
        FOR v in G.Adj[u]       // u의 인접 정점들 탐색
            IF !visited[v] AND w(u, v) < minEdge[v] // u에서 v로의 비용이 v의 최소비용보다 작다면 갱신
                minEdge[v] = w(u, v)

백준에서 MST 대표 문제인 1197번 최소 스패닝 트리를 Prim을 이용해 풀어보자. https://www.acmicpc.net/problem/1197

package boj;

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

public class boj_1197 {
    static class Node implements Comparable<Node>{
        public int to, cost;
        public Node(int to, int cost){
            this.to = to;
            this.cost = cost;
        }
        public int compareTo(Node o){
            return this.cost - o.cost;
        }
    }

    static int V, E;    // 정점 갯수, 간선 갯수
    static LinkedList<Node> list[];   // 정점 연결하는 연결리스트
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        //연결리스트 초기화
        list = new LinkedList[V+1];
        for(int i=1; i<=V; i++)
            list[i] = new LinkedList<>();

        for(int i=0; i<E; i++){
            st = new StringTokenizer(in.readLine());
            // 각 정점별 간선, 가중치를 노드로 저장해 연결리스트 만들기
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            list[from].add(new Node(to, cost));
            list[to].add(new Node(from, cost));
        }
        System.out.println(prim());
    }

    public static int prim(){
        // 가중치 누적합, mst에 포함된 정점 개수
        int result = 0, cnt = 0;

        // 간선 가중치가 작은 순대로 우선순위큐에 저장
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[V+1];   // 정점이 mst에 속해있는지 표시
        int[] minEdge = new int[V+1];       // 정점별 최소값 저장
        Arrays.fill(minEdge, Integer.MAX_VALUE);    // 정점을 무한대값으로 초기화

        pq.offer(new Node(1, 0));   // 정점 1부터 출발
        minEdge[1] = 0;

        while(!pq.isEmpty()){
            Node minNode = pq.poll();   // 간선값 최소인 정점 poll
            if(visited[minNode.to]) continue;   //만약 이미 mst에 포함된 정점이면 continue

            visited[minNode.to] = true;
            result += minNode.cost;     // 정점 cost를 누적으로 더해주기
            if(++cnt == V)  break;      // mst에 포함된 정점 개수가 V면 탐색 종료

            // 현재 정점에 연결된 다른 정점들 탐색. pq에 넣기
            for(Node node : list[minNode.to]){
                if(!visited[node.to] && node.cost < minEdge[node.to]){
                    minEdge[node.to] = node.cost;
                    pq.offer(new Node(node.to, node.cost));
                }
            }
        }
        return result;
    }
}

Kruskal

간선을 하나씩 선택해서 MST를 찾는 알고리즘이다. 모든 간선을 가중치 기준으로 오름차순해서 정렬하고, 이 간선들을 순서대로 모든 정점이 연결될 때 까지 연결하는 것이다. 핵심은 Union-Find 알고리즘을 이용해서 구현하며, 이를 통해 사이클이 형성되지 않으면 정점을 연결할 수 있다.

처음에 모든 간선을 가중치에 따라 오름차순으로 정렬한다.(우선순위큐에 저장)
가중치가 가장 낮은 간선부터 선택한다. union-find 기법으로 사이클이 존재하면 pass한다.
n-1개의 간선이 선택될 때 까지 반복한다.

크루스칼은 우선수위큐에서 간선의 가중치를 정렬하는 로직의 시간과 동일하다. 퀵 정렬의 시간 복잡도 = O(ElogE) 그러므로 간선이 적을 때는 크루스칼이 적합하다.

Union-Find

하나의 집합을 하나의 트리로 표현하는 방법이다. 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 이를 통해 부모 노드가 같으면 사이클이 생겼다는 것을 판단할 수 있다.

Make-Set(x): 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산

Make-Set(x)
    p[x] = x;

Find_Set(x): x를 포함하는 집합을 찾는 연산

Find-Set(x)
    IF x == p[x]: return x
    ELSE: return p[x] = Find-Set(p[x])

Union(x,y): x와 y를 포함하는 두 집합을 통합하는 연산

Union(x,y)
  IF Find-Set(y) == Find-Set(x) return;
  p[Find-Set(y)] = Find-Set(x)

크루스칼 알고리즘

MST_KRUSKAL(G, w)
    FOR vertex v in G.V     // G.V: 그래프의 정점 집합
        Make_Set(v)         // G.E: 그래프의 간선 집합

    G.E에 포함된 간선들을 가중치 w에 의해 정렬

    FOR 가중치가 가장 낮은 간선 (u, v) in G.E 선택(n-1)
        IF Find_Set(u) != Find_Set(v)
            가중치 합
            Union(u, v);

백준 1197을 kruskal로 풀 경우

package boj;

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

public class boj_1197_kruskal {
    static class Node implements Comparable<Node>{
        public int from, to, cost;
        public Node(int from, int to, int cost){
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
        public int compareTo(Node o){
            return this.cost - o.cost;
        }
    }
    // 부모 노드 찾기
    public static int find_set(int a){
        if(a == parent[a])  return a;
        else    return parent[a] = find_set(parent[a]);
    }

    //union
    public static void union(int a, int b){
        int aroot = find_set(a);
        int broot = find_set(b);
        parent[broot] = aroot;
    }

    static int V, E;    // 정점 갯수, 간선 갯수
    static PriorityQueue<Node> pq;
    static int[] parent;    // 부모 노드 저장
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        // 간선 저장할 우선순위 큐
        pq = new PriorityQueue<Node>();
        for(int i=0; i<E; i++){
            st = new StringTokenizer(in.readLine());
            // 각 정점별 간선, 가중치를 노드로 저장해 연결리스트 만들기
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            pq.offer(new Node(from, to, cost));
        }
        // parent 초기화
        parent = new int[V+1];
        for(int i=1; i<=V; i++)
            parent[i] = i;

        System.out.println(kruskal());
    }

    public static int kruskal(){
        int result = 0, cnt = 0;

        while(!pq.isEmpty()){
            Node node = pq.poll();
            if(find_set(node.from) != find_set(node.to)){
                cnt++;
                result += node.cost;
                union(node.from, node.to);
            }
            if(cnt == E-1)  break;
        }
        return result;
    }
}

SongFlix v3.1.1

mst(최소스패닝트리)

mst가 사용되는 경우

신장트리

mst

MST 표현

Prim

Prim 알고리즘

Kruskal

Union-Find

크루스칼 알고리즘

백준 14172 넴모넴모(java)

Comments

mst(최소스패닝트리)

mst가 사용되는 경우

신장트리

mst

MST 표현

Prim

Prim 알고리즘

Kruskal

Union-Find

크루스칼 알고리즘

백준 14172 넴모넴모(java)

Share

Comments