최소 신장 트리 (MST)

2020. 6. 27. 17:02Computer Science/Algorithm

https://towardsdatascience.com/prims-minimum-spanning-tree-implementation-b78a5bf5e92c

 

 

Overview

 

최소 신장 트리(Minimum Spanning Tree | MST)란 한 그래프에 속해 있는 모든 정점을 잇는 최소 비용의 부분 그래프를 의미합니다. 다시 말해서, 가장 적은 비용으로 모든 정점들을 이어주는 그래프를 의미하는 것입니다. 네트워크 장비에 관한 포스팅에서 스위치(네트워크 장비)를 통해 여러 개의 컴퓨터들을 연결하는 과정에 대해서 살펴보았습니다. 이 때, 컴퓨터 사이에 두 개 이상의 네트워크 경로가 존재할 경우, 네트워크 루핑 현상이 발생할 수 있으며, 이를 막기 위해 스위치는 스패닝 트리 프로토콜을 통해 컴퓨터와 컴퓨터 사이에는 단 하나의 루트만 존재하게끔 조정해 줍니다.

 

 

이 스패닝 트리 프로토콜이 바로 최소 스패닝 트리와 밀접하게 연관되어 있습니다. 최소 신장 트리는 최소 비용(네트워크 상에서는 전송속도와 물리적 거리를 의미할 것입니다.)으로 모든 정점들 사이를 연결하며, 정점과 정점 사이에는 경로가 오직 하나임이 보장되기 때문입니다. 이번 포스팅에서는 이 최소 신장 트리 알고리즘으로 널리 알려져 있는 크루스칼 알고리즘과, 프림 알고리즘을 알아보도록 하겠습니다,

 

 

최소 신장 트리

 

- 최소의 비용으로 모든 정점들을 이어준다.

- 정점과 정점 사이의 경로가 단 하나 존재한다.

- 그래프 내에 사이클이 존재하지 않는다.

 

 

크루스칼 알고리즘

 

크루스칼 알고리즘이 갖는 아이디어는 우선 간선의 가중치가 작은 순서대로 간선들을 정렬하고, 이 간선들을 하나씩 붙여가면서 최소 신장 트리를 완성하자는 것입니다. 단, 간선의 가중치가 낮다고 해서 무조건 추가하게 될 경우 그래프 내에 사이클이 생기거나, 정점과 정점 사이의 경로가 2개 이상인 경우, 즉 최소 신장트리의 조건을 만족하지 못하는 경우가 생기게 됩니다. 따라서 다음과 같은 방식으로 진행합니다.

 

 

1. 간선의 가중치가 작은 순서대 로 간선들을 정렬한다. 

2. 가중치가 가장 작은 간선을 뽑고, 간선의 양 끝 정점을 잇는 다른 경로가 이미 존재하는지를 확인한다.

3. 존재하는 경우, 해당 간선을 무시한다. (이미 경로가 있으므로)

4. 존재하지 않는 경우, 해당 간선을 추가하고, 두 정점과 간선을 최소 신장 트리에 추가한다.

5. 모든 정점이 방문될 때까지 이를 반복한다. 

 

 

여기서 2번 항목, 간선을 추가하려고 할 때, 간선의 양 끝 정점을 잇는 다른 경로가 이미 존재하는 지를 확인하기 위해서 크루스칼 알고리즘에서는 상호배타적 집합(Disjoint Set)을 계산하는 Union-find를 사용합니다. Union-find는 같은 그래프에 속해 있는 서로 다른 두 정점에 대해서 같은 결과(parent node의 인덱스)를 반환하기 때문에 두 간선이 이미 같은 그래프에 속해 있는 지를, 즉 두 간선을 잇는 경로가 이미 존재하는지를 확인하는데에 사용할 수 있습니다.

 

 

소스 코드(JAVA)

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

public class Kruskal {
    public static int[] parent;
    public static ArrayList<Edge> edgeList;

    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 token = new StringTokenizer(br.readLine());

        int v = Integer.parseInt(token.nextToken());
        int e = Integer.parseInt(token.nextToken());
        // 각각 정점이 공통된 집합에 속해 있는지를 알아보기 위한 parent 배열
        parent = new int[v];
        // 모든 간선의 집합. compareTo를 구현하여 가중치가 작은 순서대로 정렬한다.
        edgeList = new ArrayList<Edge>();

        for(int i=0;i<v;i++) parent[i] = i;
        for(int i=0;i<e;i++){
            token = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(token.nextToken()) - 1;
            int end = Integer.parseInt(token.nextToken()) - 1;
            int val = Integer.parseInt(token.nextToken());
            edgeList.add(new Edge(start, end, val));
        }
        Collections.sort(edgeList);

        long sum = 0;
        long max = 0;
        for(int i=0; i<edgeList.size(); i++){
            Edge edge = edgeList.get(i);
            if(!isSameParent(edge.v1, edge.v2)) {
                sum += edge.cost;
                if(max < edge.cost) max = edge.cost;
                union(edge.v1, edge.v2);
            }
        }

        bw.write((sum - max)+"\n");
        bw.flush();
        bw.close();
    }

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x != y) parent[y] = x;
    }

    public static int find(int x) {
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    public static boolean isSameParent(int x, int y) {
        return find(x) == find(y);
    }
}

