[개념 학습 및 정리] 기초 그래프 알고리즘 (최소 신장 트리)

1. 최소 스패닝 트리

1) 최소 스패닝 트리

우선 최소 스패닝 트리는 그래프의 모든 노드를 포함하는 트리이다. 한 가지 그래프가 있을 때, 여러가지 스패닝 트리가 존재할 수 있으며, 한 가지 스패닝 트리에서 선택된 간선의 가중치의 합이 해당 스패닝트리의 가중치를 정의할 수 있다. 이 과정에서 모든 스패닝 트리중에서 가중치가 가장 작은 스패닝 트리를 물어보는것이 최소 신장 트리, 최소 스패닝 트리라고 한다. 즉, 그래프의 모든 노드를 포함하는 트리중 간선의 가중치의 합이 최소인 트리를 뜻한다.

2) Cut Property

Cut Property는 최소 스패닝 트리에서 정리하는 과정을 뜻한다. 그래프를 잘라, 노드를 두 그룹으로 나누고(Cut), 두 개의 트리를 잇는 간선 중, 가중치가 가장 작은 것을 기준으로 합쳐 최소 스패닝 트리로 만드는 것을 뜻한다.

3) 크루스칼 알고리즘

크루스칼 알고리즘은 각 노드를 하나의 최소 스패닝 트리로 보고 시작한다. 쉽게 말한다면 가장 작은 가중치를 가진 간선을 색칠하는 알고리즘이다. 단, 해당 과정에서 트리내에 사이클이 생겨서는 안된다는 점을 주의해야한다.

 

구현할 때 고려해야하는 부분은 두 가지가 있다.

• 간선 가중치 순으로 정렬하는 것이 어렵다.
• 사이클 확인하는 것에 대한 고찰이 필요하다.

4) disjoint set

C에서는 disjoint set 자료구조를 이용하여 트리의 사이클 존재 유무를 확인한다.

 

1. 모든 정점들이 각각의 개인적인 그룹으로 각자가 루트이다.

2. 정점 1과 2를 묶어 트리를 만든다.

3. 정점 3과 4를 묶어 트리를 만든다.

4. 두 개의 정점이 같은 그룹인지 확인하는 방법은 각각의 정점의 대표(루트)를 비교를 통해서 알 수 있다.

- 4와 6이 같은 그룹인가? : 4의 대표인 '3'과 6의 대표인 '6'이 다르므로 동일 그룹이 아니다.

- 2와 4가 같은 그룹인가? : 2의 대표인 '1'과 4의 대표인 '3'이 다르므로 동일 그룹이 아니다.

5. 두 개의 그룹을 합칠 경우에는, 각 그룹의 대표(루트)를 구하고 하나의 대표를 다른 대표의 자식으로 넣어 하나의 트리로 만든다. 

- 1과 4를 합친다면? : 1과 4를 이을 수 있지만, 1이 속한 트리의 정점인 '1'과 4가 속한 트리의 정점인 '3'을 묶는다.

- 2와 4가 같은 그룹인가? : 2의 대표는 '1', 4의 대표는 '1'이 되므로 동일 그룹이다.

5) 크루스칼 동작과정

그래프와 그룹을 의미하는 그림이 있을 경우의 크루스칼 동작과정은 다음과 같다.

1. 1과 6의 간선을 이어도 되는가? (사이클이 생기는가?)

- 1과 6은 다른 그룹이기에 가능

2. 2와 3의 간선을 이어도 되는가?

3. 3과 7의 간선을 이어도 되는가?

4. 3과 5의 간선을 이어도 되는가?

5. 5와 7의 간선을 이어도 되는가?

- 5와 7은 같은 그룹에 속하며, 이을 경우 사이클이 생기기에 불가능

6. 7과 8의 간선을 이어도 되는가?

7. 4와 5의 간선을 이어도 되는가?

8. 두 개의 그룹의 대표(루트)를 이용하여 합쳐 최소 패닝 트리를 완성한다.

5) 구현

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

class Edge implements Comparable<Edge>{
    private int from;
    private int to;
    private int dis;

    public Edge(int from, int to, int dis) {
        this.from = from;
        this.to = to;
        this.dis = dis;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.dis, o.dis);
    }

    // x가 속한 그룹의 대표 찾기
    public int findSet(int[] p, int x) {
        if(p[x] == x) return x;
        else return p[x] = findSet(p, p[x]);
    }

    // x와 y 그룹을 합치기
    public void union(int[] p, int x, int y) {
        if(x < y) p[findSet(p, y)] = findSet(p, x);
        else p[findSet(p, x)] = findSet(p, y);
        
        // p[2] = 1 이라는 뜻은, 2번 노드의 대표가 1이라는 뜻
    }

    public int getFrom() {
        return from;
    }

    public int getTo() {
        return to;
    }

    public int getDis() {
        return dis;
    }
}

public class Main {

    private static int node;
    private static int edge;

    private static int[] p; // 정점을 저장할 배열
    private static PriorityQueue<Edge> pq;

    private static int count; // 지나간 노드의 수
    private static int sum; // 최소 패닝 트리 간선의 합

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());

        p = new int[node+1];
        for(int i = 1; i < node+1; i++) { // 0부터 node개의 정점 저장
            p[i] = i;
        }

        pq = new PriorityQueue<>();
        for(int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            pq.add(new Edge(a, b, w));
        }

        while(!pq.isEmpty()) {
            Edge edge = pq.poll();

            // from 노드와 to 노드의 대표가 같지 않을 경우
            if(edge.findSet(p, edge.getFrom()) != edge.findSet(p, edge.getTo())) {
                sum += edge.getDis();

                // 모든 정점을 돌았을 경우
                if(++count == node) break;

                // from 노드와 to 노드 합치기
                edge.union(p, edge.getFrom(), edge.getTo());
            }

        }

        bw.write(sum + "");

        bw.flush();
        bw.close();
        br.close();
    }

}
/*
예제 입력
8 10
1 2 1
1 3 2
2 3 3
2 4 4
4 5 1
4 6 2
5 6 2
5 8 2
6 7 3
7 8 4

예제 출력
15
 */