[알고리즘] PRIM 알고리즘 / 수도 코드 (Java)

프림 알고리즘

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 '최소 신장 트리(MST)'를 만들어 가는 방식

최소신장트리?

노란색 선으로 연결된 부분이 '최소 신장 트리' 이다.

신장 트리는 n개의 정점으로 이루어진 무향그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리를 말한다. 

최소 신장 트리 (Minimum Spanning Tree)는 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리를 말한다.

무향 그래프에서 신장 트리는 여러개가 될 수 있지만 최소 신장 트리는 하나만 존재할 수 있다.

 

그래프에서 최소 비용 문제를 구하는 방법

- 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리

- 두 정점 사이의 최소 비용의 경로 찾기

=> 이때 사용되는 알고리즘으로는 PRIM 알고리즘과 Kruskal 알고리즘이 있다.

오늘은 PRIM 알고리즘에 대해 알아보자

 

PRIM 알고리즘 과정

1. 임의 정점을 하나 선택해서 시작

2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택

3. 모든 정점이 선택될 때 까지 1,2 번 과정을 반복

 

수도 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
// 프림 알고리즘이용
/*
5
0 5 10 8 7 
5 0 5 3 6 
10 5 0 1 3 
8 3 1 0 1 
7 6 3 1 0
==>10

7
0 32 31 0 0 60 51
32 0 21 0 0 0 0
31 21 0 0 46 0 25
0 0 0 0 34 18 0
0 0 46 34 0 40 51
60 0 0 18 40 0 0
51 0 25 0 51 0 0
==>175
 */

public class MST2_Prim{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        int[][] input = new int[N][N];
        boolean[] visited = new boolean[N];
        int[] minEdge = new int[N];
        // 신장트리에 연결된 정점에서 자신으로의 최소 간선 비용
        
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                input[i][j] = Integer.parseInt(st.nextToken());
            }
            minEdge[i] = Integer.MAX_VALUE;
        }// i노드에서 j노드까지의 비용을 모두 배열에 저장
        
        int minVertex,min,result = 0;
        minEdge[0] = 0; // 임의의 시작점 비용 0 셋팅
        
		for(int c = 0 ; c< N; c++){// 모든 정점 수만큼 반복
            min = Integer.MAX_VALUE;// 초기값으로 정수의 최대치를 주고 시작
            minVertex = 0;
            // 신장트리에 연결되지 않은정점중 minEdge 비용이 최소인 정점
            for(int i=0; i<N; ++i) { 
            	if(!visited[i] &&  min > minEdge[i] ) {
            		min = minEdge[i];
            		minVertex = i;
            	}
            }	
            
            result += min; 
            visited[minVertex] = true; 
            
            for (int i = 0; i < N; i++) { 
                if (!visited[i] && input[minVertex][i] != 0 &&  minEdge[i] > input[minVertex][i]  ) {
                	minEdge[i] = input[minVertex][i];
                }
            }
        }
        System.out.println(result);
    }
}// end class

input: 정점과 간선 비용 정보가 담겨있는 배열
visited : 정점이 연결됐으면 true로 바꿔준다.
minEdge: 신장트리에 연결된 정점에서 자신으로의 최소 간선 비용

1. 신장 트리에 연결되지 않는 정점 중 가장 간선 비용을 min에, 정점을 minVertex에 담는다.
2. result+= min을 통해 비용을 더해준다.
3. visited[minVertex] = true를 통해 연결해준다.
4. 연결되어있지 않고(!visited[i]), minVertex기준으로 연결된 정점 간선 비용 값이 기존 minEdge에 저장된 값보다 작다면 minEdge를 채운다.

PriorityQueue를 사용한 PRIM 알고리즘

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
//프림 알고리즘 이용 : PriorityQueue 버전
/*
5
0 5 10 8 7 
5 0 5 3 6 
10 5 0 1 3 
8 3 1 0 1 
7 6 3 1 0
==>10

7
0 32 31 0 0 60 51
32 0 21 0 0 0 0
31 21 0 0 46 0 25
0 0 0 0 34 18 0
0 0 46 34 0 40 51
60 0 0 18 40 0 0
51 0 25 0 51 0 0
==>175
 */

public class MST3_Prim_PQ{
    static class Vertex implements Comparable<Vertex>{
    	int no; 
    	int edge;
		public Vertex(int no, int edge) {
			super();
			this.no = no;
			this.edge = edge;
		}
		@Override
		public int compareTo(Vertex o) {
			return this.edge - o.edge;
		}
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        int[][] input = new int[N][N];
        boolean[] visited = new boolean[N];
        int[] minEdge = new int[N];
        PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>();
        
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                input[i][j] = Integer.parseInt(st.nextToken());
            }
            minEdge[i] = Integer.MAX_VALUE;
        }// i노드에서 j노드까지의 비용을 모두 배열에 저장
        
        int result = 0, nodeCount= 0;
        minEdge[0] = 0;//시작점 비용 0 셋팅
        queue.offer(new Vertex(0,0));
        
		while(!queue.isEmpty()){

			Vertex minVertex = queue.poll();// PQ 에서 간선비용이 최소인 정점 뽑기
			if(visited[minVertex.no]) continue;
			
            result += minVertex.edge;   
            visited[minVertex.no] = true; 
            if(++nodeCount == N) break; 
            
            for (int i = 0; i < N; i++) { 
                if (!visited[i] && input[minVertex.no][i] != 0 &&   minEdge[i] > input[minVertex.no][i] ) {
                	minEdge[i] = input[minVertex.no][i];
                	queue.offer(new Vertex(i, input[minVertex.no][i])); 
                }
            }
        }
        System.out.println(result);
    }
}// end class

1. PriorityQueue<Vertex>의 Vertex 클래스(정점 정보를 가지고 있음)는 Comparable<Vertex>를 implements 하고 있기 때문에 정렬이 edge(간선 비용)기준으로 오름차순 정렬된다.

즉, poll() 하면 가장 작은 간선 비용을 가진 정점이 poll된다.

2. 가장 먼저 뽑히는 정점을 연결(visited[minVertex.no] = true)하고, minVertex.no 기준으로 연결된 정점 간선 비용 값이 기존 minEdge에 저장된 값보다 작다면 minEdge를 채운다.

3. PriorityQueue에 새로운 정점 정보를 offer(add)한다.

4. PriorityQueue가 빌 때까지 1,2,3번을 반복한다.