[MST] Prim

이번 시간에는 MST를 구하는 두 번째 알고리즘으로 Prim에 대해서 살펴보자.

 

Prim 알고리즘

 

알고리즘 개요

Prim은 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 구성하는 방식이다. 따라서 Kruskal과 달리 정점 중심의 알고리즘이다.

Prim은 서로 소인 두 개의 집합 즉 [MST 집합]과 [비 MST 집합]으로 정점들을 관리한다.(그렇다고 union find 를 쓴다는 이야기는 아니다.) 여기서 [MST 집합]은 MST를 구성하고 있는 정점들의 집합이고 [비 MST 집합]은 아직 MST를 구성하고 있지 않은 정점들의 집합이다. 우리는 [비 MST] 집합에서 하나씩 정점들을 선택해서 MST 집합을 완성해나가는 과정이다.

Prim의 기본 동작은 다음과 같다.

• 어차피 모든 정점은 MST 집합이 되므로 임의의 정점을 선택해서 MST 집합을 구성한다.
• MST 집합과 연결되는 비 MST 집합의 정점들 중 최소 비용으로 연결 가능한 정점을 선택한다. 이 과정에서 점점 MST 집합이 증가되고 연결할 수 있는 비 MST 집합과의 거리가 갱신된다.
• 모든 정점을 선택할 때까지 위 과정을 반복한다.

 

알고리즘 전개 절차

초기 상태는 MST 그룹과 비 MST 그룹으로 나뉘며 어떤 정점이 MST의 대상이 되었는지 관리하기 위한 테이블이 필요하다.

초기 상태: 두 개의 그룹으로 나뉜다.

이제 임의의 한 점(1)을 MST 그룹으로 처리한다.

{1}은 MST가 되었고.. 다음 MST의 후보는?

{1}과 연결할 수 있는 최소 비용의 비 MST 그룹으로 2를 선택한다.

2까지 포섭 완료! 이제 MST 그룹은 {1, 2}

{1, 2}와 연결될 수 있는 다음 포섭 대상으로 7을 선택한다.

{1, 2} 주변 정점 중 7은 2의 비용으로 갈 수 있다.

 

{1, 2, 7}과 연결된 수 있는 다음 최소 비용 정점은 6!

다음 대상은 6 너로 정했다!

{1, 2, 7, 6}과 연결되는 다른 정점은 5!

다음 정점으로 5가 선택된다.

{1, 2, 7, 6, 5}와 연결될 수 있는 다음 정점은 4!

또 다음 대상은 4(6원짜리)이지만 4는 이미 MST 그룹원이다.

마지막으로 3이 선택되면 종료!

드디어 모든 비 MST 그룹이 MST 그룹으로 이동 완료!

 

기본코드

Prim은 정점 중심으로 처리한다. 따라서 정점을 정의하는데 비용의 오름차순으로 정렬되어야 한다.

static class LinkNode implements Comparable<LinkNode> {
  int i, w;
  LinkNode pre;
  // Prim 처리를 위한 생성자
  public LinkNode(int i, int w) {
    this.i = i;
    this.w = w;
  }
  // 그래프 구성을 위한 생성자
  public LinkNode(int i, int w, LinkNode pre) {
    this(i, w);
    this.pre = pre;
  }
  @Override
  public int compareTo(LinkNode o) {
    return Integer.compare(this.w, o.w);
  }
}

다음은 최소 비용 정점을 찾아가는 과정인데 Dijkstra와 완전 유사하다. 단 차이점은 Dijkstra는 누적 비용을 계산했다면 Prim은 그냥 주변 정점과의 비용만 고려한다.

boolean[] visited = new boolean[V + 1];
PriorityQueue<LinkNode> pq = new PriorityQueue<>();
pq.add(new LinkNode(1, 0));// 임의의 정점에서 시작
int nodeCnt = 0;           // 종료 조건을 위한 flag
while (!pq.isEmpty()) {
  LinkNode front = pq.poll();
  if (visited[front.i]) {
    continue;
  }
  visited[front.i] = true;
  // 모든 정점을 방문했다면 그만
  if (++nodeCnt == V) {
    return;
  }
  // 다음 정점 처리
  for (LinkNode child = graph[head.i]; child != null; child = child.pre) {
    // 미방문이면 방문하지만 여기서 방문 처리 하지는 않는다.
    if (!visited[child.i]) {
      pq.add(new LinkNode(child.i, child.w));
    }
  }
}

 

BJ 6497 전력난 솔루션(Prim)