[알고리즘] Prim 알고리즘이란?

오늘은 MST를 만드는 알고리즘 중 Prim 알고리즘에 대해서 알아보겠습니다.

 

---

Prim 알고리즘이란?

Prim 알고리즘은 MST(Minimun Spanning Tree)를 찾는 알고리즘 중 하나입니다.

 

임의의 시작점에서 시작하여 해당 점과 가장 가까운 정점을 추가하여 하나의 트리를 만들고, 해당 트리에서 가장 가까운 정점을 하나씩 추가하여 MST를 만드는 알고리즘입니다.

 

아래의 그림으로 차근차근 진행해봅시다.

 

Kruskal의 동일한 예제를 통해 확인해봅시다.

 

가장 먼저 모든 정점 간의 연결이 없다고 생각하고 진행합니다. 거기서 임의의 한 정점을 뽑을건데, 음.. 저는 5번 정점을 시작으로 진행해보겠습니다.

 

5번 정점과 연결된 가장 가까운 정점은 거리가 2인 3번 노드입니다.

 

3번 노드와 하나의 트리를 이루어 시작해보겠습니다.

이제 정점 3과 5가 이어진 하나의 트리에서 가장 가까운 정점을 찾아봅시다.

 

아마도 정점 5번과 연결된 2번 정점이 되겠네요. 그러면 아래와 같은 트리가 생성됩니다.

 

이제 이 트리와 가장 가까운 정점을 찾아봅시다. 정점 2와 연결된 4번 정점이 가장 가깝겠네요.

 

거의 다 왔습니다. 이제 4번 정점과 연결된 6번 정점을 연결해줍니다.

 

나머지 두개는 빠르개 진행합니다. 6번 정점과 가장 가까운 1번 정점이 선택되고, 그 다음에는 0번 정점이 연결되겠네요.

 

간선은 아래와 같이 선택되고 총 n개의 정점이 모두 선택되었으므로 MST를 구성하였다고 판단하여 종료하게 됩니다.

 

저희가 지금까지 봤던 MST와 동일한 모양임을 알 수 있습니다.

 

 

자! 이제 코드를 확인해봅시다.

 

 

Prim 알고리즘의 구현

우리는 배열을 이용하여 진행합니다. 배열에는 트리와 인접한 정점들의 가중치만을 살려놓습니다.

그렇지 않은 트리와 적어도 두 정점만큼 떨어져있다면, 배열에서 해당 정점의 값은 자료형 최대 표현 범위 즉, 무한대로 표시합니다.

 

아래의 코드를 보면 이해하실 수 있습니다.

 

public class Edge {
    int adjVertex;
    int weight;

    public Edge(int adjVertex, int weight) {
        this.adjVertex = adjVertex;
        this.weight = weight;
    }
}

저희가 이번에 사용할 Edge 클래스는 자신으로부터 연결된 인접 정점만을 가리킵니다. 또한 가중치를 가지고 있습니다.

 

import java.util.List;

public class PrimMST {
    int N;
    List<Edge>[] graph;

    public PrimMST(List<Edge>[] graph) {
        this.N = graph.length;
        this.graph = graph;
    }

    public int[] mst(int s){
        boolean[] visited = new boolean[N];
        int[] D = new int[N];

        int[] previous = new int[N];
        for(int i=0; i<N; i++){
            previous[i] = -1;
            D[i] = Integer.MAX_VALUE;
        }
        previous[s] = 0;
        D[s] = 0;

		// 트리로부터 가까운 거리를 갖는 minVertex 찾기
        for(int k=0; k<N; k++){
            int minVertex = -1;
            int min = Integer.MAX_VALUE;

            for(int j=0; j<N; j++){
                if((!visited[j]) && (D[j] < min)){
                    min = D[j];
                    minVertex = j;
                }
            }
            
            visited[minVertex] = true;

            for (Edge i : graph[minVertex]) { // D를 갱신
            	// 트리 내에 있는 정점과 연결된 정점들만 D를 갱신해야함.
                if(!visited[i.adjVertex]){
                    int currentDist = D[i.adjVertex];
                    int newDist = i.weight;
                    if(newDist < currentDist){
                        D[i.adjVertex] = newDist;
                        previous[i.adjVertex] = minVertex;
                    }
                }
            }
        }
        return previous;
    }
}

 

이 코드에서 마지막 부분이 D를 갱신하는 부분인데, 이 부분을 주의깊게 살펴봐야합니다. 초기에는 무한대로 지정해줍니다.

 

그리고, 트리로 인식되는 정점들과 연결된 정점만 배열 D의 값을 갱신해주는 것입니다.

그렇게 함으로써 '트리 근방에 있는 정점들 중의 최소'를 구할 수 있게 됩니다.

 

 

이 코드를 통해서 상단의 트리를 입력값으로 넣었을 때 나오는 값을 아래와 같습니다.

 

 

Prim 알고리즘의 수행 시간

저희는 배열을 통해서 minVertex를 찾았습니다. 따라서 minVertex를 찾는 시간 O(n), 해당 과정을 n번 반복하기 때문에 O(n^2)이 됩니다.

 

반면, 우리가 배열을 사용하지 않고 Kruskal에서 이용한 우선순위 큐를 이용하게 된다면, 별도의 정렬 없이 큐에서 pop을 통해 나오는 값이 최소일 것입니다.

 

우선순위 큐의 정렬은 O(log n)을 갖게되므로, 총 O(n log(n))이 됩니다. 따라서 우선순위 큐를 활용한다면 기존보다 매우 효율적인 방법이 되겠습니다.

 

---

오늘은 Prim 알고리즘에 대해서 배웠습니다. 진행하는 과정부터 코드까지 그리 어렵지 않은 알고리즘이라고 생각합니다! 다음 포스팅에서는 MST를 찾는 알고리즘 중 마지막으로 Sollin 알고리즘에 대해서 배워보겠습니다. 감사합니다.