[알고리즘] [18] 최소신장트리

1. 최소 신장 트리 (Minimum Spanning Tree)

• 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
• 신장 트리 : n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n - 1개의 간선으로 이루어진 트리
• 최소 신장 트리 : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

2. KRUSKAL 알고리즘

• 간선을 하나씩 선택해서 MST를 찾는다.
  >> 간선 중심으로 해결하는 알고리즘이므로 간선 리스트로 그래프를 표현한다.
  
  
• 초기에 모든 간선을 가중치 오름차순으로 정렬한다.
• 가중치가 낮은 간선부터 선택하며 트리를 증가시킨다.
  >> 사이클이 존재하면 남은 간선 중 그 다음으로 가중치가 낮은 간선을 선택한다.
  
  
• n - 1개의 간선이 선택될 때까지 반복한다.
• Union-Find 알고리즘을 활용하여 사이클을 피할 수 있다.

3. PRIM 알고리즘

• 정점에 연결된 간선들 중 하나를 선택하며 MST를 만들어 간다.
  >> 정점 중심으로 해결하는 알고리즘이므로 인접 리스트 또는 인접 행렬로 그래프를 표현한다.
  
  
• 임의의 정점을 하나 선택한다.
• 선택한 정점과 인접하는 정점 중 가중치가 가장 낮은 간선이 존재하는 정점을 선택한다.
• 모든 정점이 선택될 때까지 반복한다.
• 트리 정점들 (tree vertices)과 비트리 정점들 (non-tree vertices)의 서로소인 두 집합 정보를 유지한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class PrimTest {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int v = Integer.parseInt(br.readLine());
		int[][] adjMatrix = new int[v][v]; // 인접행렬
		boolean[] visit = new boolean[v]; // 트리 정점 여부
		int[] minEdge = new int[v]; // 비트리 정점을 기준으로 트리 정점들과 연결했을 경우 최소 간선 비용
		
		StringTokenizer st;
		
		for (int i = 0; i < v; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < v; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		Arrays.fill(minEdge, Integer.MAX_VALUE); // 최솟값 갱신
		minEdge[0] = 0; // 임의의 시작점을 위한 처리
		int res = 0; // 최소 신장 비용
		
		int c;
		for (c = 0; c < v; c++) {
			
			// step 1 : 비트리 정점 중 최소간선비용의 정점 찾기
			int min = Integer.MAX_VALUE;
			int minVertex = -1;
			
			for (int i = 0; i < v; i++) {
				if (!visit[i] && minEdge[i] < min) {
					min = minEdge[i];
					minVertex = i;
				}
			}
			
			if (minVertex == -1) break;
			res += min; // 간선 비용 누적
			visit[minVertex] = true; // 트리 정점에 포함
			
			// step 2 : 새롭게 트리 정점에 확장된 정점 기준으로 비트리 정점들과의 간선비용을 고려하여 최적 업데이트
			for (int i = 0; i < v; i++) {
				if (!visit[i] && adjMatrix[minVertex][i] != 0 
						&& adjMatrix[minVertex][i] < minEdge[i]) {
					minEdge[i] = adjMatrix[minVertex][i];					
				}
			}
		}
		
		System.out.println(c == v ? res : -1);
	}
}

 

Prim Algorithm with Priority Queue

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

public class PrimPQTest {
	
	static class Vertex implements Comparable<Vertex> {
		int no;
		int wei;
		public Vertex(int no, int wei) {
			this.no = no;
			this.wei = wei;
		}
		@Override
		public int compareTo(Vertex o) {
			return this.wei - o.wei;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int v = Integer.parseInt(br.readLine());
		int[][] adjMatrix = new int[v][v]; // 인접행렬
		boolean[] visit = new boolean[v]; // 트리 정점 여부
		int[] minEdge = new int[v]; // 비트리 정점을 기준으로 트리 정점들과 연결했을 경우 최소 간선 비용
		
		StringTokenizer st;
		
		for (int i = 0; i < v; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < v; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		
		Arrays.fill(minEdge, Integer.MAX_VALUE); // 최솟값 갱신
		minEdge[0] = 0; // 임의의 시작점을 위한 처리
		pq.offer(new Vertex(0, minEdge[0]));
		
		int res = 0; // 최소 신장 비용
		
		int c = 0;
		while (!pq.isEmpty()) {
			
			// step 1 : 비트리 정점 중 최소간선비용의 정점 찾기
			Vertex minVertex = pq.poll();
			
			if (visit[minVertex.no]) continue;
			res += minVertex.wei; // 간선 비용 누적
			visit[minVertex.no] = true; // 트리 정점에 포함
			c++;
			
			// step 2 : 새롭게 트리 정점에 확장된 정점 기준으로 비트리 정점들과의 간선비용을 고려하여 최적 업데이트
			for (int i = 0; i < v; i++) {
				if (!visit[i] && adjMatrix[minVertex.no][i] != 0 
						&& adjMatrix[minVertex.no][i] < minEdge[i]) {
					minEdge[i] = adjMatrix[minVertex.no][i];
					pq.offer(new Vertex(i, minEdge[i]));
				}
			}
		}
		
		System.out.println(c == v ? res : -1);
	}
}