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

December 28, 2020 5 분 소요

신장 트리

신장 트리는 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리(사이클이 존재하지 않음)입니다.

사이클이 없으면서, 간선은 정점의 개수 - 1 개를 가집니다.

아래 사진의 세 그래프 모두 신장 트리를 나타냅니다.

최소 신장 트리

최소 신장 트리는 신장 트리 중에서도 사용된 간선들의 가중치의 합이 최소인 트리를 의미합니다.

최소 신장 트리는 다음과 같은 특징을 갖습니다.

무방향 가중치 그래프
그래프의 가중치 합이 최소여야 한다.
N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선을 사용해야 한다.
사이클을 포함해서는 안된다.

최소 신장 트리는 최소값이 같은 신장 트리가 여러 개 있을 수 있기에 두 개 이상 존재할 수 있습니다.

최소 신장 트리는 도로망, 통신망 등과 같은 분야에서 비용 최소화가 이익과 직결되는 부분에 적용할 수 있습니다.

크루스칼 알고리즘

크루스칼 알고리즘은 비용이 작은 간선을 하나씩 선택해 MST를 구성하는 알고리즘입니다. 간선이 적을 때 사용합니다.

동작 과정은 다음과 같습니다.

그래프의 간선들을 가중치의 오름차순으로 정렬합니다.
정렬된 간선 리스트에서 가중치가 적은 순서대로 사이클을 형성하지 않는 간선을 선택합니다.
1. 가중치가 가장 낮은 간선을 선택합니다.
2. 해당 간선으로 사이클이 형성되면, 버리고 다음 간선을 선택합니다.
해당 간선을 MST 집합에 추가합니다.
위 과정들을 (N-1)개의 간선이 선택될 때까지 반복합니다.

크루스칼 알고리즘은 O(ElogE)의 시간 복잡도를 갖습니다. 정점의 개수와는 상관 없이 간선의 개수가 영향을 주는 것을 알 수 있습니다. 따라서, 간선이 적을 때 사용하는 것이 적합합니다.

동작

1. 간선들을 가중치 기준 오름차순으로 정렬

2. 간선 2-3 을 선택

3. 간선 1-2 를 선택

4. 간선 1-3 은 사이클을 발생시킴

5. 간선 5-7 을 선택

6. 간선 3-6 을 선택

7. 간선 4-5 를 선택

8. 간선 1-6 은 사이클을 발생시킴

9. 간선 5-6 을 선택

10. 최종

간선을 추가했을 때 사이클이 생기는 지 확인할 때에 Union-find 알고리즘이 사용됩니다.

코드

package 최소신장트리;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Kruskal {
    static int[] parents;
    static int[] rank; // Union-Find의 효율성을 위해 트리의 깊이를 요소로 갖는 배열입니다.

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

        int V = sc.nextInt();
        int E = sc.nextInt();

        int[][] edges = new int[E][3];
        for (int i = 0; i < E; i++) {
            edges[i][0] = sc.nextInt(); // 시작 정점
            edges[i][1] = sc.nextInt(); // 도착 정점
            edges[i][2] = sc.nextInt(); // 가중치
        }

        // 간선들을 가중치 오름차순 정렬합니다.
        Arrays.sort(edges, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // o1[2] - o2[2]는 underflow나 overflow가 발생할 수 있으니 compare 메소드를 사용합니다.
                return Integer.compare(o1[2], o2[2]);
            }
        });

        // 각 정점에 대해 Union-Find 연산을 준비합니다.
        for (int i = 0; i < V; i++)
            makeSet(i);

        int cnt = 0;
        int result = 0;
        for (int i = 0; i < E; i++) {
            int a = findSet(edges[i][0]);
            int b = findSet(edges[i][1]);

            if (a == b) continue; // 같은 set에 속하면 패스합니다.

            union(a, b); // 같은 set에 속하지 않으면, 하나의 set으로 합쳐주고,
            result += edges[i][2]; // 간선을 선택하여 비용을 누적시킵니다.
            cnt++; // 간선 선택 횟수를 증가시킵니다.

            // (정점의 개수 - 1)번 반복하면 그만합니다.
            if (cnt == V - 1) break;
        }

        System.out.println(result);
    }

    static void makeSet(int x) {
        parents[x] = x;
    }

    static int findSet(int x) {
        if (parents[x] == x)
            return x;

        else
            return parents[x] = findSet(parents[x]);
    }

    static void union(int x, int y) {
        int px = findSet(x);
        int py = findSet(y);

        // 계층 구조를 유지하기 위해서는 깊이가 더 적은 트리를 더 깊은 트리의 루트 아래에 추가해야 깊이 증가가 없습니다.
        if (rank[px] > rank[py])
            parents[py] = px;
        else {
            parents[px] = py;

            if (rank[px] == rank[py]) {
                rank[py]++;
            }
        }
    }
}

