프림 알고리즘 : 최소 신장 트리(MST)를 찾는 알고리즘

프림 알고리즘

최소 신장 트리(MST)를 찾기 위한 알고리즘이다. 프림 알고리즘은 주어진 그래프에서 시작 정점을 선택하고 해당 정점을 기준으로 MST를 구축해나가는 방식으로 동작한다.

 

1. 시작 정점을 우선순위 큐에 넣는다. (우선순위 큐는 가중치에 따라 오름차순 정렬되어야 함)
2. 우선순위 큐에서 노드 하나를 꺼내 MST에 포함되어 있는지 확인
    2-1. 포함되어 있다면 무시. 다시 1번으로
    2-2. 포함되어 있지 않다면 방문처리 후 해당 노드와 연결된 노드를 우선순위 큐에 추가
3. 2번 과정 반복

최소 신장 트리에 대해서는 크루스칼 알고리즘 참고!

        static class Edge implements Comparable<Edge> {
        int v;
        int cost;

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

        // 거리(비용)이 짧은 것이 높은 우선순위를 가지도록
        @Override
        public int compareTo(Edge o) {
            if (this.cost < o.cost)
                return -1;
            return 1;
        }
    }

    static ArrayList<ArrayList<Edge>> graph = new ArrayList<>();

    public static void prim(int start, int n) {
        boolean[] visited = new boolean[n+1];

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(start, 0));

        int total = 0;
        while(!pq.isEmpty()) {
            Edge edge = pq.poll();
            int v = edge.v;
            int cost = edge.cost;

            if(visited[v]) continue;

            visited[v] = true;
            total += cost;

            for (Edge e : graph.get(v)) {
                if (!visited[e.v]) {
                    pq.offer(e); // 선택된 노드와 연결된 간선을 우선순위 큐에 추가
                }
            }
        }
    }

 

모든 노드에 대해 탐색을 진행하므로 O(V)이고, 우선순위 큐를 사용하여 매 노드마다 최소 간선을 찾는 시간은 O(logV) 이므로 탐색 과정에는 O(VlogV) 가 소요된다. 그리고 각 노드의 인접 간선을 찾는 시간은 모든 노드의 차수와 같으므로 O(E) 이고, 간선을 힙에 넣는 과정이 log(V)가 되어 O(ElogV)가 소요된다. 따라서 O(VlogV + ElogV)로 O(ElogV)가 된다.

 

우선순위큐가 아닌 배열로 구현한다면 O(V²) 가 된다.