[알고리즘] 크루스칼(Kruskal), 프림(Prim) 알고리즘
크루스칼 알고리즘 (Kruskal's Algorithm)
크루스칼 알고리즘은 최초의 정점 없이, 최소 간선을 하나씩 추가하여 MST (Minimum Spanning Tress, 최소신장트리) 를 생성해 나가는 알고리즘이다.
- 가중치가 최소인 간선을 하나씩 선택해 나간다.
- 기본적으로 그리디 알고리즘을 기반으로 한다. (Prim 알고리즘도 마찬가지)
- 모든 정점을 순회하고, 사이클을 만들지 않아야 한다.
- 그래프 G(V, E)인 경우, 이진힙 이용시 평균 O(E*logV)의 시간복잡도 (V: 정점수, E: 간선수)
★ 크루스칼 알고리즘은 서로소 집합만 정확히 알고 있으면 매커니즘은 어렵지 않다.
💡 크루스칼 알고리즘 매커니즘
1. 정렬
주어진 그래프의 모든 간선의 가중치를 오름차순으로 정렬한다.
결과: 가중치 정렬 값의 집합
2. 최소간선선택
정렬된 간선을 순서대로 선택하면서, 간선의 양 끝 정점을 Union한다.
단, 이때 선택된 두 정점이 같은 집합에 속해있다면 사이클(cycle)이 있다고 판단하고 포함시키지 않는다.
사이클을 판단하기 위해 서로소 집합을 활용한다.
3. 반복
다음 간선 중 최소간선을 선택하고, n-1개의 간선이 선택되면 종료
결과: 선택된 정점의 집합
📌 크루스칼 알고리즘 코드구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
/*
input(첫 줄의 첫 숫자는 정점의 개수, 두 번째 숫자는 간선의 개수).
6 9
1 6 5
2 4 6
1 2 7
3 5 15
5 6 9
3 4 10
1 3 11
2 3 3
4 5 7
*/
public class KruskalTest {
static int V, E, mst;
static int[] parent;
static ArrayList<Edge> edgeList;
public static void main(String[] args) throws IOException {
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); // 정점의 개수
E = Integer.parseInt(st.nextToken()); // 간선의 개수
edgeList = new ArrayList<Edge>();
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken()); // from정점
int end = Integer.parseInt(st.nextToken()); // to정점
int value = Integer.parseInt(st.nextToken()); // 가중치
edgeList.add(new Edge(start, end, value)); // 간선들을 리스트에 다 집어넣기
}
parent = new int[V+1];
mst = 0;
// makeSet
for (int i = 1; i <= V; i++) {
parent[i] = i;
}
Collections.sort(edgeList); // 간선의 가중치 순으로 오름차순 정렬
// 낮은 가중치부터 크루스칼 알고리즘 진행
for (int i = 0; i < E; i++) {
Edge edge = edgeList.get(i);
if(find(edge.start) != find(edge.end)) { // 사이클이 존재하지 않는 경우에만 간선을 선택
union(edge.start, edge.end);
mst += edge.value;
}
}
System.out.println("최종 비용 : " + mst);
}
// 해당 정점의 부모(대표자) 찾기
public static int find(int x) {
if(parent[x] == x)
return x;
else
return find(parent[x]);
}
// 두 집합 합치기
private static void union(int a, int b) {
int p1 = find(a);
int p2 = find(b);
if(p1 != p2) { // 두 집합의 대표자가 다른 경우 합치기
parent[p1] = p2;
}
// if (p1 > p2) {
// parent[p1] = p2;
// } else {
// parent[p2] = p1;
// }
}
// 간선 정보
static class Edge implements Comparable<Edge>{
int start;
int end;
int value;
public Edge(int start, int end, int value) {
super();
this.start = start;
this.end = end;
this.value = value;
}
@Override
public int compareTo(Edge o) { // 가중치를 기준으로 오름차순 정렬
return this.value > o.value ? 1 : -1;
}
}
}
프림 알고리즘 (Prim's Algorithm)
무방향 그래프, 최소신장트리(Minimum Spanning Tree) 기반
- 임의의 정점을 선택하고 정점으로부터 최소간선을 선택하면서 정점을 추가해나가는 알고리즘 (기존정점을 가지고)
- 최소 비용 신장 트리를 찾는 알고리즘
- 그래프 G(V, E)인 경우, 이진힙 이용시 평균 O(E*logV)의 시간복잡도, 최악 O(V²) (V: 정점수, E: 간선수)
💡 프림 알고리즘 실행순서
1. 최초 정점선택
임의의 정점 선택
결과: 정점 S
2. 최소간선선택
최초 정점으로부터 최소 비용의 정점을 선택
결과: 선택된 정점 집합
3. 반복
다음 정점선택을 반복. 단, 기존 비용과 계속 비교하여 최소 비용을 선택하고 갱신 (n-1번 반복)
결과: 선택된 정점의 집합
간선의 개수 적으면 크루스칼이 빨리되고, 정점의 개수가 적다면 프림이 빨리 된다