[야매 알고리즘] Kruskal 알고리즘 (MST 찾기), 백준 1197 최소 스패닝 트리

야매 알고리즘?

알고리즘의 정확한 정의나 의미를 다루지 않고 핵심적인 작동 원리와 코드 예제를 정리하기 위한 시리즈입니다.

전부 짚고 넘어가면 좋겠지만 그럴 지식도 없고, 공부하는 것보다 정리하는데 더 많은 에너지와 시간을 소모할 것 같아서, 기억을 되살리기 위한 아카이브 정도로만 사용할 수 있게 간단하게 정리할 예정입니다.

 

개요

MST(Minumum Spanning Tree)를 찾는데 사용되는 알고리즘.

임의의 connected graph가 주어졌을 때, greedy하게 간선을 선택하여 MST를 얻어낸다.

 

 

MST란?

Spanning tree는 graph 내의 모든 node를 포함하는 tree이다. Tree라는 것은 cycle이 없다는 것인데, cycle 없이 모든 node를 포함하려면 간선의 개수가 V - 1 개여야 한다.

즉 graph를 connected graph로 만드는 최소한의 간선(V - 1개)을 갖는 graph를 의미한다.

Spanning tree는 unique 하지 않다.

위 graph에서 spanning tree를 찾으면,

Spanning tree 1

Spanning tree2

Spanning tree3

이렇게 여러가지 형태의 spanning tree를 찾을 수 있다. 

 

MST는 spanning tree의 특수한 경우인데, spanning tree 중 간선의 cost의 합이 최소인 spanning tree를 MST라고 한다.

즉 MST는 간선이 V - 1 개인 connected graph 중에서 cost의 합이 최소인 graph이다.

 

 

알고리즘 설명

Kruskal 알고리즘은 다음과 같다.

1. Priority queue를 사용해서 cost가 작은 순으로 간선을 선택한다 (greedy)

2. 선택한 간선이 cycle을 만드는지 disjoint-set을 사용하여 판별한다. 즉 선택한 간선이 연결하는 두 node가 이미 같은 부분 집합에 있으면(이미 두 node 사이에 경로가 존재하면) 해당 간선은 cycle을 만드는 간선이므로 무시한다.

3. 선택한 간선이 cycle을 만들지 않으면 해당 간선을 graph에 추가시킨다.

4. 간선을 V - 1개 선택할 때 까지 1~3을 반복한다.

 

Disjoint-set(union-find)를 따로 구현해 줘야 해서 귀찮은 것 빼고는 매우 단순한 알고리즘이다.

 

 

코드

코드는 백준 1197번 최소 스패닝 트리 문제를 기준으로 작성하였다.

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

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

		int V, E;
		st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		PriorityQueue<Edge> edges = new PriorityQueue<Edge>(E);

		int node1, node2;
		long cost;
		for (int i = 1; i <= E; i++)
		{
			st = new StringTokenizer(br.readLine());
			node1 = Integer.parseInt(st.nextToken());
			node2 = Integer.parseInt(st.nextToken());
			cost = Long.parseLong(st.nextToken());
			//priority queue에 edge를 전부 추가
			edges.add(new Edge(node1, node2, cost));
		}

		DisjointSet ds = new DisjointSet(V);

		cost = 0;
		int cnt = 0;
		Edge e;
		while (!edges.isEmpty())
		{
			//edge를 V - 1개 선택하면 알고리즘 종료
			if (cnt >= V - 1)
				break;

			e = edges.poll();
			
			//두 node 사이에 경로가 존재하지 않을 경우에만 현재 선택한 edge를 추가함
			if (ds.find(e.node1) != ds.find(e.node2))
			{
				ds.union(e.node1, e.node2);
				cost += e.cost;
				cnt++;
			}
		}

		System.out.println(cost);

		br.close();
	}
}

class Edge implements Comparable<Edge>
{
	int node1;
	int node2;
	long cost;

	public Edge(int node1, int node2, long cost)
	{
		this.node1 = node1;
		this.node2 = node2;
		this.cost = cost;
	}

	public int compareTo(Edge other)
	{
		if (this.cost > other.cost)
			return 1;
		else if (this.cost < other.cost)
			return -1;
		else
			return 0;
	}
}

class DisjointSet
{
	int[] parent;

	public DisjointSet(int N)
	{
		parent = new int[N + 1];
		for (int i = 1; i <= N; i++)
			parent[i] = i;
	}

	public void union(int e1, int e2)
	{
		int parent1 = find(e1);
		int parent2 = find(e2);
		parent[parent1] = parent2;
	}

	public int find(int e)
	{
		if (parent[e] == e)
			return e;
		parent[e] = find(parent[e]);
		return parent[e];
	}
}

 

참고

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog