최소 신장 트리 (MST)

그래프에서 최소 비용 문제

1. 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리
2. 두 정점 사이의 최소 비용의 경로 찾기

신장 트리

• n개의 정점으로 이루어진 무향 그래프에서 n개의 정점와 n-1개의 간선으로 이루어진 트리

최소 신장 트리 (Minimum Spanning Tree)

• 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리

1. KRUSKAL Algorithm

1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
3. → 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
4. n-1 개의 간선이 선택될 때까지 2번 반복

MST_KRUSKAL(G, w)

	for vertex v in G.V   // G.V : 그래프의 정점 집합
		Make_Set(v)         // G.E : 그래프의 간선 집합

	for 가중치가 가장 낮은 간선 (u, v) 선택
		if Find_Set(u) != Find_Set(v)
			Union(u, v)  

 

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

public class MSTKruskal {

		static class Edge implements Compareable(Edge) {
				int start, end, weight;

				public Edge(int start, int end, int weight){
							this.start = start;
							this.end = end;
							this.weight = weight;
				}

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

		static int [] parents;

		static void make(){
				parents = new int [V];
				for (int i = 0 ; i < V ; i++) {
						parents[i] = i;
				}
		}

		static void find(int a) {
				if (parents[a] = a) return a;
				return parents[a] = find(parents[a]);
		}

		static boolean union(int a, int b) {
				int aRoot = find(a);
				int bRoot = find(b);

				if (aRoot == bRoot) return false;

				parents[bRoot] = aRoot;
				return true;
		}

		static Edge [] edgelist;
		static int V, E;

		public static void main(String [] args) throws IOException {
				BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
				StringTokenizer st = new StringTokenizer(br.readline);

				V = Integer.parseInt(st.nextToken());
				E = Integer.parseInt(st.nextToken());

				edgelist = new Edge[E];

				for (int i = 0 ; i < E ; i++) {
						st = new StringTokenizer(br.readline);
						int start = Integer.parseInt(st.nextToken());
						int end = Integer.parseInt(st.nextToken());
						int weight = Integer.parseInt(st.nextToken());
						edgelist[i] = new Edge(start, end, weight);
				}

				make();

				int result = 0, cnt = 0;

				for (Edge edge : edgelist) {
						if (union(edge.start, edge.end) {
								result += edge.weight;
								if (++cnt == V-1) break;
						}
				}

				System.out.println(result));
		}
}

2. PRIM Algorithm

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

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

서로소인 2개의 집합 정보를 유지

• 트리 정점들 - MST를 만들기 위해 선택된 정점들
• 비트리 정점들 - 선택 되지 않은 정점들

MST_PRIM(G, r)                // G: 그래프, r:시작 정점
		// result : 신장트리 최소비용, cnt: 처리한 정점수
		// visited[] : 최소신장트리 구성에 포함된 정점 여부
		result = 0 , cnt = 0      
		FOR u in G.V
				minEdge[u] = INF      // minEdge[] : 각 정점기준으로 다른 정점과의 간선 중 최소비용
		minEdge[r] = 0            // 시작 정점 r의 최소비용 0 처리
		while true                // 빈 Q 가 아닐동안 반복
				u = Extract_MIN()     // 방문하지 않은 최소비용 정점 찾기
				visited[u] = true     // 방문 처리
				result = result + minEdge[u]
				if(++cnt == N) break; // 모든 정점이 다 연결되었으면 최소신장트리 완성
				for v in G.Adj[u]     // u의 인접 정점들
						if visited[v] == false and w(u, v) < minEdge[v] // u에서 v로의 비용이 v의 최소비용보다 작다면 갱신
								minEdge[V] = w(u, v)
		return result
end MST_PRIM

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

public class MSTPrim {

		const int INF = 987654321;

		public static void main(String [] args) throws IOException {
				BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				int N = Integer.nextInt(br.readline));
				int [][] adjMatrix = new int[N][N];
				boolean [] visited = new boolean[N];
				int [] minEdge = new int[N];

				StringTokenizer st = null;
				for (int i = 0 ; i < N ; i++) {
						st = new StringTokenizer(br.readline());
						for (int j = 0 ; j < N ; j++) {
								adjMatrix[i][j] = Integer.parseInt(st.nextToken());
						}
						minEdge[i] = INF;
				}

				int result = 0;  // 최소신장 트리 비용
				minEdge[0] = 0;  // 임의의 시작점 0의 간선비용을 0으로 세팅

				for (int i = 0 ; i < N ; i++) {
						int min = INF;
						int minVertex = -1
						for (int j = 0 ; j < N ; j++) {
								if (!visited && min > minEdge[j]) {
										min = minEdge[j];
										minVertex = j;
								}
						}
	
						visited[minVertex] = true;
						result += min;

						for (int j = 0 ; j < N ; j++) {
								if (!visited && adjMatrix[minVertex][j] != 0) {
										minEdge[j] = Math.min(minEdge[j], adjMatrix[minVertex][j]);
								}
						}
				}

				System.out.println(result);
		}
}