[알고리즘] 프림 알고리즘(Prim's Algorithm) 정리 및 백준 문제 추천

GPT가 생성한 프림 알고리즘 이미지

 

개념

최소 신장 트리

아래 링크 참조 

[알고리즘]크루스칼 알고리즘(kruskal's Algorithm) 정리

 

프림 알고리즘 

 최소 신장 트리를 찾기 위해 사용되는 알고리즘. 
트리에 포함된 정점을 제외한 나머지 정점과의 간선 중 가중치가 가장 작은 간선을 선택하는 방식

 

 아래와 같은 그래프가 있다고 가정하겠습니다. 

1 번 정점부터 시작으로 간선을 확인합니다. 트리에 포함된 정점은 주황색으로 표시하였습니다. 

1번에 연결된 간선은 1 - 3과 1 - 2 이 두 개로 가중치는 각각 3과 4입니다. 이중 가중치가 작은 것은 1 - 3이므로 다음과 같은 그래프가 됩니다. 

다음으로 트리와 연결된 간선을 확인합니다. 

이후 다시 최소 가중치를 가진 정점과 연결합니다. 

이와 같은 방식으로 몯든 정점을 트리와 연결하면 최소 신장 트리가 완성됩나. 

 

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

	크루스칼 알고리즘	프림
방식	정점 시반으로 트리 확장	간선 기반으로 트리 확장
	GREEDY 알고리즘
사이클 회피	사이클 발생 x	유니온 파인드로 사이클 여부를 검사
시간 복잡도	O(NlogV)) 또는 O(N2)	O(NlogN) 쪼는
비고	간선의 개수가 작은 희소 그래프	간선의 개수가 많은 밀집 그래프

 

 

코드 구현

수도 코드

Prim(graph, start):
    1. total_weight ← 0  // 최소 신장 트리의 총 비용을 저장하는 변수
    2. visited[] ← False  // 모든 정점을 방문하지 않은 상태로 초기화
    3. priority_queue ← 빈 큐  // 최소 가중치 간선을 선택할 우선순위 큐
    4. 시작 정점의 간선들을 priority_queue에 추가
    5. visited[start] ← True  // 시작 정점을 방문 처리

    6. while priority_queue가 비어있지 않으면:
        a. 가장 작은 가중치의 간선 (weight, u, v)을 큐에서 꺼냄
        b. if v가 이미 방문된 정점이라면:
            i. continue  // 다음 간선으로 넘어감
        c. visited[v] ← True  // v 정점을 방문 처리
        d. total_weight에 weight를 더함
        e. v와 연결된 간선들을 큐에 추가, 단 방문되지 않은 정점만 추가

    7. return total_weight  // 최소 신장 트리의 총 가중치 반환

자바 코드

import java.util.*;

// 간선 클래스 (정점과 가중치를 포함)
class Edge implements Comparable<Edge> {
    int vertex;
    int weight;

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

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;  // 가중치 기준으로 정렬
    }
}

public class PrimAlgorithm {

    // 프림 알고리즘
    public static int prim(List<List<Edge>> graph, int start) {
        int totalWeight = 0;  // 최소 신장 트리의 총 가중치
        boolean[] visited = new boolean[graph.size()];  // 방문 여부 체크
        PriorityQueue<Edge> pq = new PriorityQueue<>();  // 우선순위 큐(최소 힙)

        // 시작 정점의 간선들을 우선순위 큐에 추가
        visited[start] = true;
        pq.addAll(graph.get(start));

        // 큐가 비어 있지 않은 동안 반복
        while (!pq.isEmpty()) {
            Edge currentEdge = pq.poll();  // 가장 작은 가중치의 간선을 꺼냄

            // 이미 방문한 정점이면 건너뜀
            if (visited[currentEdge.vertex]) continue;

            // 해당 정점을 방문 처리하고 가중치를 더함
            visited[currentEdge.vertex] = true;
            totalWeight += currentEdge.weight;

            // 새로 방문한 정점에서 갈 수 있는 간선들을 큐에 추가
            for (Edge edge : graph.get(currentEdge.vertex)) {
                if (!visited[edge.vertex]) {
                    pq.add(edge);
                }
            }
        }

        return totalWeight;
    }

    public static void main(String[] args) {
        int V = 5;  // 정점의 수

        // 그래프 초기화 (인접 리스트 방식)
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 추가 (양방향 그래프라고 가정)
        graph.get(0).add(new Edge(1, 2));
        graph.get(0).add(new Edge(3, 6));
        graph.get(1).add(new Edge(0, 2));
        graph.get(1).add(new Edge(2, 3));
        graph.get(1).add(new Edge(3, 8));
        graph.get(2).add(new Edge(1, 3));
        graph.get(2).add(new Edge(3, 5));
        graph.get(3).add(new Edge(0, 6));
        graph.get(3).add(new Edge(1, 8));
        graph.get(3).add(new Edge(2, 5));

        // 프림 알고리즘 실행 (0번 정점에서 시작)
        int mstWeight = prim(graph, 0);
        System.out.println("최소 신장 트리의 가중치 합: " + mstWeight);
    }
}

 

파이썬 코드

Prim(graph, start):
    # graph: 인접 리스트 형태의 그래프 (정점과 연결된 간선 정보 포함)
    # start: 시작 정점

    # 트리의 총 비용 (MST의 가중치 합)
    total_weight = 0
    
    # 방문한 정점을 기록하는 리스트
    visited = [False] * len(graph)
    
    # 우선순위 큐를 초기화 (시작 정점에서 연결된 간선을 모두 추가)
    priority_queue = []
    Add edges connected to 'start' into priority_queue
    
    # 시작 정점을 방문 처리
    visited[start] = True

    # 우선순위 큐가 비어 있지 않을 때까지 반복
    while priority_queue is not empty:
        # 큐에서 가장 작은 가중치의 간선을 꺼냄
        weight, u, v = priority_queue.pop()
        
        # v가 이미 방문된 정점이면 무시
        if visited[v]:
            continue

        # v를 방문 처리
        visited[v] = True

        # 해당 간선의 가중치를 총 비용에 더함
        total_weight += weight
        
        # v와 연결된 다른 간선들을 우선순위 큐에 추가
        for edge in graph[v]:
            if not visited[edge.to]:
                priority_queue.push(edge.weight, v, edge.to)
    
    return total_weight

 

 

추천 문제(백준)

 

• 1197번 - 최소 스패닝 트리
• 1922번 - 네트워크 연결
• 4386번 - 별자리 만들기
• 1647번 - 도시 분할 계획
• 2887번 - 행성 터널