최소 스패닝 트리(MST, Minimum spanning tree)

최소 신장 트리라고도 한다.

 

그래프에서 최소 스패닝 트리를 만들기 위해선 다음 조건을 만족해야 한다.

1. 모든 정점은 연결돼있다.

2. 사이클이 없어야 한다.(트리 형태이기 때문)

3. 최소 가중치를 가진 무방향 간선들로만 연결돼야 한다. (간선의 개수는 정점의 개수 - 1 개)

 

즉, 모든 정점을 사이클 없이 최소한의 비용으로 연결해야 한다.

그림으로 올바른 형태와 잘못된 형태를 보면 다음과 같다.

 

모든 정점을 최소한의 비용으로 연결한단 특성 때문에

통신, 운송 네트워크 등 공급과 관련된 연결망을 구축하는 문제들이 많다.

 

 

스패닝 트리를 만드는 알고리즘은 크게 2가지가 있다.

각각 유리한 점이 있고, 특정 풀이를 쓰도록 강요하는 문제는 많이 없기 때문에 편한걸 쓰면 된다.

 

1. 크루스칼 알고리즘

가중치가 작은 간선들 순으로 우선순위 큐에 저장해 정점들을 연결한다.

유니온 파인드를 알고 있다면, 주로 이 알고리즘을 쓴다.

 

간선을 정렬하는데 O(logE)

큐에 담긴 모든 간선을 탐색하는데 O(E)만큼의 시간이 소모되므로,

총 시간 복잡도는 O(ElogE)가 된다. 

 

그림으로 나타내면 다음과 같다.

정점 (1, 2) 사이의 간선의 가중치가 제일 작으니, 이 둘을 연결한다.

그 다음 간선의 가중치가 작은 순서대로 연결한다.

정점 5에서 2를 연결하든 6을 연결하든 어느 한 쪽으로만 연결해준다면 어딜 연결해도 상관 없다.

여기선 정점 2에 연결함

마지막엔 정점 7과 8을 연결한다.

정점 8과 9 사이의 간선의 가중치가 5인데 연결하지 않은 것은

이미 8과 9는 트리에 속해있기 때문에 생략한다.

이 트리에 속했는지 여부를 유니온 파인드가 해준다.

 

코드는 접어놨다.

import java.util.*;

// 보통 간선은 이런 식으로 객체를 만든다.
class Edge implements Comparable<Edge> {
    int start, end, cost;

    public Edge(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    // cost 기준 오름차순으로 정렬한다.
    public int compareTo(Edge e) {
        return this.cost - e.cost;
    }
}

class Main {

    // 간선들의 정보가 담김
    static PriorityQueue<Edge> edges = new PriorityQueue<>();
    static int[] roots = new int[10];
    public static void main(String[] args) {
        init();
        kruskal();
    }

    private static void kruskal() {
        int edgeCount = 0, totalCost = 0;
        while (!edges.isEmpty()) {
            Edge here = edges.poll();
            if (union(here.start, here.end)) {
                totalCost += here.cost;
                System.out.printf("정점 %d, 정점 %d 연결, 총 비용 = %d\n",
                        here.start, here.end, totalCost);
                edgeCount++;
            }
            // 정점이 9개므로 간선은 8개만 있으면 된다.
            if(edgeCount == 8)
                break;
        }
    }

    private static boolean union(int s, int e) {
        s = find(s);
        e = find(e);
        if(s == e)
            return false;
        if(s != e)
            roots[e] = s;
        return true;
    }

    private static int find(int s) {
        if(roots[s] == s)
            return s;
        return roots[s] = find(roots[s]);
    }

