MST - 크루스칼과 프림

- 스패닝 트리 : 그래프 중에서 일부 간선을 선택해서 만든 트리.

- 최소 스패닝 트리 : 스패닝 트리 중 간선의 가중치 합이 최소인 트리.

 

최소 스패닝 트리는 경로 세우기 문제에서 자주 나온다.

 

- 크루스칼 - 모든 간선 중 가장 작은것을 뽑는다. 단, 간선이 사이클을 만드는지 아닌지는 union-find 를 기준으로 수행한다.

- 프림 - 임의의 정점을 선택한다. 임의의 정점을 기준으로, 선택한 정점과 선택하지 않은 정점들을 연결하는 간선중에 최소값을 고른다. 이를 모든 정점을 돌 때 까지 2번 단계를 반복한다.

프림

프림부터 수도코드를 알아보겠다.

1. 임의의 정점을 선택한다. 선택표시를 한다.

2. 정점에 연결되어있는 임의의 간선을 PQ에 넣는다. 

3. PQ에서 가장 적은 코스트의 간선을 뺀다. 만약 간선이 이미 선택되어있다면 무시한다.

4. 그리고 그 간선과 연결되어있는 정점을 선택한다. 선택표시를 한다.

5. 그 정점과 연결되어있는 모든 간선들 중 선택표시가 안된 간선들만 모두 PQ에 넣어준다.

6. 그리고 3번으로 돌아간다.

7. 모든 정점을 선택하거나 PQ가 빌때까지 반복한다. 

 

 

위 수도코드를 기반으로 네트워크 연결 문제를 풀어보겠다.

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

public class Main {
	
	static class Edge implements Comparable<Edge>{
		int to;
		int cost;
		
		public Edge(int to, int cost) {
			super();
			this.to = to;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return this.cost - o.cost; 
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		List<Edge>[] list = new ArrayList[n+1];
		boolean visited[] = new boolean[n+1];
		
		for (int i = 1 ; i <= n ;i++) {
			list[i] = new ArrayList();
		}
	
		for (int i = 0 ; i < m ; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			int cost = sc.nextInt();
			list[from].add(new Edge(to, cost));
			list[to].add(new Edge(from, cost));
		}
		
		visited[1] = true;
		PriorityQueue<Edge> pq = new PriorityQueue();
		for (int i = 0 ; i < list[1].size(); i++) {
			pq.add(list[1].get(i));
		}
		
		int result = 0;
		while(!pq.isEmpty() ) {
			
			Edge e = pq.poll();
			
			if (visited[e.to] == true) {
				continue;
			}
			
			visited[e.to] = true;
			result += e.cost;
			
			for (int i = 0 ; i < list[e.to].size(); i++ ) {
				if (!visited[list[e.to].get(i).to])
					pq.add(list[e.to].get(i));
			} 
			
		}
		
		System.out.println(result);
		
		

	}

}

www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

위 수도코드를 그대로 구현하려고 한 코드이다.

 

1. 임의의 정점을 택하고

2. 그 정점과 연결되어있는 모든 간선을 pq에 추가한다.

3. 그리고 pq에서 제일 작은 cost를 뽑아주되, 이미 선택된 간선 방향으로 연결되어있는 경우는 제외한다. (사이클 발생 방지) (선택된 간선 -> 선택 안됨 방향)을 유지해야한다.

4. 새롭게 선택된 정점을 기준으로 cost를 추가해준다.

5. 3번을 pq가 빌 때 까지 반복한다 (혹은 모든 정점을 선택할 때 까지 반복하는 방법도 있다)

 

 

MST문제를 풀 때, 한가지 더 알아두었으면 좋겠는것은 MST 알고리즘을 통해 모든 정점이 연결되어있는지 체크하는지 알아보는 방법이다.

 

만약에 모두 연결되어있지 않은 그래프가 주어졌다고 하면, 위 알고리즘으로 에러없이 값이 도출되긴 하지만, MST가 애초에 형성되지 않는 조건이기 때문에 답이 틀리다.

 

다행히 프림같은경우는 visited라는 정보가 있기 때문에 쉽게 visited에 모든 영역이 true인지 false인지 체크함으로써 제대로 Spanning Tree를 만들 수 있는 그래프인지 체크 가능하다. 혹은 visitedCnt라는 변수를 만들어서 check될때마다 정점의 개수를 체크하는 방법도 있다.

 

크루스칼

크루스칼은 프림처럼 정점을 기준으로 탐색하지 않는다.

 

대신에 모든 간선을 PQ에 넣고 시작한다.

 

1. 모든 간선에서 최소 비용인 간선을 빼고, 그 간선이 사이클이 발생시키는지 체크한다.

2. 이때 사용하는것이 union-find이다. 두 간선을 union시켜버리고, 다음에 union 시켰을 때 false가 반환되면, 그 그룹 내에서 간선을 또 선택한다는 의미이므로 이건 사이클이 발생된다는 뜻이다. 

3. 사이클을 발생하지 않으면 그 간선을 선택한다.

4. 1번부터 다시 시작.

 

프림에 비하면 union-find 소스코드의 추가로 전체 길이는 길어지고, union-find의 속도도 완전히 보장할 순 없다고 생각한다. 그럼에도 불구하고, 그래프를 생성도 신경쓸 필요 없고, union-find의 로직에 사이클 여부 체크 로직을 맡기면 되는지라..  개인적으로는 더 구현이 쉽게 느껴젔다..

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

public class Main {
	
	static class Edge implements Comparable<Edge> {

		int from;
		int to;
		int cost;
		
		
		public Edge(int from, int to, int cost) {
			super();
			this.from = from;
			this.to = to;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return this.cost - o.cost;
		}
		
	}
	static int parents[];
	
	public static void make(int n) {
		parents = new int[n+1];
		for (int i = 1 ; i <= n ; i++) {
			parents[i] = i;
		}
	}

	public static int find(int a) {
		if (parents[a] == a) return a;
		return parents[a] = find(parents[a]);
	}
	
	public static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if (aRoot == bRoot) return false;
		parents[aRoot] = bRoot;
		return true;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		PriorityQueue<Edge> pq = new PriorityQueue();
		
	
		for (int i = 0 ; i < m ; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			int cost = sc.nextInt();
			pq.add(new Edge(from, to, cost));
			
		}
		
		int V = n;
		int targetE = V - 1;
		int result = 0;
		make(n);
		
		while(!pq.isEmpty()) {
			Edge p = pq.poll();
			if (union(p.from, p.to)) {
				result += p.cost;
				targetE--;
			}
		}
		
		System.out.println(result);
		
		
	}

}

 

프림과 달라진 점이라면, 프림은 일반적인 그래프처럼 입력을 받았다면,  크루스칼은 Edge 기준으로만 입력을 받는다. 나머지는 union-find에 맡긴다.

 

추가적으로, 정상적으로 spanning tree를 만들었는지 체크하기 위해서는, 프림과 마찬가지로 targetE = V - 1라는 변수를 넣어준다.

union될때마다 targetE의 값을 줄여주면, 연산이 모두 종료되었을 때 targetE의 값이 0이 되어야한다. 모든 스패닝 트리 간선을 택했다는 의미이다. 만약 0 보다 큰 값이 나오면 스패닝 트리를 만들었음에 실패했는것을 의미한다.