[MST 개념] 최소 비용 신장 트리

최소 비용 신장 트리 [ Munimum Spanning Tree ]

 

https://en.wikipedia.org/wiki/Minimum_spanning_tree.

 

신장 트리(Spanning Tree)

 

https://ghkvud2.tistory.com/97

 

Spanning Tree : 그래프 내의 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프.

 

• Spanning Tree = 신장 트리 = 스패닝 트리
• 신장트리를 구성하는 방법은 유일하지 않다.
• N개의 정점을 가지는 그래프의 최소 간선의 수는 (N - 1)개 이고, 모든 정점이 (N - 1)개의 간선으로 연결되어 있으면 필연적으로 트리의 형태로 이루어질 수 밖에 없다.
• 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다.

 

최소 비용 신장 트리(Minimum Spanning Tree)

 

https://ghkvud2.tistory.com/97

 

MST(Minimum Spanning Tree) : Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

 

• 무방향 가중치 그래프
• 최소 비용의 Spanning Tree를 선택하는 것.
  - 가중치의 합이 최소인 Spanning Tree.
• n개의 정점을 가지는 그래프에 대해 (n-1)개의 간선을 사용.
• 사이클이 포함되어선 안된다.

 

MST 사용

• 도로망, 통신망, 유통망 등의 여러 분야에서 비용을 최소로 하는 경우.

 

MST 구현 방법

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

 

 

관련 문제

2020/12/27 - [JAVA/[JAVA - BAEKJOON] 알고리즘] - [BAEKJOON_1197 - JAVA] 최소 스패닝 트리(MST)

[BAEKJOON_1197 - JAVA] 최소 스패닝 트리(MST)

 

 

MST 구현 방법

 

1. 크루스칼(Kruskal MST) 알고리즘

 

탐욕적인 방법(greedy method)을 이용.

 

• MST(최소 비용 신장 트리)가 최소 비용의 간선으로 구성, 사이클을 포함하지 않음을 전제로,
  각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.
• 간선 선택을 기반으로 하는 알고리즘이다.
• 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.
  
  

[과정]

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
   1. 가장 낮은 가중치를 먼저 선택한다.
   2. 사이클을 형성하는 간선리아면 다음 간선을 선택한다.
3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가, (n-1)개의 간선이 선택될 때까지 반복한다.
   
   

시간 복잡도 : O(MlogM)

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;
	}
}

 

 

2. 프림(Prim MST) 알고리즘

 

시작 정점에서 출발, 신장트리 집합을 단계적으로 확장.

 

• 정점 선택을 기반으로 하는 알고리즘이다.
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.

 

[과정]

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

시간 복잡도 : O(N^2)
최소 우선순위 큐를 사용하면 : O(MlogN)

 

 

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(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);
	}
}