Prim 알고리즘 [프림][MST][JAVA]

[광고 누르면 오늘의 행운 상승!!]

프림 알고리즘 이란?

- 프림 알고리즘은 MST(최소신장트리)를 구현하는 한 방법으로 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다.

- 각 정점들은인접한 정점 중 최소 비용으로 이동가능한 정점을 선택하여 추가한다.

- 우선순위 큐를 이용하여 임의의 정점부터 인접한 정점을 거리를 기준으로 정렬한다.

- 최소 거리의 정점을 꺼내서 다시 인접한 정점을 넣고 정렬한다.

- 반복한다.

package Study3;

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

public class bj_1700_최소스패닝트리_서울_06_박이삭_Prim  {
	public static class Edge implements Comparable<Edge> {
		int node;
		double dis;

		public Edge(int node, double dis) {
			this.node = node;
			this.dis = dis;
		}
		@Override
		public int compareTo(Edge o) {
			return Double.compare(this.dis, o.dis);
		}
	}

	static int V,E, ans = 0, cnt = 0;
	static ArrayList<ArrayList<Edge>> graph;
	static boolean[] visit;
	static PriorityQueue<Edge> pq;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		pq = new PriorityQueue<>();
		
	  //정점의 수
		V = Integer.parseInt(st.nextToken());
    //간선의 수
		E = Integer.parseInt(st.nextToken());
		visit = new boolean[V];
		
		//정점의 연결을 저장할 리스트
		graph = new ArrayList<>();
		
		for (int i = 0; i < V; i++) {
			graph.add(new ArrayList<>());
		}
		
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken()) -1;
			int B = Integer.parseInt(st.nextToken()) -1;
			int dis = Integer.parseInt(st.nextToken());
			
			graph.get(A).add(new Edge(B, dis));
			graph.get(B).add(new Edge(A, dis));
		}
		//임의의 정점(0)부터 시작한다.
		pq.add(new Edge(0,0));
		
		while (!pq.isEmpty()) {
			Edge edge = pq.poll();
			//방문했다면 continue;
			if(visit[edge.node]) continue;
			visit[edge.node] = true;
			//거리 증가
			ans += edge.dis;
			//그래프에 연결된 노드를 돌면서 방문하지 않았다면 pq에 넣어준다.
			for (Edge next : graph.get(edge.node)) {
				if(!visit[next.node]) {
					pq.add(next);
				}
			}
			//모든 정점을 순회하였다.
			if (++cnt == V) break;
		}
		System.out.println(ans);
	}
}