class Edge implements Comparable<Edge> {
    int v1, v2, cost;
    Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        if (this.cost < o.cost) return -1;
        else if(this.cost == o.cost) return 0;
        else return 1;
    }
}

 

Time Complexity

 

크루스칼 알고리즘은 가중치에 따라서 모든 간선들을 정렬한 후에, 간선의 개수만큼 Loop를 돌면서 신장 트리를 완성하는 방식이므로 모든 간선들을 정렬하는데 걸리는 시간이 전체 알고리즘의 시간복잡도인  O(ElogE)가 됩니다.

 

프림 알고리즘

 

프림 알고리즘은 앞서 설명한 크루스칼 알고리즘과 비슷하지만 조금은 다른 방법을 사용합니다. 그래프의 모양과는 상관없이 모든 간선을 가중치 순으로 먼저 정렬한 뒤에 간선을 끼워 맞추는 식으로 작동하는 크루스칼 알고리즘과는 다르게, 프림 알고리즘은 시작 정점에 붙어있는 간선들 만을 가중치 순으로 먼저 정렬한 뒤에 다음 정점을 추가하는 방식으로 작동합니다. 다음 정점을 추가한 뒤에는 추가된 정점들에 붙어있는 모든 간선들을 기준으로 가장 가중치가 낮은 간선을 뽑아 또 정점을 추가하는 과정을 반복합니다. 

 

이렇게 트리를 만들어가면서 해당 트리에 붙어있는 간선들만을 기준으로 트리에 정점을 추가하기 때문에 프림 알고리즘을 사용하면, 트리 생성의 중간 단계를 볼 수 있다는 장점이 있습니다.

 

1. 시작 정점 설정 (보통 0번 인덱스), 시작 정점의 방문여부를 true로 설정한다.

2. 시작 정점에 붙어있는 모든 간선들을 우선순위 큐(Priority Queue)에 추가한다.

> (우선순위 큐는 간선의 가중치가 낮을 수록 우선순위가 높음)

3. 가장 가중치가 낮은 간선을 추가한 뒤에, 해당 정점의 방문여부를 true로 설정한다.

4. 추가된 정점에 붙어있는 간선들을 기존의 우선순위 큐에 추가한다.

5. 모든 정점이 방문될때까지 위의 과정을 반복한다.

 

 

다시 말해서, 프림 알고리즘은 모든 간선이 아닌, 시작 정점에 붙어있는 간선들만을 가지고 다음 정점을 정한다음, 해당 정점을 포함하는 간선들을 기존의 간선들에 추가하여 다시 정렬한 다음, 다음 정점을 정하는 방식으로 신장 트리를 확장시켜 나가는 방식입니다.

 

 

 

소스 코드(JAVA)

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

public class Prim {

    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 token = new StringTokenizer(br.readLine());

        int v = Integer.parseInt(token.nextToken());
        int e = Integer.parseInt(token.nextToken());
        
        // 현재 그래프에서 가중치가 가장 낮은 간선 순서대로 저장하는 Priority Queue
        PriorityQueue<PrimEdge> queue = new PriorityQueue<>();
	// 각각의 정점이 가지고 있는 간선의 정보를 ArrayList로 저장.
        ArrayList<PrimEdge>[] graph = new ArrayList[v];
        // 각각의 정점의 방문 여부를 체크하는 배열.
        boolean[] isVisited = new boolean[v];

        for(int i=0; i<v;i++) graph[i] = new ArrayList<>();
        for(int i=0; i<e;i++){
            token = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(token.nextToken()) - 1;
            int end = Integer.parseInt(token.nextToken()) - 1;
            int val = Integer.parseInt(token.nextToken());
            graph[start].add(new PrimEdge(end, val));
            graph[end].add(new PrimEdge(start, val));
        }

        long sum = 0;
        isVisited[0] = true;
        for(int i=0; i<graph[0].size(); i++) {
            queue.add(graph[0].get(i));
        }

        while(!queue.isEmpty()) {
            PrimEdge temp = queue.poll();
            int to = temp.to;
            int val = temp.val;

            if(isVisited[to]) {
                continue;
            }
            isVisited[to] = true;

            sum += val;
            for(int i=0; i<graph[to].size(); i++) {
                queue.add(graph[to].get(i));
            }
        }

        bw.write(sum +"\n");
        bw.flush();
        bw.close();
    }
}

class PrimEdge implements Comparable<PrimEdge> {
    int to, val;
    PrimEdge(int to, int val) {
        this.to = to;
        this.val = val;
    }

    @Override
    public int compareTo(PrimEdge o) {
        return this.val - o.val;
    }
}

 

Time Complexity

 

프림 알고리즘은 모든 정점을 거치면서 해당 정점을 포함하는 모든 간선들을 우선순위 큐에 추가하는 방식으로 작동합니다. 따라서 성능은 우선순위 큐의 성능에 의해서 결정되며, 일반적으로 O(ElogV)의 시간복잡도를 갖는 것으로 알려져 있습니다. 

반응형

'Computer Science > Algorithm' 카테고리의 다른 글

머지 소트 트리 (Merge Sort Tree)  (0) 2020.06.21
세그먼트 트리(Segment Tree)  (0) 2020.06.18
펜윅 트리(Fenwick Tree)  (0) 2020.06.14
KMP 알고리즘  (0) 2020.03.17