알고리즘 - 최소 비용 신장 트리 (MST)

신장 트리 (Spanning Tree)

신장 트리란 그래프에서 모든 정점이 최소한으로 연결되어 있는 그래프를 의미합니다. 

 

신장트리

신장 트리 특징

신장 트리의 특징은 다음과 같습니다.

• 하나의 그래프에 여러 신장 트리가 존재할 수 있다.
• 모든 정점들이 연결되어 있으며, 사이클이 존재하지 않는다.
• n개의 정점을 가진 신장 트리는 n-1개의 간선을 가지고 있다.

 

최소 비용 신장 트리 (MST)

최소 비용 신장 트리(Minimum Spanning Tree)란 신장 트리 중에 사용된 간선들의 가중치 합이 가장 작은 트리를 의미합니다.

 

쉽게 말해, 모든 노드들을 가장 적은 비용으로 연결시킨 그래프라고 생각하면 됩니다. 

 

최소 비용 신장 트리

두 가지의 그리디 알고리즘으로 최소 비용 신장 트리를 구할 수 있습니다.

 

 

크루스칼 알고리즘 (Kruskal)

크루스칼 알고리즘은 간선 중 최소 값을 가진 간선부터 순차적으로 연결하여 구하는 방식입니다. 

 

크루스칼 알고리즘을 사용하기 위해선 간선에 대한 정렬을 해주어야 하는데, 이 작업이 크루스칼 알고리즘에서 가장 많은 시간을 요구하므로 시간복잡도는 정렬의 속도인 O(ElogE)의 시간복잡도를 가집니다.

 

주로 간선 수가 적을 때 사용됩니다.

 

구현 방법

출처:https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

1. 간선들의 가중치를 오름차순으로 정렬합니다.
2. 정렬된 간선 리스트에서 간선을 순서대로 선택합니다.
   • 가장 낮은 값부터 순차적으로 선택되며, 사이클을 형성하는 간선은 제외합니다.
   • 보통 사이클 검사는 Union-Find 알고리즘을 이용합니다.
3. 선택된 간선의 개수가 N-1에 도달한다면 종료합니다. (혹은 전부 다 돌려도 상관없습니다.)

 

프림 알고리즘 (Prim)

 

임의의 노드에서 시작하여 연결된 노드들의 간선 중 가장 낮은 가중치를 갖는 간선을 선택해 나가는 방법을 프림 알고리즘이라고 합니다.

 

다익스트라 알고리즘과 거의 동일한 알고리즘이지만, 다익스트라와는 달리 음수 가중치가 있더라도 동작 가능합니다.

 

시간 복잡도는 우선순위 큐를 이용하면 O(ElogV)가 걸리며, 간선의 개수가 많을 때 크루스칼보다 유리합니다. 

 

구현 방법

 

출처:https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=babobigi&logNo=220492017389

1. 임의의 노드 하나를 선택합니다.
2. 연결된 노드 중, 가중치가 작은 간선을 지닌 노드를 선택합니다.
   
   • 이미 방문한 노드라면, 그 다음으로 가중치가 작은 노드를 선택합니다.
3. 모든 정점이 선택될 까지 2번 과정을 반복합니다.

 

 

프로그래밍 언어로 구현

Java

크루스칼

import static algo.UnionFind.*;

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.IntStream;

/**
 * edges = 간선 정보로  {1,2,5} 는 1 -> 2로 5의 가중치를 의미
 * v = 정점의 개수
 * e = 간선의 개수
 *
 * 여기서 UnionFind는 제가 직접 만들어둔 UnionFind를 사용했습니다. 관련 게시글이 블로그에 있으니 참고하세요.
 */

public class Kruskal {

   // 최소 비용 구하기
   public static int kruskal(int[][] edges, int v, int e) {
      int weightSum = 0;

      // 1. 간선들의 가중치를 오름차순으로 정렬
      Arrays.sort(edges, Comparator.comparing(edge -> edge[2]));


      // union-find를 사용하기 위한 배열 생성
      int[] parents = IntStream.range(0, v + 1).toArray();


      // 2. 간선을 순서대로 선택
      for (int i = 0; i < e; i++) {
         // 사이클이 없을 때만
         if (find(parents, edges[i][0]) != find(parents, edges[i][1])) {
            union(parents, edges[i][0], edges[i][1]);

            // 가중치 합산
            weightSum += edges[i][2];
         }
      }

      return weightSum;
   }
}

 

프림

프림은 우선순위큐로 구현하므로, 자바에서 제공하는 PriortiyQueue를 이용했습니다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Prim {

   public static int prim(int[][] edges, int v, int e) {
      int weightSum = 0;

      // 간선 정보를 그래프로 만들어 주는 밑작업
      ArrayList<ArrayList<Node>> graph = new ArrayList<>();

      for (int i = 0; i < v + 1; i++) {
         graph.add(new ArrayList<>());
      }

      for (int i = 0; i < e; i++) {
         ArrayList<Node> nodeA = graph.get(edges[i][0]);
         ArrayList<Node> nodeB = graph.get(edges[i][1]);

         nodeA.add(new Node(edges[i][1], edges[i][2]));
         nodeB.add(new Node(edges[i][0], edges[i][2]));
      }

      // 노드에 방문했는지 체크할 배열 생성
      boolean[] visited = new boolean[v + 1];

      // 노드들의 간선 중 가중치가 가장 작은 간선을 선택하기 위한 우선순위 큐
      PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparing(edge -> edge.weight));

      // 1번 노드부터 시작
      pq.add(new Node(1, 0));

      // MST 간선 수 체크
      int cnt = 0;

      while (!pq.isEmpty()) {
         // 현재 노드
         Node cur = pq.poll();

         cnt += 1;

         // 현재 노드가 방문한 노드라면 건너뛰기
         if (visited[cur.to]) {
            continue;
         }

         // 현재 노드 방문 처리
         visited[cur.to] = true;

         // 현재 노드로 올 때 발생한 가중치 더하기
         weightSum += cur.weight;

         // 현재 노드가 가지고 있는 인접 노드 수만큼 반복
         for (int i = 0; i < graph.get(cur.to).size(); i++) {

            // 인접 노드 가져오기
            Node adjNode = graph.get(cur.to).get(i);

            // 방문한 노드라면 건너뛰기
            if (visited[adjNode.to]) {
               continue;
            }

            // 인접 노드를 우선순위 큐에 추가
            pq.offer(adjNode);
         }
      }

      return weightSum;
   }

   // 이동하려는 노드를 위한 자료구조
   static class Node {

      int to;
      int weight;

      public Node(int to, int weight) {
         this.to = to;
         this.weight = weight;
      }
   }

}