[JAVA] 최소 비용 신장 트리 MST - 프림 알고리즘

 

신장트리(Spanning Tree)는 그래프 내의 모든 정점을 포함하는 트리입니다. MST(Minimum Spanning Tree)는 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 이야기합니다. MST는 크루스칼 그리고 프림 알고리즘이 있습니다. 여기서는 프림알고리즘을 다루겠습니다.

 

• 그래프 내의 간선의 숫자가 적은 희소 그래프의 경우 : 크루스칼 알고리즘
• 그래프 내의 간선의 숫자가 많은 밀집 그래프의 경우 : 프림 알고리즘

 

동작방식

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법

1. 시작 단계에서는 시작 정점만이 MST 에 포함합니다.
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장합니다.
   • 즉, 가장 낮은 가중치를 먼저 선택합니다.
3. 위의 과정을 트리가 N-1 개의 간선을 가질 때까지 반복합니다.

시간복잡도

기본적으로 O(N^2) 의 시간복잡도를 가지고 있습니다. 우선순위 큐를 사용한다면 O( E logV)의 시간복잡도를 가집니다.

참고사이트

https://hibee.tistory.com/300

[AL] 7. 최소 비용 신장 트리(MST) 알고리즘

기본코드

7 11 1 2 2 2 3 5 1 3 20 1 4 10 4 5 1 5 6 23 3 6 3 3 5 6 7 6 9 7 3 2 2 7 7

package study.graph;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class B implements Comparable<B>{
	int n;
	int dist;
	
	B (int a, int b){
		this.n = a;
		this.dist = b;
	}

	@Override
	public int compareTo(B tar) {
		if(tar.dist < this.dist) return 1;
		if(tar.dist > this.dist) return -1;
		return 0;
	}
	
	
}

public class MST_프림 {

	public static void main(String[] args) throws IOException {
		
		System.setIn(new FileInputStream("input\\prim.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		int[] used = new int[N+1]; // 방문 여부 (0: 미방문, 1: 방문)
		
		ArrayList<ArrayList<B>> alist = new ArrayList<ArrayList<B>>();
		for(int i=0; i<=N; i++) {
			alist.add(new ArrayList<B>());
		}
		
		StringTokenizer st = null;
		for(int m=1; m<=M; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			
			alist.get(a).add(new B(b, dist));
			alist.get(b).add(new B(a, dist));
		}
		
		PriorityQueue<B> pq = new PriorityQueue<B>();
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(1); // 임의의 한 노드를 지정
		int sumDist = 0;
		
		while(!q.isEmpty()) {
			int currentNode = q.poll();
			used[currentNode] = 1; // 방문표시
			
			// 현재 노드에 연결된 간선을 pq에 넣음(방문한 노드는 제외)
			for(int i=0; i<alist.get(currentNode).size(); i++) {
				if(used[alist.get(currentNode).get(i).n] != 1) {
					pq.add(alist.get(currentNode).get(i));
				}
			}
			
			while(!pq.isEmpty()) {
				B tar = pq.poll();
				
				if(used[tar.n] == 1) continue; // 방문한 노드면 pass
				
				used[tar.n]= 1;// 방문표시
				sumDist += tar.dist;
				q.add(tar.n); // 연결된 노드를 큐에 넣어줌
				break; // pq에서 방문하지 않은 노드로 가는 가장 dist가 작은 것을 석택해주었으니 여기서 멈춤
			}
		}
		
		bw.write("# " + sumDist);
		
		bw.close();
		br.close();
		
	}
}