ZeroCho Blog

안녕하세요. 이번 시간에는 그래프를 활용한 알고리즘인 프림 알고리즘에 대해 알아보겠습니다. 이 알고리즘은 그리디 알고리즘이기도 합니다.

다음과 같은 그래프가 있습니다.

그래프인데 아크들에 가중치가 붙어 있습니다. 가중치는 거리나 중요도로 이해하셔도 됩니다.

최소 신장 트리

여기서 최소 신장 트리 문제가 나오는데, 한 버텍스를 기준으로 가능한한 작은 가중치의 아크들을 사용해서 모든 버텍스를 연결하는 트리를 만드는 겁니다. 즉, 최소의 아크 값만 사용해서 모든 버텍스를 연결하는 것을 찾는 거죠. 위의 경우, 정답은 다음과 같습니다.

총합 13 가중치의 아크들로 모든 버텍스들을 연결하였습니다. 이런 모양의 트리를 최소 신장 트리라고 부릅니다. 이 문제를 푸는 알고리즘은 크게 두 가지가 있는데, 크루스칼과 프림 알고리즘입니다. 저는 이중에서 프림 알고리즘만 코드로 다루고, 크루스칼은 간단히 설명만 하고 넘어가겠습니다.

이 최소 신장 트리가 최단 경로인지 궁금할 수 있습니다. 정답은 아니라는 겁니다. 얼핏 보면 최단경로처럼 보이기도 하지만, A에서 E로 가는 것은 최소 신장 트리인 ACDE보다 ACE가 더 짧습니다. 최단 경로를 구하는 알고리즘은 다음 시간 다익스트라 알고리즘 때 할 예정입니다.

프림 알고리즘

프림 알고리즘은 간단합니다. 일단 기준 버텍스 하나를 잡고, 그 버텍스에서 출발하는 가장 작은 값의 아크와 도착 버텍스를 선택합니다. 그리고 이제 선택된 버텍스들에서 출발하고, 이미 선택하지 않은 아크 중 가장 작은 값의 아크와 도착 버텍스를 선택합니다. 모든 버텍스가 선택될 때까지 반복하면 됩니다.

위의 예시를 통해 설명하자면, 버텍스 B에서 시작할 때 가장 작은 값의 아크는 BC입니다. BC와 C를 선택합니다. 이제 B와 C에서 출발하는 아크 중 가장 작은 아크는 이미 선택한 BC를 제외하고 AC나 CD입니다. AC와 A를 먼저 선택합니다. 이제 A, B, C에서 출발하는 아크 중 가장 작은 아크는 CD입니다. CD와 D를 선택하면 됩니다. 이렇게 반복해서 E와 F까지 선택하게 되면 그게 최소 신장 트리입니다.

매우 간단하죠? 프림 알고리즘은 전체를 생각하지 않고 현재 상황에서 최선의 선택만 고려하기 때문에 그리디 알고리즘입니다.

코드로 볼까요? 그래프 자료구조 시간에 만들었던 코드를 재사용합니다. 프로토타입으로 하나만 더 추가하면 됩니다.

Graph.prototype.mst = function() {
  var first = this.first;
  var inTreeCount = 0;
  while (first) { // 모든 inTree를 false로 초기화
    first.inTree = false;
    var arc = first.arc;
    while (arc) {
      arc.inTree = false;
      arc = arc.nextArc;
    }
    first = first.next;
  }
  this.first.inTree = true; // 첫 버텍스를 MST에 넣습니다.
  inTreeCount++;
  console.log('%s 버텍스가 추가되었습니다.', this.first.key);
  var temp = this.first;
  var current;
  var minArc; // 최소 아크를 저장
  var minTemp; // 최소 아크의 출발 버텍스를 저장
  while (inTreeCount != this.count) { // 모든 버텍스를 추가할 때까지
    while (temp) {
      current = temp;
      temp = temp.next;
      if (!current.inTree) continue;
      arc = current.arc;
      while (arc) {
        if (!arc.destination.inTree) {
          if (!minArc) minArc = arc;
          if (minArc.data > arc.data) { // 기존 최솟값보다 더 작은 값을 찾았을 때 
             minArc = arc; // 최소 아크를 찾음
            minTemp = current; // 최소 아크의 출발 버텍스 저장
          }
        }
        arc = arc.nextArc;
      }
    }
    minArc.destination.inTree = true;
    minArc.inTree = true;
    inTreeCount++;
    console.log('%s 버텍스에서 %s 버텍스로 향하는 가중치 %d의 아크가 추가되었습니다.', minTemp.key, minArc.destination.key, minArc.data);
    minArc = null;
    temp = this.first;
  }
};

