[Algorithm] Prim's Algorithm (프림 알고리즘)

1. Prim's Algorithm

 

프림 알고리즘은 크루스칼과 달리 정점을 기준으로 MST를 구성하는 방법이다.

MST에 포함된 정점 집합과 아직 포함되지 않은 정점 집합, 두가지를 가지고 수행되는 알고리즘이다.

매 순서마다 두 집합을 연결하고 있는 edge들을 모두 확인하여 가장 작은 가중치를 가지고 있는 edge를 선택하여 해당 edge와 연결되어 있는 정점을 MST에 포함시키는 방식으로 확장한다.

 

 

2. 프림 알고리즘 구현

 

1) MST에 포함된 정점을 저장할 집합을 선언하고 MST에 포함되어 있는 정점을 추가하여 초기화한다.

2) 각 정점의 거리를 표현하는 공간을 선언하고 MST에 포함된 정점은 0으로 나머지는 무한대로 초기화한다.

3) 아직 MST에 포함되지 않은 정점 중 가장 최단 거리를 가지고 있는 정점을 찾는다.

4) 해당 정점을 MST에 포함된 집합에 추가한다.

5) 새로 포함된 정점과 인접한 정점들을 확인하여 최단거리를 업데이트한다.

6) 모든 정점이 MST에 포함될 때까지 3) ~ 4) 를 반복한다.

 

    // matrix 사용
    private int[][] prim() {
        int[][] result = new int[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = i + 1; j < N; j++) {
                result[i][j] = result[j][i] = -1;
            }
        }

        // 각 정점의 연결 상태를 저장하는 배열
        int[] parent = new int[N];
        parent[0] = 0;

        // 각 정점들의 최소 거리
        int[] vertices = new int[N];
        // 첫번째 노드를 제외하고는 INF로 초기화
        for(int i = 1; i < N; i++) vertices[i] = Integer.MAX_VALUE;

        int count = 0;
        while(count++ < N) {
            int vertex = find(vertices);
            visited[vertex] = true;
            result[parent[vertex]][vertex] = result[vertex][parent[vertex]] = vertices[vertex];
            this.weight += vertices[vertex];

            // 새로 추가되는 정점과 인접한 정점 중 아직 포함되지 않은 정점들에 대해 weight를 업데이트 한다.
            for(int i = 0; i < N; i++) {
                if(graph[vertex][i] == Integer.MAX_VALUE || visited[i] || vertices[i] < graph[vertex][i]) continue;
                vertices[i] = graph[vertex][i];
                parent[i] = vertex;
            }
        }

        return result;
    }

    // 인접 리스트와 binary heap 사용
    private int[][] primList() {
        List<Node>[] graphLists = new LinkedList[N];
        for(int i = 0; i < N; i++) {
            graphLists[i] = new LinkedList<>();
            for(int j = 0; j < N; j++) {
                if(this.graph[i][j] == Integer.MAX_VALUE) continue;
                graphLists[i].add(new Node(j, this.graph[i][j]));
            }
        }

        int[][] result = new int[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = i + 1; j < N; j++) {
                result[i][j] = result[j][i] = -1;
            }
        }

        Node[] v = new Node[N];
        int[] parent = new int[N];
        for(int i = 0; i < N; i++) {
            v[i] = new Node(i, Integer.MAX_VALUE);
            parent[i] = -1;
        }

        v[0].weight = 0;
        parent[0] = 0;
        visited[0] = true;

        TreeSet<Node> queue = new TreeSet<Node>(new NodeComparator());
        for(int i = 0; i < N; i++) queue.add(v[i]);

        while(!queue.isEmpty()) {
            Node node = queue.pollFirst();
            visited[node.vertex] = true;
            result[parent[node.vertex]][node.vertex] = result[node.vertex][parent[node.vertex]] = v[node.vertex].weight;
            this.weight += v[node.vertex].weight;

            for(Node next : graphLists[node.vertex]) {
                if(visited[next.vertex] || v[next.vertex].weight <= next.weight) continue;
                queue.remove(v[next.vertex]);
                v[next.vertex].weight = next.weight;
                queue.add(v[next.vertex]);
                parent[next.vertex] = node.vertex;
            }
        }

        return result;
    }

 

 

3. 시간 복잡도

 

프림 알고리즘은 매 정점마다 인접한 정점들을 확인해야 하기때문에 O(V²)의 시간 복잡도를 가진다.

하지만 인접 리스트와 힙 자료구조를 사용하여 연결되어 있는 정점들을 정렬된 순서대로 찾게 되면 O(E log V)의 시간 복잡도를 가진다.