[JAVA] Kruskal 알고리즘

Kruskal?

Kruskal 알고리즘은 Greedy 기법을 이용하여 각 가중치를 간선에 할당한 그래프(어떤 비용을 가지고 있는 간선으로 이루어진 그래프)의 모든 정점을 최소 비용으로 연결하는 최적의 해를 구하는 데 사용하는 알고리즘이다.

글로만 설명하면 머리만 아프니, 바로 그림과 함께 예제를 보자.

---

위와 같이 간선과 노드, 그리고 각 간선이 가지는 비용으로 이루어진 그래프가 주어졌을 때, 우리의 임무는 각 노드들을 최소한의 비용으로 모두 연결하는 것이다. 그러나 여기서 각 연결은 서로가 맞물리는 상황(사이클)이 발생하지 않아야 한다.

Kruskal 알고리즘의 기본적인 원리는 다음과 같다.

 

 1. n개의 노드가 모두 연결되는 제일 작은 경우의 수는 n-1이다.

 

 2. 비용 기준으로 오름차순 정렬하여 제일 비용이 작은 간선부터 Union을 이용하여 연결 한다.

 

 3. 각 연결 수행 전에 해당 연결이 Cycle을 만드는 연결인지 Find를 활용하여 알아낸다.

    1) 만약 사이클을 만든다면 사용할 수 없는 간선이므로 다음 간선으로 이동하여 확인을 이어간다.

    2) 또한 사이클을 만드는 지 여부는 연결될 노드가 연결 전부터 같은 부모 노드를 가지고 있다면, 이는 사이클이다!

 

 4. n-1개의 간선이 연결되었으면 종료한다.

 

이해하기 쉽게 과정을 그림으로 정리해보면 이와 같다.

 

출처: https://www.dotnetlovers.com/article/230/minimum-spanning-tree-mst-using-kruskals-algorithm

원리를 알았으면, 바로 코드를 작성하여 확인해볼 수 있다!

---

◎Edge.java

package com.choonham;

public class Edge {

	public int v1;
	public int v2;
	public int cost;

	public Edge() {
		// TODO Auto-generated constructor stub
	}

	public Edge(int v1, int v2, int cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

}

◎Union_Find.java

package com.choonham;

public class Union_Find {

	public Union_Find() {

	}

	public int getParent(int parent[], int x) {
		if (parent[x] == x)
			return x; // 부모노드가 자기 자신일 경우, 재귀 stop
		return parent[x] = getParent(parent, parent[x]); // 아닐 경우 한번 더 진행
	}

	// 부모 노드의 크기를 비교 후 작은 값을 큰 값의 부모로
	public void unionParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if (a < b)
			parent[b] = a;
		else
			parent[a] = b;
	}

	// 두 수가 서로 연결되어 있는 지 판단
	public boolean findParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if (a == b)
			return true;
		else
			return false;
	}

}

◎Main.java

package com.choonham;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {

	public static void main(String[] args) {
		Union_Find uf = new Union_Find();
		List<Edge> edgeList = new ArrayList<>();
        //부모 노드 생성
		int[] parent = new int[5];
		for (int i = 0; i < 5; i++) {
			parent[i] = i;
		}
       
        //간선 정보 삽입
		edgeList.add(new Edge(0, 3, 3));
		edgeList.add(new Edge(0, 4, 12));
		edgeList.add(new Edge(1, 2, 2));
		edgeList.add(new Edge(1, 3, 5));
		edgeList.add(new Edge(2, 3, 3));
		edgeList.add(new Edge(2, 4, 7));
        
        //오름차순 정렬
		Collections.sort(edgeList, new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return (o1.cost < o2.cost ? -1 : ((o1.cost == o2.cost) ? 0 : 1));
			}
		});

		int sum = 0;

		for (int i = 0; i < edgeList.size(); i++) {
			Edge edge = edgeList.get(i);
			if (!uf.findParent(parent, edge.v1, edge.v2)) { //두 노드가 같은 부모를 가지고 있지 않다면,
				sum += edge.cost;
				uf.unionParent(parent, edge.v1, edge.v2);  //연결
			}
		}

		System.out.println(sum);

	}
}

---

◎Output

위와 같이 모든 노드를 연결하는 최소 비용을 구할 수 있다!

---

사실 Union-Find 알고리즘만 잘 이해하고 있다면, 구현하는데 크게 어려울 거 없는 알고리즘이다. 

 

 

 

끝!!