[알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘 (Kruskal Algorithm)

① 크루스칼 알고리즘이란?

▷ 최소 비용 신장 트리를 찾는 알고리즘입니다.

▷ 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다.

▷ 최소 스패닝 트리(MST, Minimum Spanning Tree)를 찾음으로서 간선의 가중치의 합이 최솟값이 되도록 하는 알고리즘이라고도 할 수 있습니다.

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

   ▶ 최소 스패닝 트리 : 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리.

▷ 변의 개수 E(간선), 꼭짓점의 개수 V(노드)라고 하면 이 알고리즘은 O (E log V )의 시간복잡도를 가진다.

   ▶ E(간선): 거리, 비용에 해당되며 선에 해당되는 부분입니다.

   ▶ V(노드): 정점, 도시에 해당되며 동그라미에 해당되는 부분입니다.

▷ 유니온 파인드(Union-Find) 개념에 대한 정립이 선행되어야 하므로 꼭 읽어주세요!!! 이 후 구현하는데 사용되게 됩니다.

   ▶ http://brenden.tistory.com/33 

② 그림으로 보는 크루스칼 알고리즘 (Kruskal Algorithm)

위의 그래프를 살펴 보았을 때 노드는 6개이고, 간선의 갯수는 9개 입니다.

크루스칼 알고리즘은 다음과 같은 절차로 진행됩니다.

1. STEP(1) : 모든 간선들을 거리(비용,가중치)를 기준으로 오름차순으로 정렬한다.

2. STEP(2) :  정렬된 간선을 순서대로 선택한다.

3. STEP(3) :  선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 두 정점을 연결시킨다.

▷즉 사이클 테이블을 통해 두 점이 연결되어 있는지 여부를 파악합니다. (Union-Find 알고리즘 이용한다)

▷최소비용 신장 트리에서는 사이클이 발생되면 안되기 때문입니다.

STEP(1)은 위와 같이 모든 간선들을 '거리(비용, 가중치)를 기준으로 먼저 오름차순 정렬'을 수행하였습니다.

STEP(2),(3)을 진행합니다. 위 그림을 보면 가장 가중치가 가장 낮은 3이였던 간선을 선택합니다. 두 노드를 연결해 줍니다.

사이클 테이블에 4의 경우 2로 갱신하게 되고 나머지 경우 모두 1로 갱신하게 됩니다. 손이 가는대로 예시를 만들었더니 조금 안 예쁘게 나왔네요..

위 그림처럼 가장 가중치가 낮은 두 번째 간선을 선택합니다. 사이클 테이블도 갱신해줍니다.

위 그림처럼 가장 가중치가 낮은 세 번째 간선을 선택합니다. 사이클 테이블도 갱신해줍니다.

위 그림처럼 가장 가중치가 낮은 네 번째 간선을 선택하면 안됩니다!!!! 사이클이 생기기 때문에입니다.

그 이유로 가장 가중치가 낮은 다섯 번째 간선을 선택합니다. 사이클 테이블도 갱신해줍니다.

위 그림처럼 가장 가중치가 낮은 여섯 번째 간선을 선택합니다. 6개의 모든 노드가 연결되었기 때문에 이 후에 있는 간선들은 확인하지 않아도 됩니다. 모든 사이클 테이블의 모든 값이 1이 되면서 최소 비용 신장 트리가 만들어진 것을 볼 수 있습니다.

③ Kruskal Algorithm 알고리즘 코드

	import java.util.ArrayList;
	import java.util.Collections;
	class Edge implements Comparable<Edge> {
	int v1;
	int v2;
	int cost;
	Edge(int v1, int v2, int cost) {
	this.v1 = v1;
	this.v2 = v2;
	this.cost = cost;
	}
	@Override
	public int compareTo(Edge o) {
	if(this.cost < o.cost)
	return -1;
	else if(this.cost == o.cost)
	return 0;
	else
	return 1;
	}
	}
	public class Main {
	public static int[] parent;
	public static ArrayList<Edge> edgeList;
	public static void union(int x, int y) {
	x = find(x);
	y = find(y);
	if(x != y)
	parent[y] = x;
	}
	public static int find(int x) {
	if(parent[x] == x) {
	return x;
	}
	return parent[x] = find(parent[x]);
	}
	public static boolean isSameParent(int x, int y) {
	x = find(x);
	y = find(y);
	if(x == y) return true;
	else return false;
	}
	public static void main(String[] args) {
	edgeList = new ArrayList<Edge>();
	edgeList.add(new Edge(1,4,4));
	edgeList.add(new Edge(1,2,6));
	edgeList.add(new Edge(2,3,5));
	edgeList.add(new Edge(2,4,3));
	edgeList.add(new Edge(2,5,7));
	edgeList.add(new Edge(2,6,8));
	edgeList.add(new Edge(3,6,8));
	edgeList.add(new Edge(4,5,9));
	edgeList.add(new Edge(5,6,11));
	parent = new int[7];
	for(int i = 1; i <= 6; i++) {
	parent[i] = i;
	}
	Collections.sort(edgeList);
	int sum = 0;
	for(int i = 0; i < edgeList.size(); i++) {
	Edge edge = edgeList.get(i);
	if(!isSameParent(edge.v1, edge.v2)) {
	sum += edge.cost;
	union(edge.v1, edge.v2);
	}
	}
	System.out.println(sum);
	}
	}

view raw Kruskal_Algorithm.java hosted with ❤ by GitHub

④ Kruskal Algorithm 관련 알고리즘 문제

(백준 1197) 최소 스패닝 트리 (https://www.acmicpc.net/problem/1197) 해결 코드

참고

1. https://ko.wikipedia.org/wiki/크러스컬_알고리즘
2. https://blog.naver.com/ndb796/221230994142 (나동빈 님 블로그)