최소 신장 트리(MST)

최소 신장 트리(MST)

• 그래프에서 최소 비용 문제
  1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
  2. 두 정점 사이의 최소 비용의 경로 찾기
     
     
• 신장 트리
  • n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
    
    
• 최소 신장 트리
  • 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

KRUSKAL 알고리즘

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

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

  

  
  

• 구현

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

public class MST1_KruskalTest {
	
	static class Edge implements Comparable<Edge>{
		int start;
		int end;
		int 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 this.weight - o.weight;
		}
	}
	
	static int N;
	static int[] parents;
	static Edge[] edgeList;
	
	// 단위 집합 생성
	public static void makeSet() {
		parents = new int[N];
		// 자신의 부모노드를 자신의 값으로 세팅
		for(int i=0; i<N; i++) {
			parents[i] = i;
		}
		
	}
	
	// a의 집합 찾기 : a의 대표자 찾기
	public static int findSet(int a) {
		if(a==parents[a]) {
			return a;
		}
		
		return parents[a] = findSet(parents[a]);
	}
	
	// a,b 두 집합 합치기
	public static boolean union(int a, int b) {
		
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if(aRoot == bRoot)
			return false;
		
		parents[bRoot] = aRoot;
		return true;
	}
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
	
		edgeList = new Edge[E];
		
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			edgeList[i] = new Edge(from, to, weight);
		}
		
		Arrays.sort(edgeList);
		
		makeSet();
		
		// 결과 비용 변수
		int result = 0;
		int cnt = 0;
		
		for(Edge edge : edgeList) {
			if(union(edge.start, edge.end)) {
				result += edge.weight;
				if(++cnt == N-1) {
					break;
				}
			}
		}
		
		System.out.println(result);
		
	}

}

PRIM 알고리즘

• 하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 MST를 만들어 가는 방식
  1. 임의 정점을 하나 선택해서 시작
  2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
  3. 모든 정점이 선택될 때까지 1,2 과정을 반복
     
     
• 서로소인 2개의 집합 정보를 유지
  • 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
  • 비트리 정점들(non-tree_vertices) - 선택 되지 않은 정점들
    
    

• 구현

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

public class MST2_PrimTest {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int[][] adjMatrix = new int[N][N];
		int [] minEdge = new int[N];	// 타 정점에서 자신으로의 간선 비용중 최소 비용을 저장
		boolean[] isVisited = new boolean[N];
		
		for(int r=0;r<N;r++) {
			st = new StringTokenizer(br.readLine());
			for(int c=0;c<N;c++) {
				adjMatrix[r][c] = Integer.parseInt(st.nextToken());
			}
			minEdge[r] = Integer.MAX_VALUE;	// 충분이 큰 값으로 최소값 초기화
		}
		
		int result = 0;	// MST 비용
		minEdge[0] = 0;	// 임의로 0번부터 시작
		
		// N개의 정점을 모두 연결
		for(int c=0;c<N;c++) {
			// 신장트리에 연결되지 않은 정점 중 가장 유리한 비용의 정점을 선택
			int min = Integer.MAX_VALUE;
			int minVertex = -1;
			
			for(int i=0; i<N; i++) {
				if(!isVisited[i] && min > minEdge[i]) {
					min = minEdge[i];
					minVertex = i;
				}
			}
			
			// 선택된 정점을 신장트리에 포함시킴
			isVisited[minVertex] = true;
			result += min;
			
			// 선택된 정점 기준으로 신장트리에 포함되지 않은 다른 정점으로의 간선 비용을 따져보고 최소값 갱신
			for(int i=0;i<N;i++) {
				if(!isVisited[i] && adjMatrix[minVertex][i] != 0 && minEdge[i] > adjMatrix[minVertex][i]) {
					minEdge[i] = adjMatrix[minVertex][i];
				}
			}
		}
		
		System.out.println(result);
		
	}

}

정리

• 인접 행렬, 인접 리스트 : 정점 중심으로 해결(PRIM 알고리즘)
• 간선 리스트 : 간선 중심으로 해결(KRUSKAL 알고리즘)
• 간선이 적을 때 : KRUSKAL
• 간선이 많을 때 : PRIM