[알고리즘] 최소 스패닝 트리 : 프림 (Prim)

프림 (Prim)

• 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나
• 하나의 시작점으로 구성된 트리에 간선을 하나씩 추가하는 방식

동작 과정

1.

그래프를 확인하고 출발 노드를 우선순위 큐에 저장한다. (start, 0)

이때 저장되는 가중치는 자기 자신이므로 0이다.

우선순위 큐 : (0, 0) 

2.

우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다.

이때 한번 지나갔던 정점은 추가하지 않는다.

우선순위 큐 : (2, 1), (1, 5)

3.

우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다.

이때 한번 지나갔던 정점은 추가하지 않는다.

우선순위 큐 : (3, 2), (1, 5)

 

4.

우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다.

이때 한번 지나갔던 정점은 추가하지 않는다.

우선순위 큐 : (1, 1), (6, 3), (1, 5), (4, 5)

5.

우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다.

이때 한번 지나갔던 정점은 추가하지 않는다.

우선순위 큐 : (5, 3), (6, 3), (6, 3), (1, 5), (4, 5)

 

6.

우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다.

이때 한번 지나갔던 정점은 추가하지 않는다.

우선순위 큐 : (6, 2), (6, 3), (6, 3), (1, 5), (4, 5)

7.

우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다.

이때 한번 지나갔던 정점은 추가하지 않는다.

우선순위 큐 : (6, 3), (6, 3), (1, 5), (4, 5)

8.

우선순위 큐를 poll 했을 때 나온 노드가 이미 지나간 정점이라면 pass 한다.

우선순위 큐 : (6, 3), (6, 3), (1, 5), (4, 5)

우선순위 큐 : (6, 3), (1, 5), (4, 5)

우선순위 큐 : (1, 5), (4, 5)

우선순위 큐 : (4, 5)

9.

우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다.

이때 한번 지나갔던 정점은 추가하지 않는다.

우선순위 큐 :

static int n; // 정점의 개수
static boolean visited[] = new boolean[n];
static int count = 0;
static ArrayList<edge>[] graph = new ArrayList[n]; // 간선 입력
		
for(int i = 0; i < n; i++) {
	graph[i] = new ArrayList<>();
}

static void prim() {
	pq.add(new edge(0,0));
		
	while(!pq.isEmpty()) {
		edge cur = pq.poll();
			
		if(visited[cur.node]) { // 방문했던 정점 pass
			continue;
		}
		visited[cur.node] = true;
		result += cur.weight;
			
		for(edge next : graph[cur.node]) {
			if(!visited[next.node]) {
				pq.offer(next);
			}
		}
			
		if(++count == n) { // 정점의 개수만큼 방문
			break;
		}
	}
}

static class edge implements Comparable<edge>{
	int node;
	int weight;
		
	edge(int node, int weight){
		this.node = node;
		this.weight = weight;
	}

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