최소 신장 트리(Minimum Spanning Tree)

최소 신장트리란

최소 신장 트리(Minimum Spanning Tree)는 가중치가 있는 무방향 그래프의 모든 노드를 포함하면서 사이클이 없고 가중치의 합이 최소가 되는 트리입니다.

< MST의 예제, 출처 : https://en.wikipedia.org/wiki/Minimum_spanning_tree >

연결그래프가 주어질 때, MST를 구하는 알고리즘은 대표적으로 크루스칼, 프림 2가지가 있습니다.
두 알고리즘은 비슷한 시간 복잡도를 가지지만 나름의 장, 단점이 있으므로 모두 알아봅시다.

1. 프림 알고리즘

프림 알고리즘은 일단 시작점을 아무 정점을 선택하고, 이는 MST를 구성하는 첫 원소가 됩니다.
그리고 현재까지 구성된 MST의 원소(시작점)에 연결된 간선 중 가장 가중치가 작은 값을 가지는 간선을 골라 이어준 후 MST의 원소로 추가합니다.

그리고 MST가 완벽하게 완성될 때까지 현재까지 구성된 MST의 원소들에 연결된 간선 중 가장 가중치가 작은 값을 고른 후 이 정점을 MST의 원소에 추가해주면 됩니다.

시작점 1을 기준으로 연결된 간선 중 최소 가중치인 3번 노드 선택 (주황색 간선은 MST의 원소와 연결된 간선)

3번 노드를 MST의 원소로 추가, 가중치 최소인 4번 노드 선택

4번 노드를 MST의 원소로 추가, 가중치 최소인 6번 노드 선택

6번 노드를 MST의 원소로 추가, 가중치 최소인 5번 노드 선택

5번 노드를 MST의 원소로 추가, 가중치 최소인 2번 노드 선택

MST 완성, 총 비용은 21

이를 인접행렬로 구현시, G(V, E)에 대해 시간 복잡도 O(V^2)를 가집니다.
이는 이진힙 또는 우선순위 큐를 사용하면 O(E log V)의 시간 복잡도를 가집니다.

 

2. 크루스칼 알고리즘

크루스칼 알고리즘은 먼저 모든 간선을 간선 값으로 오름차순 정렬합니다.
그리고 각 정점에 번호를 부여합니다. 이 번호는 각 정점의 그룹 정보를 의미합니다.
그 후 정렬된 간선들을 탐색하면서 간선의 시작점과 도착점이 이어져있는지를 그룹 정보를 다루는 Disjoint-set 알고리즘을 이용해 확인합니다.
만약 두 정점이 같은 그룹으로 이어져 있다면 다음 간선을 탐색합니다.
같은 그룹으로 이어져 있지 않다면 디스조인트-셋 자료구조의 병합 과정을 거쳐 두 그룹을 합칩니다.
이를 반복하면 MST가 완성됩니다.

최소 가중치 간선을 선택합니다. 두 정점은 다른 그룹(색)이기 때문에 디스조인트-셋 자료구조를 사용하여 하나의 그룹으로 만들어 줍니다.

하나의 색으로 만들어 준 후, 다음 최소 가중치 간선을 선택한 후, 하나의 그룹으로 만듭니다. 아래도 똑같이 진행합니다.

마지막으로 2를 이어줍니다.

MST가 완성되었습니다. 총 비용은 21입니다.

예시 코드

아래는 위의 알고리즘들을 사용하여 작성한 프로그램입니다.

입력	출력
첫째 줄에 정점의 수 자연수 n과 간선의 수 자연수 m이 주어진다. 두 번째 줄 ~ m + 1번째 줄까지는 간선의 정보인 정수 X, Y, COST가 차례로 주어진다. 이는 X와 Y를 잇는 가중치가 COST인 간선이 존재한다는 의미이다.	MST를 만드는 최소비용을 출력한다.
Sample Input	Sample Output
6  8 1  2  7 1  3  3 2  4  10 3  4  1 3  5  6 3  6  10 4  5  13 5  6  4	21

Java (Kruskal)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Node implements Comparable<Node> {
    int x, y, z;

    public Node() {}
    public Node(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    @Override
    public int compareTo(Node arg0) {
        return this.z - arg0.z;
    }
}

public class Main {
    static int uf[];

    static int disjoint(int x) {
        if(x != uf[x]) return uf[x] = disjoint(uf[x]);
        else return x;
    }

    public static void main(String[] args) {
        ArrayList<Node> Edges = new ArrayList<Node>();

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        uf = new int[n + 1];

        for (int i = 1; i <= n; i++)
            uf[i] = i;
        for (int i = 0; i < m; i++)
            Edges.add(new Node(sc.nextInt(), sc.nextInt(), sc.nextInt()));

        Collections.sort(Edges);

        long ans = 0;

        for (int i = 0; i < m; i++) {
            int x = Edges.get(i).x, y = Edges.get(i).y;
            if (disjoint(y) != disjoint(x)) {
                uf[disjoint(y)] = uf[x];
                ans += Edges.get(i).z;
            }
        }
        System.out.println(ans);
    }
}

Java (Prim)

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

class Node implements Comparable<Node> {
    int x, y;

    public Node() {}

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Node arg0) {
        return this.y - arg0.y;
    }
}

public class Main {
    int v[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList<Node> g[] = new ArrayList[10005];
        PriorityQueue<Node> pq = new PriorityQueue<Node>();

        for (int i = 1; i <= n; i++)
            g[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            g[x].add(new Node(y, z));
            g[y].add(new Node(x, z));
        }

        int s = 1, ans = 0;
        int v[] = new int[n + 1];

        for (int i = 0; i < n - 1; i++) {
            v[s] = 1;
            for (int j = 0; j < g[s].size(); j++) {
                pq.add(g[s].get(j));
            }
            while (v[pq.element().x] == 1) {
                pq.remove();
            }
            ans += pq.element().y;
            s = pq.peek().x;
            pq.remove();
        }
        System.out.println(ans);
    }
}