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

1. Prim 알고리즘이란?

---

무방향 연결 그래프가 주어졌을 때, 서브 그래프인 최소비용 신장트리(MST_Minimum Spanning Tree)를 찾을 때 사용하는 알고리즘입니다. MST를 만들기 위한 또 다른 알고리즘으로는 크루스칼 알고리즘이 있습니다.

 

다음과 같은 연결 그래프가 있다고 해보겠습니다.

[그림 1] 초기 연결 그래프

위와 같이 주어진 연결 그래프를 가지고 Prim 알고리즘을 통해 MST를 찾아보겠습니다.

가장 먼저 시작 정점을 선택해야합니다. (시작 정점은 어떤 정점이든 상관없습니다. 여기선 시작 정점으로 1을 선택하겠습니다.)

[그림 2] 시작 정점 선택

1번 정점을 가지는 그래프를 G라고 하겠습니다.

다음으로 그래프 G가 가지는 간선 중 가중치가 낮은 간선을 선택합니다. (최초 그래프 G에 속한 정점은 1번뿐이죠? 🙂 )

[그림 3] 시작 정점에서 가중치가 낮은 간선을 선택

이제 그래프 G는 1번과 3번 정점을 포함합니다. 마찬가지로 그래프 G가 가지는 간선 중 가중치가 낮은 간선을 선택합니다.

그래프 G가 가지는 간선으로는 (1, 2), (3, 2), (3, 4), (3, 5) 4개가 있는데, 이 중, 가중치가 가장 낮은 (3, 2)를 선택합니다.

[그림 3] 그래프 G는 1, 2, 3번 정점을 가진다.

이제 위의 과정을 반복해보자.

[그림 4] 위의 과정을 반복한 모습

최종적으로 아래와 같은 MST가 만들어집니다.

[그림 5] 최종 생성된 MST

2. 코드

---

class Main {

    private static int distance; // MST의 최소비용을 담습니다.
    
    private static void prim() {
        Queue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, 0)); // (node, distance)
        visited[0] = true;
        
        int edgeCount = 0;
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            edgeCount++; // 그래프에 정점이 하나씩 추가될 때마다 +1
            if (edgeCount == V - 1) { // MST에서 간선의 수는 (정점의 수 - 1)입니다.
                return;
            }
            if (!visited[now.node]) {
                visited[now.node] = true;
                distance += node.distance;
                
                for (Node next : graph.get(now.node)) {
                    pq.add(next);
                }
            }
        }
    }
}
class Node {
    int node, distance;
    Node(int node, int distance) {
        this.node = node;
        this.distance = distance;
    }
}

3. 참고자료 

---

[1] https://www.weeklyps.com/entry/프림 알고리즘