프림 알고리즘

프림 알고리즘은 하나의 정점에서 연결된 간선들 중 하나씩 선택하면서 MST를 구성하는 알고리즘입니다. 간선이 많을 때 사용합니다.

정점을 하나씩 선택할 때마다 간선을 추가하면서 트리를 확장해나갑니다. 선택된 정점들을 트리 정점, 선택되지 않은 정점들을 비트리 정점이라고 합니다.

동작 과정은 다음과 같습니다.

임의의 정점 하나를 선택합니다.
선택된 정점들과 인접하는 정점들 중, 최소 비용의 간선이 존재하는 정점을 선택합니다.
모든 정점이 선택될 때까지 위 1, 2를 반복합니다.

프림 알고리즘은 O(v^2)의 시간 복잡도를 갖습니다. 정점의 개수에 비해 간선의 개수가 많을 때 사용하는 것이 적합합니다.

동작

1. 부모를 기억하는 π 배열, 부모로부터의 간선 비용을 저장하는 key 배열을 사용

π 배열 : 부모의 정점 번호

key 배열 : 해당 부모로부터 나 자신까지 오는 데의 비용

key 값들 중에 가장 작은 값을 다음 정점으로 선택합니다.

2. 정점 1을 선택합니다.

정점 1을 선택함으로써, 정점 1과 연결된 정점들로의 비용을 갱신합니다.

3. 정점 2를 선택합니다.

정점 3으로 가는 더 짧은 길이 생겼으므로, 해당 key 값을 변경합니다.

4. 정점 3을 선택합니다.

정점 6으로 가는 새로운 짧은 길이 생겼으므로, 해당 key 값을 변경합니다.

5. 정점 6을 선택합니다.

정점 6이 선택되면서 정점 4로 가는 비용이 기존 정점 2로부터 드는 19보다, 정점 6으로부터 가는 11이 더 작으므로, 갱신합니다.

또한 정점 5로도 갈 수 있으므로, π 및 key 값을 갱신해줍니다.

6. 정점 5를 선택합니다.

정점 5를 선택함으로써, 정점 4로가는 비용이 더 작아지므로, 정점 4에 대한 π 및 key 값을 업데이트 합니다.

또한 새롭게 정점 7로 갈 수 있게 되면서 정점 7에 대한 π 및 key 값을 변경합니다.

7. 정점 7을 선택합니다.

정점 7이 선택되어도 더 적은 비용으로 갈 수 없으므로, 값이 변경되지 않습니다.

8. 정점 4를 선택합니다.

9. 최종

key 값들을 더하면, 최소 비용이 됩니다.

코드

package 최소신장트리;

import java.util.Arrays;
import java.util.Scanner;

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

        int V = sc.nextInt();
        int E = sc.nextInt();

        int[][] adj = new int[V][E];

        for (int i = 0; i < E; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            adj[a][b] = adj[b][a] = c;
        }

        boolean[] check = new boolean[V];
        int[] key = new int[V];
        int[] pi = new int[V];

        Arrays.fill(key, Integer.MAX_VALUE);

        // 맨 처음 정점을 선택합니다. 처음 선택되는 정점이 루트이므로 부모는 없고, 거리는 0으로 설정합니다.
        pi[0] = -1;
        key[0] = 0;

        for (int i = 0; i < V - 1; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;

            for (int j = 0; j < V; j++) {
                if (!check[j] && key[j] < min) {
                    index = j;
                    min = key[j];
                }
            }

            // index : 선택이 안된 정점 중 key 값이 가장 작은 정점의 번호
            check[index] = true;

            // index 정점에서 출발하는 모든 간선에 대해서 key를 업데이트 해줍니다.
            for (int j = 0; j < V; j++) {
                // check가 안되어있으면서, 간선은 존재하고, 그 간선의 비용이 key 값보다 작다면, key 값을 업데이트 해줍니다.
                if (!check[j] && adj[index][j] != 0 && key[j] > adj[index][j]) {
                    pi[j] = index;
                    key[j] = adj[index][j];
                }
            }
        }

        int result = 0;
        for (int i = 0; i < V; i++)
            result += key[i];

        System.out.println(result);
        System.out.println(Arrays.toString(pi));
    }
}

Twitter Facebook LinkedIn

김무성