[알고리즘] 프림 알고리즘(최소신장트리, 최소스패닝트리)

오늘은 프림 알고리즘에 대해 정리해보겠습니다.

스패닝 트리는 그래프 내의 모든 정점을 연결하지만 사이클이 없는 트리입니다.

밑의 그래프는 예시로 만들어본 그냥 트리입니다. 정점 4개와 6개의 간선으로 이루어져있습니다.

그냥 트리

 

다음 그래프는 정점 4개와 3개의 간선으로 이루어져있습니다. 최소한의 간선의 갯수로 이루어져 있고 모든 정점이 연결된 스패닝 트리의 형태입니다. 스패닝 트리는 다음과 같이 간선의 갯수가 정점의 갯수 - 1 개라는 특징이 있습니다.

 

 

최소 스패닝 트리는 이러한 스패닝 트리 중 사용된 가중치 합이 최소인 트리를 뜻합니다.

 

스패닝 트리
 - 최소한의 간선의 갯수로 이루어져 있고 모든 정점이 연결됨
 - 간선의 갯수 = 정점의 갯수 - 1

최소 스패닝 트리
 - 스패닝 트리 중 사용된 가중치 합이 최소인 트리 

 

최소 스패닝 트리를 구하는 알고리즘은 크루스칼, 프림 두가지가 있습니다.

이번 포스팅에서는 프림 알고리즘에 대해 설명하겠습니다.

 

개념

 

프림 알고리즘은 하나의 시작점으로 구성된 트리에 간선을 하나씩 추가하는 형태입니다.

정점 선택을 기반으로 하며 이전단계에서 만들어진 신장트리를 확장합니다.

정점의 수에 영향을 받기에 정점의 수가 적고 간선의 수가 많은 그래프에서 효과적입니다.

 

프림

• 하나의 시작점으로 구성된 트리에 간선을 추가 -> 이전단계에서 만들어진 신장 트리를 확장
• 정점 선택 기반
• 정점(노드)의 수에 영향을 받기에 정점의 수가 적고 간선의 수가 많은 그래프에서 효과적

 

구현 예시

 

위키백과에서 프림을 설명하기 위한 그래프 예시를 가져왔습니다. 

먼저 임의의 점을 선택해 줍니다.

편하게 A를 시작점으로 설정하겠습니다.

A에는 A와 B를 연결하는 가중치 7인 간선과 A와 D를 연결하는 가중치 5인 간선이 있습니다.

가중치가 적은 간선을 연결합니다.

연결된 정점, 간선은 빨간색으로 표시하고 사용할 수 있는 간선은 파란색으로 표시했습니다.

사용할 수 있는 간선 중 가중치가 가장 낮은 간선을 연결해줍니다.

 

A, D, F가 연결되었습니다.

다시 파란 간선중 가중치가 가장 낮은 간선을 연결합니다.

 

A, B, D, F가 연결되었습니다.

또한 D와 B를 연결하던 가중치 9인 간선은 의미가 없어지므로 배제합니다.

위의 과정들을 반복하면 다음과 같은 최소 스패닝 트리가 완성됩니다.

 

 

과정을 요약해보겠습니다.

1. 임의의 정점을 선택
2. 가중치가 가장 낮은 간선 연결
3. 사용할 수 있는 간선 중 연결된 정점 제외하고 가중치가 가장 낮은 간선 연결
4. 모든 정점이 연결될 때까지 반복

 

문제 예시

 

백준 1197 최소스패닝트리 문제를 사용하였습니다.

문제 링크 : https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

정점 사용은 방문배열을 통해 처리하였고 가중치 순 정렬을 위해 우선순위 큐를 사용하였습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 가중치가 작은 순서부터 정렬
class Node implements Comparable<Node> {
    int v;
    int w;

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

    @Override
    public int compareTo(Node o) {
        return this.w - o.w;
    }
}


class Main {
    static int sum;                             // 합을 구할 sum
    static ArrayList<ArrayList<Node>> graph;    // 간선 정보를 저장할 그래프
    static boolean[] visit;                     // 방문 확인할 visit

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());   // 정점의 갯수
        int E = Integer.parseInt(st.nextToken());   // 간선의 갯수

        graph = new ArrayList<>();
        for (int i = 0; i < V + 1; i++) {           // 인덱스 혼동을 피하고자 V+1
            graph.add(new ArrayList<>());
        }

        visit = new boolean[V + 1];                 // 위와 마찬가지

        // A가 B와 연결되어 있다면 B와 A도 연결되어 있음 -> 양쪽으로 추가
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            graph.get(A).add(new Node(B, C));
            graph.get(B).add(new Node(A, C));
        }

        // 임의의 정점에서 시작
        prim(new Node(1, 0));
        System.out.println(sum);

    }

    static void prim(Node start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();     // 우선순위 큐 사용 -> 가중치순 정렬
        pq.add(start);
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (visit[now.v]) {         // 방문했으면 (= 만약 정점이 저장되어있으면) 넘어가라
                continue;
            }
            visit[now.v] = true;        // 방문처리(= 정점 저장)
            sum += now.w;               // 가중치 저장
            for (Node next : graph.get(now.v)) {
                if (!visit[next.v]) {
                    pq.add(next);
                }
            }
        }
    }
}

 

---

다익스트라 vs 프림

 

구현하다보면 다익스트라 알고리즘과 유사하다는 느낌을 받을 수 있습니다.

두 알고리즘의 차이를 살펴보겠습니다.

 

다익스트라 : 두 정점 사이의 촤단거리를 구한다.

프림 : 모든 노드들을 최소비용으로 연결한다.

 

위의 표를 예시로 들겠습니다.

 

시작점을 B로 설정해도 프림 알고리즘의 결과는 동일합니다.

완성된 최소 스패닝 트리를 통해 B에서 C로 간다고 할때 가중치의 합은 7 + 5로 12 입니다.

다익스트라로 간다고 쳤을때는 8 입니다.

프림은 두 노드 사이의 거리가 최소가 아닐 수 있습니다.

또한 프림은 방향이 없는 그래프에서만 작용하며, 다익스트라는 방향이 있든 없든 모두 사용 가능합니다.

결과적으로 비슷한 구현 방법이고 얻어걸려서 같을 수는 있지만

프림은 다익스트라를 보장하지 않고, 다익스트라 또한 프림을 보장하지 않습니다.

 

 

많이 부족한 코드입니다. 수정할 점, 잘못된 점, 개선점 보이면 말씀해주세요!!

감사합니다.