[알고리즘 정리] Kruskal & Prim(크루스칼과 프림)

 

 

다룰 내용

• 신장 트리란 무엇인가?
• 최소 비용 신장 트리란 무엇인가?
• 최소 비용 신장 트리를 구성하는 방법
• Kruskal 알고리즘
• Prim 알고리즘

 

---

신장 트리란 무엇인가?

그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말합니다.

사이클이 안 생기는 조건 안에서 간선의 개수를 정점 - 1개로 골라 만드는 것으로, 정점 - 1의 수가 간선의 수가 되는 트리입니다.

 

 

최소 비용 신장 트리란 무엇인가?

신장 트리 중에서 간선들의 합이 최소인 트리입니다. 또한 무향 가중 그래프에서 만들어질 수 있고 사이클이 발생되지 않으며 비용의 합이 최소인 트리입니다.

 

 

최소 비용 신장 트리의 특징

1. 무방향 가중치 그래프입니다.
2. 가중치의 합이 최소입니다.
3. 정점 n개에서 n - 1개의 간선을 가지는 트리입니다.
4. 사이클이 포함되서는 안됩니다.

 

최소 비용 신장 트리의 사용

도로망, 통신망, 유통망 등 여러 분야에서 비용을 최소로 해야하는 경우에 유용하게 사용됩니다.

 

 

최소 비용 신장 트리를 구성하는 방법

• Kruskal(크루스칼 알고리즘)
• Prim(프림 알고리즘)

 

---

 

Kruskal 알고리즘

간선 선택 기반의 알고리즘으로, 탐욕적인 방법을 이용, 간선을 하나씩 선택해서 MST를 찾는 알고리즘입니다.

 

 

크루스칼 알고리즘 동작 과정

1. 그래프의 간선들을 가중치의 오름차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택합니다.
   1. 이때 가중치가 가장 낮은 간선을 선택합니다.
   2. 사이클이 형성되는 간선이라면 다음 간선을 선택합니다.
3. 선택한 간선을 MST 집합에 추가 (n - 1)개의 간선이 선택될 때까지 반복 수행합니다.

 

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

public class Kruskal {
	
    // 정점의 부모 노드를 저장할 배열
	public static int parents[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input1[] = br.readLine().split(" ");
		int V = Integer.parseInt(input1[0]); // 정점의 개수
		int E = Integer.parseInt(input1[1]); // 간선의 개수
		// 정점의 정보 2개 + 이들의 가중치 순으로 입력이 들어옴.
		int edges[][] = new int[E][3]; 
		// 1번부터 인덱스를 사용하기 위해서 V + 1
		parents = new int[V + 1];
		
		// 간선의 정보와 가중치 입력 받기
		for(int i = 0; i < E; i++) {
			String input2[] = br.readLine().split(" ");
			edges[i][0] = Integer.parseInt(input2[0]); // 정점1
			edges[i][1] = Integer.parseInt(input2[1]); // 정점2
			edges[i][2] = Integer.parseInt(input2[2]); // 가중치
		}
		
		// 가중치 오름차순으로 정렬
		Arrays.sort(edges, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// 2번째 인덱스에 가중치가 있으므로 가중치를 기준으로 오름차순 정렬
				return Integer.compare(o1[2], o2[2]);
			}
		});
		
		// parents를 -1로 초기화
		Arrays.fill(parents, -1);
		
		// 출력될 가중치의 합
		int result = 0;
		int cnt = 0;
		// 간선의 수만큼 loop 수행
		for(int i = 0; i < edges.length; i++) {
			// 정점과 정점이 연결될 수 있는지 확인
			if(union(edges[i][0], edges[i][1])) {
				result += edges[i][2]; // 가중치 덧셈
				cnt++;
			}
			// cnt가 정점 - 1개가 된다는 것은 모든 정점을 다 연결했다는 의미이므로 종료
			if(cnt == V - 1) break;
		}
		System.out.println(result);
	}
	
	public static int find(int x) {
		if(parents[x] < 0) return x;
		return parents[x] = find(parents[x]);
	}
	
	public static boolean union(int x, int y) {
		int xRoot = find(x); // x의 root를 찾아서 결과 받음
		int yRoot = find(y); // y의 root를 찾아서 결과 받음
		
		// 두 개의 정점의 root가 같지 않다면 같은 집합에 속하지 않은 것
		if(xRoot != yRoot) { 
			parents[yRoot] = xRoot; // 따라서 y의 root를 x의 root로 변경
			return true; // 연결되었으므로 true return
		}
		// 연결을 하지 못한 경우이므로 false return
		return false;
	}
}

 

 

---

Prim 알고리즘

정점 선택 기반의 알고리즘으로, 하나의 정점에서 연결된 간선들 중에 최소 간선 비용을 가진 정점을 하나씩 선택하면서 MST를 찾는 알고리즘

 

 

