최소 신장 트리(MST)에 대해

1. 신장 트리(Spanning Tree)

• 그래프의 모든 정점을 최소한 적은 간선만 사용해 연결하는 트리를 말한다
• 정점이 N개라면 N-1개의 간선만 사용해 모든 정점을 연결한 형태를 이루게 된다
• 신장 트리는 그 구조상 사이클을 포함하지 않는다
• 만드는 방법 : 한 정점을 기준으로 DFS/BFS를 실행할 때, 탐색한 간선들이 곧 하나의 신장 트리가 된다

 

 

2. 최소 신장 트리(Minimum Spanning Tree, MST)

• 최소 신장 트리란, 가중치 있는 그래프에서, 신장트리를 이루는 간선의 가중치 총합이 최소가 되는 신장트리를 말한다
• 모든 정점들을 최소 비용으로 연결하는 것

 

 

3. 최소 신장 트리 구현

• 크루스칼(KRUSKAL) 알고리즘 (간선 기반)

  

  https://visualgo.net/en/mst

   
  • Greedy하게 간선을 선택하여 최소 신장 트리를 완성한다
  • 간선의 가중치가 작을수록 선택에 우선순위를 두되,
  • 해당 간선을 선택함으로 인해 트리에 사이클이 발생한다면, 선택하지 않고 넘어간다
  • n-1개의 간선을 선택하면, MST가 완성된 것이다
  • 사이클의 발생 여부 탐색 : 간선의 양쪽 정점 사이에 이미 경로가 존재한다면, 사이클이 발생하게 된다
  • 분리집합을 이용해 간선 선택시 양 정점의 집합을 합쳐, 사이클 발생을 막을 수 있다

 

• 프림(PRIM) 알고리즘 (정점 기반)

  

  https://visualgo.net/en/mst

  • 한 정점에서 시작해 최적의 간선만을 선택해 트리를 확장해 나간다
  • 현재 트리에 속한 정점들의 인접 정점 중, 가장 적은 비용으로 진행할 수 있는 정점을 선택, 트리에 포함시킨다
  • n-1개의 정점을 선택하면, MST가 완성된 것이다
  • 다익스트라와 형태가 거의 비슷하지만, 다익스트라는 특정 노드를 기준으로 누적된 거리를 기준으로 한다

 

 

4. JAVA 기초 코드(문제링크)

• Kruskal 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());

		//간선 리스트..대신 크기가 주어지니 간선배열 사용
		edge[] e = new edge[m];
		for (int i = 0; i < m; i++) {
			e[i]=new edge();
			st = new StringTokenizer(br.readLine(), " ");
			
			e[i].n1=pint(st.nextToken());
			e[i].n2=pint(st.nextToken());
			e[i].cost=pint(st.nextToken());
		}
		//정렬, 작은 간선부터 확인
		Arrays.sort(e);
		//분리집합 초기화
		init(n);
		
		int cnt=0, i=0;//현재 선택한 edge의 갯수, 현재 edge index
		int totalCost=0;//전체cost
		while(true) {
			//union이 정상적으로 수행 됬다면 ( = cycle을 이루지 않는 간선이 tree에 포함되었다면)
			if(union(e[i].n1, e[i].n2)) {
				//cnt, cost 반영
				cnt++;
				totalCost+=e[i].cost;
			}
			if(cnt==n-1)break;//n-1개의 간선을 선택했다면 MST의 완성
			i++;
		}
		//최소 cost의 2개의 마을로 분할하는 법 = MST에서 가장 cost가 큰 edge 하나 자르기
		System.out.println(totalCost-e[i].cost);
	}

	//분리집합
	static int[]parents;
	static void init(int n) {
		parents=new int[n+1];
		for (int i = 0; i <= n; i++) {
			parents[i]=i;
		}
	}
	static int find(int n) {
		if(parents[n]==n)return n;
		return parents[n]=find(parents[n]);
	}
	static boolean union(int n1, int n2) {
		int p1=find(n1);
		int p2=find(n2);
		
		if(p1==p2)return false;
		parents[p1]=p2;
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	//간선 객체
	static class edge implements Comparable<edge>{
		int n1;
		int n2;
		int cost;
		@Override
		public int compareTo(edge e) {
			return this.cost-e.cost;
		}		
	}
}

 

• Prim 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());

		ArrayList<ArrayList<int[]>>graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<>());
		}
		
		//그래프 입력
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken());
			int y = pint(st.nextToken());
			int cost = pint(st.nextToken());

			graph.get(x).add(new int[] {y,cost});
			graph.get(y).add(new int[] {x,cost});
		}
		
		int totalCost=0, cnt=0, max=-1;
		//전처리
		boolean[] isV = new boolean[n+1];
		PriorityQueue<int[]>pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[1]-o2[1];
			}
		});
		for (int i = 1; i <= n; i++) {
			pq.offer(new int[] {i,Integer.MAX_VALUE});
		}
		//임의의 시작 노드 설정
		pq.offer(new int[] {1,0});
		
		while(cnt!=n) {//n개의 정점을 선택하면 MST의 완성
			int[] curNode = pq.poll();

			if(isV[curNode[0]])continue;//이미 방문한 node면 무시한다
			
			isV[curNode[0]]=true;
			totalCost+=curNode[1];
			if(max<curNode[1])max=curNode[1];//MST의 가장 큰 edge 저장
			cnt++;
			
			for (int i = 0; i < graph.get(curNode[0]).size(); i++) {
				int[] next = graph.get(curNode[0]).get(i);
                if(!isV[next[0]]) {
					pq.offer(next);
				}
			}
			
		}
		System.out.println(totalCost-max);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}