최소신장트리(MST) feat. PRIM

---

---

PRIM 알고리즘

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식

서로소인 2개의 집합 정보를 유지

• 트리로 선택된 정점들
• 비트리 정점들

 

1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때 까지 2과정을 반복

 

PRIM 알고리즘 적용 예

 

1. 임의의 정점 선택 (0번 선택)  0번에서 연결할수 있는 간선은 18, 22 두개 이다

2.  1번에서 선택된 간선들 중에 비용이 적은 간선이 18을 선택하고 1번에서 갈수 있는 간선들을 확인한다.

0번에서 갈수있는 간선과 새로 추가된 1번에서 갈수 있는 간선들 중에 가장 최소의 값을 선택한다.

3. 22, 7, 14 중 최소값이 7을 선택하고 새롭게 연결된 3번을 트리에 추가한다.

 

이러한 방식으로 모든 정점이 연결될때 까지 반복하면 프림알고리즘으로 MST를 구하는 게 된다.

---

---

PRIM 알고리즘 코드

class Edge implements Comparable<Edge>{
	int w;
	int cost;
	
	Edge(int  w, int cost){
		this.w = w;
		this.cost = cost;
	}
	
	@Override
	public int compareTo(Edge o) {
		return this.cost - o.cost;
	}
}

public class prim_main {
	static List<Edge>[] graph;
	
	public static void prim(int start, int n) {
		boolean[] visit = new boolean[n + 1];
		
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.offer(new Edge(start, 0));
		
		int total = 0;
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			int v = edge.w;
			int cost = edge.cost;
			
			if(visit[v]) continue;
            
			visit[v] = true;
			total += cost;
			
			for(Edge e : graph[v]) {
				if(!visit[e.w]) {
					pq.add(e);
				}
			}
		}
		System.out.println(total);
	}

	
	public static void main(String[] args) throws IOException {
   		// 그래프 입력, 저장
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());
		
        // 그래프 선언, 간선 리스트로 표현
		graph = new ArrayList[n + 1];
		for (int i = 0; i < graph.length; i++) graph[i] = new ArrayList<>();
		
		StringTokenizer st;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			graph[v].add(new Edge(w, cost));
			graph[v].add(new Edge(v, cost));
		}
		
        // 프림 알고리즘 수행
		prim(1, n);
	}
}