[Algorithm] Prim

Prime 이란?

• MST를 만드는 알고리즘 중 하나입니다.
• Kruskal 과 다른점은 시작점을 기준으로 만들게 됩니다.

 

 

 

Prime 알고리즘

• S 집합: 현재까지 선택된 노드들
• S - A: 선택 되지 않은 노드들

 

핵심

• 선택한 노드들과 선택되지 않은 노드들을 연결하는 엣지중 최소를 찾는 것이다.

 

 

순서

• 노드를 선택한다.
• 선택한 노드들(S) 과 연결된 제일 노드를 선택한다.
  - 단 가중치가 제일 작은 엣지를 선택한다.

 

 

 

 

 

가중치가 최소인 엣지 찾기

O(n) 으로 노드들을 찾을수 있다.

• 선택되지 않은 노드들에 2개의 값을 추가해준다.
• key: 현재노드와 선택된 노드들간의 최소 거리
• π   : 현재노드에 연결된 선택된 노드

 

• 그림으로보아야 이해가 빠르다.

 

• H 를 기준으로 설명하면 현재까지 선택된 노드들(A,B,C,I) 중
• H 와 연결된 노드들은 (A, B, I) 이다.
• A,B,I 중 H 와 연결된 에지의 최소값은 7 이다.
• 그렇기 때문에 K 값은 7 이되고
• π 는 I 가된다.

 

 

 

구현

package com.company;

import java.util.*;

public class Prim {

    private ArrayList<ArrayList<Edge>> graph; // 그래프 를 저장하기 위해 List
    private ArrayList<Edge> primMST;          // MST 의 노드를 저장하기 위한 List
    boolean []visit;                          // 방문을 했는지 체크하기 위한 리스트


    public Prim(int count) {
        graph = new ArrayList<ArrayList<Edge>>();    // 그래프 초기화
        primMST = new ArrayList<>();                 // MST 노드를 저장할 List 초기화
        visit = new boolean[count+1];                // visit 초기화
        for(int i = 0; i <= count; i++) {            // 주어진 노드 수만큼 graph 초기화
            graph.add(new ArrayList<Edge>());
        }
    }

    class Edge implements Comparable<Edge> {
        private int u;                              // 시작노드
        private int v;                              // 종료노드
        private int w;                              // 가중치

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return this.w > o.w ? 1 : -1;      // 우선순위 큐에 넣을때
        }                                      // 최소값을 기준으로 정렬하기 위한 비교함수
    }

    public void addEdge(int u,int v,int w) {
        graph.get(u).add(new Edge(u,v,w));     // 양방향으로 추가
        graph.get(v).add(new Edge(v,u,w));     // 양방향으로 추가
    }


    public void runPrim(int startPoint) {

        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();// 1. 현재 노드를 기준으로 연결된 노드를
                                                                  //    우선순위 큐에 저장할 용도
        Deque<Integer> queue = new LinkedList<>();                // 2. 탐색을 위한 queue

        queue.add(startPoint);                                    // 시작점 을 넣어준다.

        while (!queue.isEmpty()) {                        // 1. 큐가 비워질때까지 반복
            int current = queue.poll();                   // 2. 큐에 있는 노드 번호를 가져온다.
            visit[current] = true;                        // 3. 방문했다고 표시
            for (Edge edge : graph.get(current)) {        // 4. 인접한 노드들 중 최소 가중치를 가지는 노드를
                if (!visit[edge.v]) {                     //    찾기 위해 우선순위 큐에 넣는다.
                    priorityQueue.add(edge);
                }
            }

            while (!priorityQueue.isEmpty()) {
                Edge edge = priorityQueue.poll();         // 가장 작은 노드를 꺼낸다.
                if (!visit[edge.v]) {                     // 방문했는지 체크
                    visit[edge.v] = true;                 // 방문했다고 표기
                    primMST.add(edge);                    // 현재 선택된 노드를 MST 에 넣어준다.
                    queue.add(edge.v);                    // 노드의 번호를 넣어준다. 해당 노드를 기준으로 탐색
                    break;
                }
            }
        }
    }

    public void printNode() {
        for(int i = 0; i < primMST.size(); i++) {
            System.out.println(primMST.get(i).v);
        }
    }


    public static void main(String[] args) {

        Prim prim = new Prim(9);
        prim.addEdge(1,2,4);
        prim.addEdge(1,8,8);

        prim.addEdge(2,3,8);
        prim.addEdge(2,8,11);

        prim.addEdge(3,4,7);
        prim.addEdge(3,9,2);
        prim.addEdge(3,6,4);

        prim.addEdge(4,5,9);
        prim.addEdge(4,6,14);

        prim.addEdge(5,6,10);


        prim.addEdge(6,7,2);


        prim.addEdge(7,8,1);
        prim.addEdge(7,9,6);

        prim.addEdge(8,9,7);

        prim.runPrim(1);
        prim.printNode();
    }
}