최소 신장 트리 알고리즘 (2): 프림 알고리즘 (Prim's Algorithm)

1. 프림 알고리즘이란?

프림 알고리즘(Prim's Algorithm)은 최소 신장 트리(MST: Minimum Spanning Tree)를 구하는 알고리즘 중 하나로, 정점을 중심으로 트리를 확장하는 방식으로 동작한다. 시작 정점에서 출발하여 가장 가중치가 낮은 간선을 선택하며 트리를 확장해 나간다.

1.1 프림 알고리즘의 특징

• 탐욕적 접근법(Greedy Approach) 기반
• 무방향 가중 그래프에서 사용
• 정점을 중심으로 최소 비용 간선을 선택해 트리를 확장
• 시간 복잡도: O((V + E) log V) (V는 정점 수, E는 간선 수)

2. 프림 알고리즘의 동작 원리

프림 알고리즘은 다음과 같은 단계로 수행된다:

1. 초기화:
   • 시작 정점을 선택하고 해당 정점에서 연결된 간선 중 가장 작은 가중치의 간선을 선택
   • 최소 비용 트리에 포함된 정점을 추적
2. 트리 확장:
   • 이미 선택된 정점과 인접한 정점 중 최소 가중치를 가진 간선을 선택
   • 해당 간선과 연결된 정점을 트리에 추가
3. 반복:
   • 트리에 포함된 정점 수가 (V-1)개가 될 때까지 위 과정을 반복

2.1 프림 알고리즘 예제

다음과 같은 가중치 그래프에서 최소 신장 트리를 구해 보자:

     (A)
    / | 
   1  3  
 (B) (C)-4-(D)
   \  |
    2 5
     (E)

2.2 프림 알고리즘의 수행 과정

1. 시작 정점으로 (A) 선택
2. (A-B: 1) 선택 → 트리에 (A)와 (B) 추가
3. (B-E: 2) 선택 → 트리에 (E) 추가
4. (A-C: 3) 선택 → 트리에 (C) 추가
5. (C-D: 4) 선택 → 트리에 (D) 추가

최종 최소 신장 트리(MST):

     (A)
    / | 
   1  3  
 (B) (C)-4-(D)
   \  
    2 
     (E)

3. 프림 알고리즘 구현 (Java)

import java.util.*;

class Edge implements Comparable<Edge> {
    int dest, weight;

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

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class Prim {

    public static void primAlgorithm(Map<Integer, List<Edge>> graph, int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[graph.size()];
        int mstWeight = 0;

        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();

            if (visited[current.dest]) continue;

            visited[current.dest] = true;
            mstWeight += current.weight;
            System.out.println("정점: " + current.dest + ", 가중치: " + current.weight);

            for (Edge edge : graph.getOrDefault(current.dest, new ArrayList<>())) {
                if (!visited[edge.dest]) {
                    pq.add(edge);
                }
            }
        }

        System.out.println("MST의 총 가중치: " + mstWeight);
    }

    public static void main(String[] args) {
        Map<Integer, List<Edge>> graph = new HashMap<>();

        graph.put(0, Arrays.asList(new Edge(1, 1), new Edge(2, 3), new Edge(3, 4)));
        graph.put(1, Arrays.asList(new Edge(0, 1), new Edge(4, 2)));
        graph.put(2, Arrays.asList(new Edge(0, 3), new Edge(3, 4), new Edge(4, 5)));
        graph.put(3, Arrays.asList(new Edge(0, 4), new Edge(2, 4)));
        graph.put(4, Arrays.asList(new Edge(1, 2), new Edge(2, 5)));

        primAlgorithm(graph, 0);
    }
}

4. 프림 알고리즘의 성능 분석

4.1 시간 복잡도

• O((V + E) log V): 우선순위 큐 사용 시

4.2 공간 복잡도

• O(V + E): 그래프 저장 및 우선순위 큐 사용

5. 프림 알고리즘의 장점과 단점

5.1 장점

• 밀집 그래프(Dense Graph)에 적합
• 우선순위 큐 사용 시 효율적
• 구현이 직관적이고 이해하기 쉬움

5.2 단점

• 희소 그래프(Sparse Graph)에서는 비효율적
• 우선순위 큐를 사용하는 구현에서 추가 메모리 필요

5.3 희소 그래프와 밀집 그래프란?

• 희소 그래프(Sparse Graph): 간선의 수가 정점의 수에 비해 적은 그래프 (E ≪ V²)
• 밀집 그래프(Dense Graph): 간선의 수가 정점의 수에 비례하거나 많은 그래프 (E ≈ V²)

6. 프림 알고리즘의 활용 사례

• 네트워크 설계: 최소 비용으로 컴퓨터나 장치를 연결하는 최적 경로 찾기
• 도로망 최적화: 도시 간 최소 거리로 도로 설계
• 전기 회로 설계: 전선의 길이를 최소화하는 회로 설계

7. 크루스칼 알고리즘 vs. 프림 알고리즘

특징	크루스칼 알고리즘	프림 알고리즘
시간 복잡도	O(E log E)	O((V + E) log V)
구현 방식	간선 중심(E)	정점 중심(V)
적합한 그래프	희소 그래프 (간선 수가 적을 때)	밀집 그래프 (간선 수가 많을 때)
사이클 검사	유니온-파인드로 검사	방문한 노드로 검사

8. 결론

프림 알고리즘은 정점을 기준으로 최소 신장 트리를 구하는 강력한 알고리즘으로, 밀집 그래프에서 특히 효율적이다. 희소 그래프에서는 크루스칼 알고리즘이 더 적합할 수 있으며, 문제의 특성과 그래프의 밀도를 고려해 적절한 알고리즘을 선택하는 것이 중요하다.