크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 즉, 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다.
용어
- 노드 = 정점 = 도시: 그래프에서 동그라미에 해당하는 부분
- 간선 = 거리 = 비용: 그래프에서 선에 해당하는 부분
예시
간선을 거리가 짧은 순서대로 그래프에 포함시키는 방법
모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함시킨다
노드 1부터 노드 7까지 연결된 모든 간선 정보를 저장한 것이다.
노드 6, 7은 이미 다른 노드들의 간선 정보에 모두 포함이 되어있기 때문에 존재하지 않는다.
다음은 오름차순으로 정렬시킨다.
다음을 순차적으로 진행한다.
-
정렬된 순서에 맞게 그래프에 포함시킨다
-
포함시키기 전에는 사이클 테이블을 확인한다
-
사이클을 형성하는 경우 간선을 포함하지 않는다
사이클 발생 여부는 Union-Find 알고리즘을 사용하면 된다.
Java 소스 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
class A implements Comparable<A>{
int s;
int e;
int v;
public A(int s, int e, int v) {
super();
this.s = s;
this.e = e;
this.v = v;
}
@Override
public int compareTo(A arg0) { //min Heap을 만들기 위한 우선순위 큐용 Comparable 메서드
return arg0.v >= this.v ? -1 : 1;
}
}
public class source {
public static int find(int a){
if(a==parent[a]) return a; //초기화된 상태(정점이 처음 등장)이면 자기 자신이 부모
parent[a] = find(parent[a]); //find 할 때마다 부모는 최상위부모로 설정 (성능 향상)
return parent[a];
//return find(parent[a]); ← 최상위 부모를 저장하지 않고 매번 여러 단계를 올라가 찾으면 시간 초과 발생
}
public static void union(int a, int b){
int aRoot = find(a);
int bRoot = find(b);
if(aRoot != bRoot){
parent[aRoot] = b;
} else {
return;
}
}
static int N; // 정점의 개수
static int E; // 간선의 개수
static PriorityQueue<A> pq; // 간선 값을 Min Heap 으로 하는 우선순위 큐
static int[] parent; // disjoint-set(union find)에서 필요한 부모 노드를 저장하는 배열
static boolean[] visit; //방문 여부 배열
static int result; //결과 값 저장
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.valueOf(br.readLine()); //노드의 개수
E = Integer.valueOf(br.readLine()); // 간선의 개수
parent = new int[N+1]; //Disjoint-set
visit = new boolean[N+1];
result = 0;
pq = new PriorityQueue<A>();
String [] tempStr ;
for (int i = 0; i < E; i++) {
tempStr = br.readLine().split(" ");
pq.add(new A(Integer.valueOf(tempStr[0]), Integer.valueOf(tempStr[1]), Integer.valueOf(tempStr[2])));
} //모든 간선에 대해 [시작, 끝, 비용] 을 가진 클래스로 우선순위 큐에 add
for (int i = 1; i <= N; i++) {
parent[i]=i;
} // union-find 의 초기화는 일단 자기 자신의 부모노드는 자기 자신으로 설정
for (int i = 0; i < E; i++) { //모든 간선에 대해서 확인
A oneNode = pq.poll(); // 현재 큐에 있는 모든 인스턴스 중 비용이 가장 작은 간선이 poll 된다.
int start = oneNode.s;
int end = oneNode.e;
int a = find(start); // 만약 이 간선을 선택해서 연결한다고 했을때 사이클이 생기면 안되므로
int b = find(end); // 양쪽의 루트(최상위부모)노드가 무엇인지 확인하고
if( a == b ) continue; //만약 같으면 선택하지 않고 넘어간다.
union(start,end); //두개의 루트 노드가 달랐다면 한쪽의 최상위 부모를 다른 한쪽의 부모로 설정하고
result += oneNode.v; //선택된 간선이므로 간선의 비용을 더한다.
}
System.out.println(result);
}
}출처
Be More!