[알고리즘/JAVA] 최소 비용 신장 트리(MST) - 크루스칼, 프림

최소 비용 신장 트리란?

• 신장 트리(스패닝 트리) : 그래프 내의 모든 정점을 포함하는 트리
•  최소 비용 신장트리 : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리

특징 

• 무방향 가중치 그래프
• 그래프의 가중치의 합이 최소
• N개의 정점을 가지는 그래프에 대해 반드시 (N-1) 개의 간선을 사용해야 한다.
• 사이클을 포함x

대표적인 방법

• Kruskal(크루스칼)
• Prim(프림)

---

 

크루스칼 알고리즘

가장 작은 가중치를 가진 간선을 차례대로 하나씩 선택해서 MST를 찾는 알고리즘

1. 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 연결  - 사이클이 존재한다면 선택x
3. V-1개의 간선이 선택될 때 까지 (2)반복

사이클이 존재하는지는 어떻게 찾을까? 유니온 파인드 이용 https://dong-kim.tistory.com/28

[알고리즘/Java] 그래프 - 유니온 파인드(Union-Find)

 

예시문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

크루스칼 구현 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[] p;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		p = new int[V+1];
		int[][] arr = new int[E][3];
		for (int i = 0; i < E; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
			arr[i][2] = sc.nextInt();
		}
		Arrays.sort(arr, (o1, o2) -> o1[2] - o2[2]);
		for (int i = 1; i <= V; i++) {
			p[i] = i;
		}
		int ans = 0;
		int pick = 0;
		int i = 0;
		while (pick!=V-1) {
			int nx = findSet(arr[i][0]);
			int ny = findSet(arr[i][1]);
			if(nx!=ny) {
				union(nx, ny);
				ans += arr[i][2];
				pick++;
			}
			i++;
		}
		System.out.println(ans);
	}
	private static int findSet(int a) {
        if(p[a] != a) p[a] = findSet(p[a]);
        return p[a];
    }
	
	private static void union(int nx, int ny) {
		if(nx > ny) p[ny] = nx;
		else p[nx] = ny;
	}
}

 

시간복잡도

유니온파인드 과정이 상수시간이지만, 모든 간선을 정렬하는 과정에서 O(ElogE)의 시간이 소요되기 때문에 크루스칼 알고리즘의 시간복잡도는 O(ElogE)이다.

 

---

프림 알고리즘

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

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

 

예시문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

프림 구현 코드

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class 최소_스패닝_트리_프림 {
	static class node implements Comparable<node>{
		int v, weight;
		public node(int v, int weight) {
			this.v = v;
			this.weight = weight;
		}
		@Override
		public int compareTo(node o) {
			return weight - o.weight;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt(), E = sc.nextInt();
		ArrayList<node>[] arr = new ArrayList[V+1];
		for (int i = 1; i <= V; i++) {
			arr[i] = new ArrayList<>();
		}
		for (int i = 0; i < E; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int w = sc.nextInt();
			arr[x].add(new node(y, w));
			arr[y].add(new node(x, w));
		}
		boolean[] visited = new boolean[V+1];
		PriorityQueue<node> queue = new PriorityQueue<>();
		int ans = 0, pick = 0;
		// 시작점 1으로 하자
		visited[1] = true;
		for (node node : arr[1]) {
			queue.add(node);
		}
		while (pick != V-1) {
			node n = queue.poll();
			if(visited[n.v]) continue;
			visited[n.v] = true;
			ans += n.weight;
			pick++;
			for (int i = 0; i < arr[n.v].size(); i++) {
				queue.add(arr[n.v].get(i));
			}
		}
		System.out.println(ans);
	}
}

 

시간복잡도

인접 리스트를 사용한 경우 : 정점의 개수를 V, 간선의 개수를 E라고 할 떄, 우선순위 큐를 사용하여 최소 가중치 간선을 선택하는 경우 모든 정점을 선택하는 과정에서 O(VlogV)의 시간이 소요된다. 또한 각 노드의 인접 간선을 찾아 우선순위 큐에 넣는 과정이 O(ElogV)의 시간이 소요된다. 따라서 시간 복잡도는 O(VlogV + ElogV)로 O(ElogV)이다.(일반적으로 E>V)

---

정리

	크루스칼	프림
시간복잡도	O(ElogE)	O(ElogV)