[APS] MST : 프림(Prim)

프림 알고리즘

---

Prim 알고리즘

- 하나의 정점에서 시작하여, 연결된 간선들 중 최소비용 만을 선택하면서 MST를 만드는 알고리즘

• Kruskal이 간선을 선택하는 알고리즘이라면, Prim은 정점을 선택하는 알고리즘
• 일종의 그리디 알고리즘 이며, MST의 일정한 형태를 담보하지 않음

---

Prim 특징

• 정점을 기준으로 하므로, 정점이 적고 간선이 많은 밀집 그래프(dense graph)에서 유리
• 시간 복잡도 : dist[] 배열을 이용하는 경우 : O(V^2), heap 구조를 이용하는 경우 : O(ElogV);

---

---

Prim : 가중치 배열  + 인접 행렬 구현

---

1) 초기화

• 각 정점에 대하여, 정점의 방문 여부, 부모 정점, 가중치를 저장할 배열을 선언
• 시작 정점을 선택하고 가중치를 0으로 초기화, 나머지는 매우 큰 값 INF로 초기화

boolean[] visited = new boolean[V]; // 방문 배열
int[] p = new int[V]; // 출발 정점 배열
int[] dist = new int[V]; // 가중치(거리) 배열
Arrays.fill(dist, INF); // 전체 가중치를 매우 큰값 INF로 초기화
dist[0] = 0; // 시작 정점(여기서는 0번 정점)은 0으로 초기화

 

2) 연결 노드 선택

• 방문하지 않은 정점 중, 가장 가중치가 작은 정점을 선택하여 연결

int min = INF;
int idx = -1;
for(int j = 0; j<V; j++){
	if(!visited[j] && dist[j] < min) {
    // 방문한 적 없는 정점 중 최저값 갱신
		min = dist[j];
		idx = j;
	}
}
visited[idx] = true;
ans += dist[idx];

  

3) 가중치 갱신

• 선택된 정점과 연결된 아직 방문하지 않은 정점들의 가중치 확인
• 현재 정점에서 출발했을 떄의 가중치가 더 작다면 가중치와 출발정점값을 갱신

for(int j = 0; j<V; j++) {
	if(!visited[j] && adjArr[idx][j] != 0 && dist[j] > adjArr[idx][j]) {
	// 미방문 + 뽑은 정점이랑 연결되어있음 + 뽑은 정점이랑의 연결값이 지금까지 값보다 작음 
		dist[j] = adjArr[idx][j];
        // 연결값 갱신
		p[j] = idx;
        // 출발 정점값 갱신
	}
}

 

▼ 전체 코드 : 위의 2, 3 과정을 정점의 갯수만큼 반복함

import java.io.*;
import java.util.*;

public class Main {
	static final int INF = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		int[][] adjArr = new int[V][V];
		
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			
			adjArr[A][B] = C;
			adjArr[B][A] = C;
		}
		int ans = 0;
		boolean[] visited = new boolean[V];
		int[] p = new int[V]; //
		int[] dist = new int[V];
		
		Arrays.fill(dist, INF);
		dist[0] = 0; // 0번 정점으로 시자칼꼬얌
		for(int i = 0; i < V; i++) {
			//1. 내가 가장 작은 값을 뽑겠다.
			int min = INF;
			int idx = -1;
			// 아직 안뽑힌 친구들 중 가장 작은 값을 뽑겠다.
			for(int j = 0; j<V; j++) {
				if(!visited[j] && dist[j] < min) {
					min = dist[j];
					idx = j;
				}
			} 
			System.out.println(idx);
			visited[idx] = true;
			ans += dist[idx];
			//2. 뽑은 정점을 이용해서 갱신할 수 있는게 있다면 모조리 갱신
			for(int j = 0; j<V; j++) {
				if(!visited[j] && adjArr[idx][j] != 0 && dist[j] > adjArr[idx][j]) {
					dist[j] = adjArr[idx][j];
					p[j] = idx;
				}
			}
		}
		
		System.out.println(ans);
	}
}

 

---

구현 과정 (우선순위 큐 + 인접 리스트)

 

• 최소 힙을 이용하여, 반복문을 돌지 않고 매번 최저 가중치를 갖는 노드 값을 얻을 수 있음에 착안

1. 간선 클래스 선언

• Edge는 해당 간선의 도착점과 가중치를 담고 있는 객체 
• 우선순위 큐 내부에서 비교해야 하므로, Comparable<Edge>를 구현해야 함

static class Edge implements Comparable<Edge>{
		int ed, w;

		public Edge(int ed, int w) {
			super();
			this.ed = ed;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return this.w - o.w;
			// return Integer.compare(this.w , o.w);
		}
	}

 

2. 초기화

• 배열 대신 우선 순위 큐를 선언하고, 시작 정점을 선택하고 연결된 정점을 모두 넣어줌

PriorityQueue<Edge> pq = new PriorityQueue<>();
visited[0] = true; // 첫 정점 방문 처리
pq.addAll(adjList[0]); // 연결된 정점 넣기

// 아래의 방법으로도 가능
for(edge e : adjList[0]){
	pq.add(e);
}

 

3. 방문 처리

• 방문한 정점의 갯수가 V개가 될 때 까지 반복
• 우선순위 큐에서 나온 정점이 방문되지 않았다면 방문 처리

int pick = 1; // 확보한 정점의 갯수
int ans = 0;
		
while(pick < V) {
	Edge e = pq.poll();
	if(visited[e.ed]) continue;
			
	ans += e.w;
	pq.addAll(adjList[e.ed]);
	visited[e.ed] = true;
	pick++;
}

 

▼ 전체 코드

public class Prim {
	static final int INF = Integer.MAX_VALUE;
	
	static class Edge implements Comparable<Edge>{
		int ed, w;

		public Edge(int ed, int w) {
			super();
			this.ed = ed;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return this.w - o.w;
			// return Integer.compare(this.w , o.w);
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		List<Edge>[] adjList = new ArrayList[V];
		
		for(int i = 0; i<V; i++) {
			adjList[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			
			adjList[A].add(new Edge(B,C));
			adjList[B].add(new Edge(A,C));
		}
		
		boolean[] visited = new boolean[V];
		
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		
		visited[0] = true;
		
		for(int i = 0; i<adjList[0].size(); i++) {
			pq.add(adjList[0].get(i));
		}
		
		// for(edge e : adjList[0]){
		//	pq.add(e);
		//}
		
		// pq.addAll(adjList[0]);
		
		int pick = 1; // 확보한 정점의 갯수
		int ans = 0;
		
		while(pick < V) {
			Edge e = pq.poll();
			if(visited[e.ed]) continue;
			
			ans += e.w;
			pq.addAll(adjList[e.ed]);
			visited[e.ed] = true;
			pick++;
		}
		
		System.out.println(ans);
	}
}