Java - 프림 알고리즘(Prim)

◎프림 알고리즘(Kruskal)

 

프림 알고리즘은 노드를 중점으로 그리디하게 최소 스패닝 트리(MST)를 찾는 알고리즘이다.

영역을 단계적으로 넓혀간다고 생각하면 이해하기 편하다.

 

※MST의 정의와 MST를 구하는 다른 방법인 크루스칼 알고리즘에 대한 설명

https://kkwong-guin.tistory.com/61

Java - 크루스칼 알고리즘(Kruskal)

 

1. 임의의 정점을 트리에 추가한다.

2. 임의의 정점에서 인접한 정점 중 최소 비용으로 이동가능한 정점을 선택하여 트리에 추가한다.

3. 트리의 정점들에서 인접한 정점 중 이미 트리에 존재하는 정점을 제외하고 최소 비용으로 이동 가능한 정점을 선택하여 트리에 추가한다.

4. 모든 정점이 트리에 포함되면 알고리즘을 종료한다.

 

출처: https://toastfactory.tistory.com/184

(a) 정점 a를 트리에 추가한다.

(b) 인접한 정점 b,h 중 이동비용이 적은 b를 선택하여 정점 b를 트리에 추가한다.

(c) 트리에 인접한 정점 c, h 중 이동비용이 적은 c를 선택하여 정점 c를 트리에 추가한다.

(h를 선택해도 무관하다, 최소 스패닝 트리는 여러 개일 수 있기 때문이다.)

....

(i) 모든 노드가 트리에 추가되었으므로 알고리즘을 종료한다.

 

---

◎프림 알고리즘(Prim)의 구현

 

1. 정점의 수만큼 힙(비용을 기준으로 오름차순 정렬하는 힙) 생성

2. 각 정점에 관련된 힙에 인접정점과 인접 정점까지의 비용 추가

3. 임의의 정점 트리에 추가

4. 인접 정점 중 비용이 가장 작은 정점 선택

5. 모든 정점이 트리에 포함될 때까지 반복

 

package MST;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Prim_algorithm {

	PriorityQueue<int[]> pq[];
	//어떤 정점이 트리에 포함되었는지 나타내는 배열
	ArrayList<Integer> visited = new ArrayList<>();
	int nodes; // 노드 개수
	int[][] costs; // [노드1,노드2,비용]으로 이루어진 이차원배열

	@SuppressWarnings("unchecked")
	public Prim_algorithm(int nodes, int[][] costs) {
		this.nodes = nodes;
		this.costs = costs;
		
		//각 정점의 인접 정점까지의 비용을 저장하는 힙을 정점의 개수만큼 생성
		pq = new PriorityQueue[nodes]; 
		for (int i = 0; i < nodes; i++) {
			pq[i] = new PriorityQueue<int[]>(new Comparator<int[]>() {

				@Override
				public int compare(int[] a, int[] b) {
					// TODO Auto-generated method stub
					// 간선의 가중치(비용)을 기준으로 정렬
					return a[1] - b[1];

				}

			});
		}
		
		//힙에 데이터 추가
		//ex. [1,2,3]이면, 노드 1과 관련된 힙에는 [2,3]을 노드 2와 관련된 힙에는 [1,3]을 저장
		for (int i = 0; i < costs.length; i++) {
			int[] tmp1 = new int[2];

			tmp1[0] = costs[i][1];
			tmp1[1] = costs[i][2];
			pq[costs[i][0]].add(tmp1);
			
			int[] tmp2 = new int[2];
			tmp2[0] = costs[i][0];
			tmp2[1] = costs[i][2];
			pq[costs[i][1]].add(tmp2);
		}
	}

	public int solution() {
		int answer = 0;

		// 임의의 정점을 트리에 포함
		this.visited.add(0);

		// 모든 정점이 트리에 포함되면 알고리즘 종료
		while (visited.size() < this.nodes) {

			int[] selected = { 0, 1000 };
			
				//트리에 포함된 노드의 인접한 노드들 중 가중치(비용)이 가장 작은 노드 선택
				for (int i : visited) {
					while (!pq[i].isEmpty()) {
						if(!visited.contains(pq[i].peek()[0])) {
						int[] tmp = pq[i].peek();
							if (tmp[1] < selected[1]) {
								selected = tmp;
								break;
							}
							break;
						}else {
							pq[i].poll();
						}
					}
			}
			
			//간선이 이어준 노드를 트리에 포함	
			visited.add(selected[0]);
			answer += selected[1]; //비용 업데이트
		}
			
			

		return answer;
	}
	
	public static void main(String[] args) {
    	
    	int[][] costs = {{0, 1, 5}, {0, 3, 2}, {0, 4, 3}, {1, 4, 1}, {3, 4, 10}, {1, 2, 2}, {2, 5, 3}, {4, 5, 4}} ;
    	Prim_algorithm sol = new Prim_algorithm(6,costs);
    	System.out.println(sol.solution());
    	
    }
}

실행결과:

11

빨간색 간선 = 연결된 간선

흑색 간선 = 연결되지 않은 간선

최소 스패닝 트리는 위와 같으므로 2+1+3+2+3= 11이다.

---

◎프림 알고리즘(prim)의 효율성

크루스칼 알고리즘은 간선을 중점으로 MST를 찾으므로, 그래프 내에 간선의 수가 적은 희소 그래프(Sparse Graph) 일 경우에 적합이다.

프림 알고리즘은 노드를 중점으로 MST를 찾으므로, 그래프 내에 간선이 많이 존재하는 밀집 그래프(Dense Graph)일 경우에 적합하다.

---

Github codes

https://github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/MST

jerry-ryu/java_problemsolving_algorithm