var graph = new Graph();
graph.insertVertex('A');
graph.insertVertex('B');
graph.insertVertex('C');
graph.insertVertex('D');
graph.insertVertex('E');
graph.insertVertex('F');
insertTwoWayArc(graph, 6, 'A', 'B');
insertTwoWayArc(graph, 3, 'A', 'C');
insertTwoWayArc(graph, 2, 'B', 'C');
insertTwoWayArc(graph, 5, 'B', 'D');
insertTwoWayArc(graph, 3, 'C', 'D');
insertTwoWayArc(graph, 4, 'C', 'E');
insertTwoWayArc(graph, 2, 'D', 'E');
insertTwoWayArc(graph, 3, 'D', 'F');
insertTwoWayArc(graph, 5, 'E', 'F');
graph.mst();
// A 버텍스가 추가되었습니다.
// A 버텍스에서 C 버텍스로 향하는 가중치 3의 아크가 추가되었습니다.
// C 버텍스에서 B 버텍스로 향하는 가중치 2의 아크가 추가되었습니다.
// C 버텍스에서 D 버텍스로 향하는 가중치 3의 아크가 추가되었습니다.
// D 버텍스에서 E 버텍스로 향하는 가중치 2의 아크가 추가되었습니다.
// D 버텍스에서 F 버텍스로 향하는 가중치 3의 아크가 추가되었습니다.

이것과 비교하면 똑같죠? 지금 현재 방법은 힙 또는 우선순위 큐를 사용하지 않아서 성능이 안 좋습니다. 왜나면 매번 MST에 포함된 버텍스와 연결된 아크들을 검사해야 하기 때문이죠. 힙 또는 우선순위 큐를 사용하면 검사 횟수를 1번으로 줄일 수 있습니다.

배열을 사용하면 O(V^2), 이진 힙을 사용하면 O(ElgV), 피보나치 힙을 사용하면 O(E+VlgV)의 시간 복잡도를 가집니다.

크루스칼 알고리즘

크루스칼 알고리즘도 정말 간단합니다. 방법은 다음과 같습니다. 일단 가장 작은 값의 아크를 고릅니다. 그리고 그 다음 값의 아크를 고르고요. 이제 세 번째 아크부터는 가장 작은 값의 아크를 고르되 순환이 생기지 않게만 고릅니다. 순환이란, AB, BC, CA처럼 한 바뀌 빙 돌면 연결되는 그런 그래프를 의미합니다. 모든 버텍스가 다 포함될 때까지 이렇게 고르면 됩니다.

위의 예시를 통해 보면 가장 작은 값인 BC를 고른 후, DE를 고릅니다. 그 후 AC, CD, DF를 차례대로 고릅니다. 이게 끝입니다. 황당할 정도로 쉽죠? 대신 순환이 생기는지만 매번 체크하면 됩니다.

크루스칼 알고리즘도 현재 상황에서 최선의 선택이 결과적으로도 최선이기 때문에 그리디 알고리즘입니다. 위 예제에서는 프림과 크루스칼의 결과는 같습니다. 둘 중 취향에 따라 선택하면 되겠습니다. (크루스칼 알고리즘이 자료구조의 영향을 덜 받는다고 하네요. 그리고 그래프가 빽빽한 경우에는 프림 알고리즘이 더 성능이 좋다고 합니다)

크루스칼 알고리즘은 제가 직접 구현하지는 않겠습니다. (절대 못해서 그러는 건 아니고... 귀찮아서... 죄송...)

다음 시간에는 최단 경로를 구하는 알고리즘인 다익스트라 알고리즘에 대해 알아보겠습니다.