Coding Test(Prim Algorithm)

<Prim Algorithm>

Prim의 핵심은 트리 집합을 단계적으로 확장하는 것이고,

새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해줘야 한다.

PriorityQueue를 이용한 최소 힙으로 구현할 수 있고, 다익스트라 알고리즘과 구현 방식이 유사하다.

BFS + PriorityQueue

 

<동작원리>

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

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

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

 

 

<Kruskal vs Prim>

프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리르 구성 하므로 그 과정에서 사이클을 이루지 않지만 크루스칼은 시작점을 따로 정하지 않고 최소 비용의 간선을 차례로 대입 하면서 트리를 구성하기 때문에 사이클이 이루어지는 항상 확인 해야한다.

Kruskal	Prim
간선 위주의 알고리즘 간선의 개수 작을 때 유리 - 간선을 기준으로 정렬하는 과정이 오래걸림	정점 위주의 알고리즘 간선의 개수 많을 때 유리

 

 

1197번: 최소 스패닝 트리

package practice;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main_1197_1 {
	static int V, E,res;
	static int[] parent;
	static List<int[]>[] data;
	static boolean[] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
	    parent = new int[V+1]; //index 1부터 시작하고 싶어서 V+1
	    data = new ArrayList[V+1]; //Prim은 그래프형태의 데이터가 필요하기 때문에 List[][]로
	    visited = new boolean[V+1];
	    
	    //초기화
	    for (int i = 1; i < V+1; i++) {
			data[i] = new ArrayList<>();
		}
	    
	    
	    for (int i = 0; i < E; i++) {
	    	st = new StringTokenizer(br.readLine());
	    	int from = Integer.parseInt(st.nextToken());
	    	int to = Integer.parseInt(st.nextToken());
	    	int cost = Integer.parseInt(st.nextToken());
	    	
	    	//from -> to  == to -> from
	    	data[from].add(new int[] {to, cost});
	    	data[to].add(new int[] {from, cost});
		}
	    
	    prim();
	    System.out.println(res);
		
	}
	
	public static void prim() {
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->(o1[1]-o2[1]));
		
		visited[1] = true;
		int cnt = 1;
		pq.addAll(data[1]);

		
		while(!pq.isEmpty()) {	
			int[] temp = pq.poll();
			int to = temp[0];
			int cost = temp[1];
			
			if(visited[to])
				continue;

			visited[to] = true;
			res += cost;
			cnt++;
			
			if (cnt == V)
				return;
			
			pq.addAll(data[to]);


		}	
	}
}