    public static void init() {
        for (int i = 1; i < 10; i++) {
            roots[i] = i;
        }
        edges.add(new Edge(1, 2, 1));
        edges.add(new Edge(1, 4, 8));
        edges.add(new Edge(2, 3, 2));
        edges.add(new Edge(2, 5, 5));
        edges.add(new Edge(3, 6, 3));
        edges.add(new Edge(4, 5, 5));
        edges.add(new Edge(4, 7, 7));
        edges.add(new Edge(5, 6, 5));
        edges.add(new Edge(5, 8, 5));
        edges.add(new Edge(6, 9, 4));
        edges.add(new Edge(7, 8, 6));
        edges.add(new Edge(8, 9, 5));
    }
}

 

 

2. 프림 알고리즘

특정 정점부터 시작해 가중치가 작은 간선들 순으로 이어나간다.

다익스트라와 비슷한 구조를 보인다.

간선의 수가 많을 때 크루스칼에 비해 유리하다.

 

정점 1부터 시작할 때의 프림 알고리즘 진행 순서다.

크루스칼에선 5번째 탐색 때, 정점 2와 5를연결했지만,

프림 알고리즘에서 5번째 탐색 때는 정점 8을 기준으로 하기 때문에

정점 8과 5를 연결한다.

 

프림 알고리즘에선 문제가 하나 있는데

일반적으론 매 정점(V)마다 모든 간선(E)을 확인해야 하니

시간 복잡도는 O(V * E) 가 나온다.

그런데 위에 크루스칼에선 O(ElogE)인걸 보면, 상당히 비효율적이다.

그래서 따로 최적화를 거쳐 O(ElogV)로 만들어야 한다. (ex 우선순위 큐)

 

이 최적화 방법은 사람마다 다 다르니 한번 찾아보는걸 추천

 

코드는 접어놨다.

import java.util.*;

// 보통 간선은 이런 식으로 객체를 만든다.
// 원래는 start 변수는 필요 없지만 디버깅을 위해 넣음
class Edge implements Comparable<Edge> {
    int start, end, cost;

    public Edge(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    // cost 기준 오름차순으로 정렬한다.
    public int compareTo(Edge e) {
        return this.cost - e.cost;
    }
}

class Main {

    // 각 정점들에 연결된 간선 정보
    static ArrayList<Edge>[] graph = new ArrayList[10];
    // 간선들의 정보가 담김
    static PriorityQueue<Edge> edges = new PriorityQueue<>();

    public static void main(String[] args) {
        init();
        prim();
    }

    private static void prim() {
        // 정점들의 방문 정보를 담음
        boolean[] visit = new boolean[10];

        // 출발지(1)과 관련된 간선들 큐에 삽입
        for(Edge edge : graph[1])
            edges.add(edge);
        visit[1] = true;

        int edgeCount = 0, totalCost = 0;
        while (!edges.isEmpty()) {
            Edge here = edges.poll();
            // 해당 간선의 도착지가 이미 트리에 있다면 넘어감
            if(visit[here.end])
                continue;
            // 아니면 연결처리
            visit[here.end] = true;
            edgeCount++;
            totalCost += here.cost;
            System.out.printf("현재 정점 %d, 현재 정점 %d 총 비용 = %d\n",
                    here.start, here.end, totalCost);

            // 현재 정점과 연결된 간선들 탐색
            for (Edge there : graph[here.end]) {
                // 트리에 있는 간선이면 건너 뜀
                if(visit[there.end])
                    continue;
                edges.add(there);
            }
        }
    }

    public static void init() {
        for (int i = 1; i < 10; i++) {
            graph[i] = new ArrayList<>();
        }
        graph[1].add(new Edge(1, 2, 1));
        graph[2].add(new Edge(2, 1, 1));

        graph[1].add(new Edge(1, 4, 8));
        graph[4].add(new Edge(4, 1, 8));

        graph[2].add(new Edge(2, 3, 2));
        graph[3].add(new Edge(3, 2, 2));

        graph[2].add(new Edge(2, 5, 5));
        graph[5].add(new Edge(5, 2, 5));

        graph[3].add(new Edge(3, 6, 3));
        graph[6].add(new Edge(6, 3, 3));

        graph[4].add(new Edge(4, 5, 5));
        graph[5].add(new Edge(5, 4, 5));

        graph[4].add(new Edge(4, 7, 7));
        graph[7].add(new Edge(7, 4, 7));

        graph[5].add(new Edge(5, 6, 5));
        graph[6].add(new Edge(6, 5, 5));

        graph[5].add(new Edge(6, 8, 5));
        graph[8].add(new Edge(8, 6, 5));

        graph[6].add(new Edge(6, 9, 4));
        graph[9].add(new Edge(9, 6, 4));

        graph[7].add(new Edge(7, 8, 6));
        graph[8].add(new Edge(8, 7, 6));

        graph[8].add(new Edge(8, 9, 5));
        graph[9].add(new Edge(9, 8, 5));
    }
}