최소 신장 트리(MST) - Kruskal , Prim

최소 신장 트리(MST) 

그래프의 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 찾기!

어디에서 시작하는 지 상관없이 모든 정점이 다 이어질 수 있도록 팔을 뻗는다고 생각하면 된다.

• 간선이 적을 때 => KRUSKAL(간선 중심)
• 간선이 많을 때 => PRIM(정점 중심)

---

Kruskal 알고리즘

간선을 하나씩 선택해서 MST를 찾는 알고리즘

1. 모든 간선을 가중치에 따라 오름차순으로 정렬 (최초 한번)
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 *** 사이클을 형성하는 간선은 선택 x!** ⇒ union-find 알고리즘을 이용한다.
3. n-1 개의 간선이 선택될 때까지 반복해서 선택

• 사이클을 형성하는 방법 ⇒ union-find 추가하고자하는 간선의 양끝 정점이 같이 집합에 속해있는지 검사
  ⇒ 즉, 코드로 구현할 때는 간선을 선택할 때마다 union-find에서 부모를 연결해준다.
• 시간복잡도 : O(E log₂ E)

 

---

PRIM 알고리즘

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

1. 임의의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중에 최소 비용의 간선이 존재하는 정점 선택

• 시간복잡도: O(V^2)

---

PRIM(프림) 알고리즘 JAVA 코드

• 인접 행렬로 풀어도 되고 인접 리스트로 풀어도 된다.
• 이 글을 보고 있는 사람은 우선순위큐는 알고 있다고 생각하고 코드를 작성했다
• 아래는 최소 스패닝 트리 기본 문제인 백준 1197번의 풀이다.
• 내가 생각하기에는 PRIM 알고리즘에 Priority Queue를 사용하는 게 MST를 풀 때 가장 효율적인 것 같다.

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

// [D4] 최소 스패닝 트리, 모든 정점을 다 연결하자
// 일단 prim 으로 풀어본다.
public class baekjoon_1197 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int V = Integer.parseInt(st.nextToken()); // 정점의 개수
			int E = Integer.parseInt(st.nextToken()); // 간선의 개수
			
			boolean[] visited = new boolean[V+1];
			
			List<Data>[] adjList= new LinkedList[V+1];
			for(int i = 1; i<=V; i++) {
				adjList[i] = new LinkedList<Data>();
			}
			
			for(int e = 0; e<E; e++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int weight = Integer.parseInt(st.nextToken());
				
				adjList[to].add(new Data(from, weight));
				adjList[from].add(new Data(to, weight));
			}
			
			PriorityQueue<Data> queue = new PriorityQueue<>();
			long result = 0;
			int checkedV = 0;
			visited[1] = true;
			checkedV ++;
			
			for(int j = 0; j<adjList[1].size(); j++) {
				Data data = adjList[1].get(j);
				queue.offer(data);
			}
			
			// 여기부터 시작
			while(!queue.isEmpty()) {
				if(checkedV == V) {
					break;
				}
				Data data = queue.poll();
				
				// 방문한 적 있는 곳이면 continue
				if(visited[data.idx]) {
					continue;
				}
				
				// 방문한 적 없는 곳이면 체크
				visited[data.idx] = true;
				checkedV ++;
				
				result += data.weight;
				
				for(int j=0; j<adjList[data.idx].size(); j++) {
					Data d = adjList[data.idx].get(j);
					queue.offer(d);
				}
			}
			
			System.out.printf("%d%n",result);
	}
	static class Data implements Comparable<Data>{
		int idx;
		int weight;
		
		public Data(int idx, int weight) {
			this.idx = idx;
			this.weight = weight;
		}

		@Override
		public int compareTo(Data o) {
			if(this.weight==o.weight) {
				return Long.compare(this.idx, o.idx);
			}
			return Long.compare(this.weight, o.weight);
		}
	}
}

 

사진 출처: https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html