MST - 프림 알고리즘(Prim's Algorithm)이란?

y20ng·2024년 9월 24일

알고리즘

목록 보기

3/6

🌳MST(최소 신장 트리)란?

가중치가 있는 그래프에서, 모든 정점을 연결하는 간선들의 부분집합 중, 가중치 합이 최소인 트리

MST는 그래프의 모든 정점을 연결하는 간선들의 부분집합 중에서 가중치 합이 최소가 되는 트리를 말한다. 쉽게 말해, 하나의 연결된 네트워크에서 가장 적은 비용으로 모든 정점을 연결하는 방법을 찾는 문제라고 볼 수 있다!

💡 MST의 특징

모든 정점을 포함해야 함
사이클이 없어야 함
간선 가중치의 합이 최소가 됨

🔍 MST를 구하는 대표적인 알고리즘

MST를 구할 때 가장 많이 사용되는 알고리즘에는 두 가지가 있다.
바로 크루스칼 알고리즘과 프림 알고리즘이다. 두 알고리즘 모두 목적은 같지만, 문제를 해결하는 방식에서 차이가 있다.

비교 항목	크루스칼 알고리즘	프림 알고리즘
특징	간선을 중심으로 트리 확장	정점 중심으로 트리 확장
사이클 여부 판별	유니온-파인드 자료 구조 사용	우선순위 큐를 사용하여 간선 선택
적합한 그래프	희소 그래프 (간선이 적은 그래프)	밀집 그래프 (간선이 많은 그래프)
시간 복잡도	O(E log E)	O(E log V)

프림 알고리즘

💡 프림 알고리즘의 특징

정점 중심으로 트리를 확장
우선순위 큐를 사용하여 최소 가중치의 간선을 선택한다
초기 정점의 선택은 결과에 영향을 주지 않는다
: 어디서 시작하든 상관 없이 결과 값은 동일하다!

🔄 동작 과정

임의의 정점을 시작 정점으로 설정
선택한 정점과 인접한 정점들 중에서 가중치가 가장 작은 간선을 선택한다
모든 정점이 포함될 때까지 위의 과정을 반복한다.

🧐언제 프림 알고리즘을 사용해야 할까?

프림 알고리즘은 밀집 그래프에서 뛰어난 성능을 보인다.
즉, 정점과 간선이 많은 경우, 프림 알고리즘은 빠른 탐색을 보장한다.
하지만 희소 그래프에서는 상대적으로 불필요한 간선들이 많이 포함될 수 있기 때문에, 이 경우에는 크루스칼 알고리즘을 고려하는 것이 더 나을 수 있다!

💻 코드로 보는 프림 알고리즘

📌 포인트

우선순위 큐를 활용

트리 확장: 선택된 간선의 도착 정점이 아직 트리에 포함되지 않았다면, 그 정점을 트리에 추가하고 해당 정점에 연결된 간선들을 다시 우선순위 큐에 넣습니다

사이클 방지: 이미 방문한 정점(즉, 트리에 포함된 정점)은 건너뜁니다. 이를 위해 visited 배열을 사용해 사이클을 방지합니다.

public static void prim() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        totalWeight = 0;
        int pick= 1;

        // 시작 정점 선택 (0번 정점) 및 초기화
        visited[0] = true;
        pq.addAll(adjList[0]); // 시작 정점에 연결된 모든 간선을 우선순위 큐에 추가

	        while(pick!= N) {
            // 1. 우선순위 큐에서 가장 가중치가 작은 간선을 꺼냄
            Edge edge = pq.poll();

            if(visited[edge.to]) {
                // 2. 이미 방문한 정점이면 건너뜀
                continue;
            }

            // 간선의 가중치를 총합에 더함
            totalWeight += edge.weight;
            // 도착 정점을 방문 처리
            visited[edge.to] = true;
            pick++;

            // 3. 새로 방문한 정점(도착 정점)에 연결된 모든 간선을 우선순위 큐에 추가
            for(Edge nextEdge : adjList[edge.to]) {
                if(!visited[nextEdge.to]) {
                    pq.add(nextEdge);
                }
            }
        }
    }

인접리스트를 프림 알고리즘 활용 전체 코드


public class Main {
    static int N, M;
    static List<Edge>[] adjList;
    static int totalWeight;
    static boolean[] visited;

		// 클래스 생성
    static class Edge implements Comparable<Edge> {
        int from, to, weight;

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

        @Override
        public int compareTo(Edge o) {
            // 가중치 오름차순으로 정렬
            return Integer.compare(this.weight, o.weight);
        }
    }

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

        // 정점 수와 간선 수 입력
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        adjList = new ArrayList[N];
        visited = new boolean[N];

        // 인접 리스트 초기화
        for(int i = 0; i < N; i++) {
            adjList[i] = new ArrayList<>();
        }

        // 간선 정보 입력 및 인접 리스트 구성
        for(int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken()) - 1; // 인덱스는 0부터 시작하도록 조정
            int to = Integer.parseInt(st.nextToken()) - 1;
            int weight = Integer.parseInt(st.nextToken());

            // 무방향 그래프이므로 양쪽에 간선을 추가
            adjList[from].add(new Edge(from, to, weight));
            adjList[to].add(new Edge(to, from, weight));
        }

        prim();

        System.out.println(totalWeight);
    }

    public static void prim() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        totalWeight = 0;
        int selectedVertices = 1;

        // 시작 정점 선택 (0번 정점) 및 초기화
        visited[0] = true;
        pq.addAll(adjList[0]); // 시작 정점에 연결된 모든 간선을 우선순위 큐에 추가

        while(selectedVertices != N) {
            // 1. 우선순위 큐에서 가장 가중치가 작은 간선을 꺼냄
            Edge edge = pq.poll();

            if(visited[edge.to]) {
                // 2. 이미 방문한 정점이면 건너뜀
                continue;
            }

            // 간선의 가중치를 총합에 더함
            totalWeight += edge.weight;
            // 도착 정점을 방문 처리
            visited[edge.to] = true;
            selectedVertices++;

            // 3. 새로 방문한 정점(도착 정점)에 연결된 모든 간선을 우선순위 큐에 추가
            for(Edge nextEdge : adjList[edge.to]) {
                if(!visited[nextEdge.to]) {
                    pq.add(nextEdge);
                }
            }
        }
    }
}