프림 알고리즘 동작 과정

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

프림의 경우 선택된 정점들과 연결된, 선택되지 않은 정점들의 간선에서 최소 간선 비용을 가진 정점을 선택하는 방식으로 진행됩니다.

 

 

Prim + 인접 행렬

 

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

public class Prim {
	/*
	 * 간선이 많은 경우 Prim이 유리하고 
	 * 인접행렬을 사용하는 것이 유용함
	 * 프림 + 인접행렬 궁합 좋음
	 */

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input1[] = br.readLine().split(" ");
		int V = Integer.parseInt(input1[0]); // 정점의 개수
		int E = Integer.parseInt(input1[1]); // 간선의 개수
		// 정점의 정보 2개 + 이들의 가중치 순으로 입력이 들어옴.
		int adj[][] = new int[V][V]; 
		int result = 0;
		
		// 간선의 정보와 가중치 입력 받기
		for(int i = 0; i < E; i++) {
			String input2[] = br.readLine().split(" ");
			int a = Integer.parseInt(input2[0]) - 1;
			int b = Integer.parseInt(input2[1]) - 1;
			int c = Integer.parseInt(input2[2]);
			// 인접 행렬 구성
			adj[a][b] = c;
			adj[b][a] = c;
		}
		
		// 선택되었는지 아닌지 판단하기 위한 boolean 배열
		boolean visited[] = new boolean[V];
		// 현재 선택된 정점들로부터 도달할 수 있는 최소 거리 저장 배열
		int distance[] = new int[V];
		
		// 모두 최대 값으로 key를 갱신
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		distance[0] = 0; // 처음 선택한 정점은 거리 0
		int cnt = 0;
		
		while(true) {
			int min = Integer.MAX_VALUE;
			int idx = 0;
			for(int i = 0; i < V; i++) {
				// 선택되지 않았고 거리를 저장한 key보다 작은 경우 갱신
				if(!visited[i] && distance[i] < min) {
					idx = i;
					min = distance[i];
				}
			}
			
			// 선택된 정점에 포함시킴
			visited[idx] = true;
            // 결과값에 가중치 덧셈
			result += min;
			cnt++;
			
            // cnt가 V랑 같아지면 모든 정점을 처리한 것이므로 종료
			if(cnt == V) break;
			
            // 새로 추가한 정점으로부터 연결되어 있는 다른 정점의 간선 정보 업데이트
			for(int i = 0; i < V; i++) {
				if(!visited[i] && adj[idx][i] > 0 && distance[i] > adj[idx][i]) {
					distance[i] = adj[idx][i];
				}
			}
		}
		
		System.out.println(result);
	}
}

 

 

Prim + PQ(Priority Queue)

 

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;

public class Prim_pq {

	public static class Vertex implements Comparable<Vertex>{
		int v, dist;

		Vertex(int v, int dist){
			this.v = v;
			this.dist = dist;
		}

		@Override
		public int compareTo(Vertex o) {
			return Integer.compare(this.dist, o.dist);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input1[] = br.readLine().split(" ");
		int V = Integer.parseInt(input1[0]);
		int E = Integer.parseInt(input1[1]);

		int result = 0;

		List<Vertex> list[] = new ArrayList[V];

		for(int i = 0; i < V; i++) list[i] = new ArrayList<Vertex>();

		// 간선의 정보와 가중치 입력 받기
		for(int i = 0; i < E; i++) {
			String input2[] = br.readLine().split(" ");
			int a = Integer.parseInt(input2[0]) - 1;
			int b = Integer.parseInt(input2[1]) - 1;
			int c = Integer.parseInt(input2[2]);
			// 인접 리스트 구성
			list[a].add(new Vertex(b, c));  
			list[b].add(new Vertex(a, c));  
		}

		// 선택되었는지 아닌지 판단하기 위한 boolean 배열
		boolean visited[] = new boolean[V];
		// 현재 선택된 정점들로부터 도달할 수 있는 최소 거리 저장 배열
		int distance[] = new int[V];

		// 모두 최대 값으로 key를 갱신
		Arrays.fill(distance, Integer.MAX_VALUE);

		distance[0] = 0; // 처음 선택한 정점은 거리 0
		int cnt = 0;

		PriorityQueue<Vertex> q = new PriorityQueue<Vertex>();
		q.offer(new Vertex(0, distance[0]));

		while(true) {
			Vertex cur = q.poll();

			if(visited[cur.v]) continue; 
			visited[cur.v] = true;
			result += cur.dist;
			cnt++;

			if(cnt == V) break;

			for(Vertex v : list[cur.v]) {
				if(!visited[v.v] && distance[v.v] > v.dist) {
					distance[v.v] = v.dist;
					q.offer(new Vertex(v.v, distance[v.v]));
				}
			}
		}
		System.out.println(result);
	}
}