스패닝 트리: 그래프에서 일부 간선을 선택해서 만든 트리
최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치 합이 최소인 트리
스패닝 트리를 구하는 알고리즘
- Prim: 정점을 점점 확장해 나가는 방식 (힙을 써서 구현 - 정점번호, 가중치 저장) --> 최소값을 우선 순위 큐를 이용하면 최소 값을 logE만에 찾을 수 있다. 이 경우 시간복잡도는 O(ElogE)가 된다. 모든 간선이 힙에 한번 씩 들어갔다가 나오기 때문
- 그래프에서 아무 정점이나 선택한다.
- 선택한 정점과 선택하지 않은 정점을 연결하는 간선 중에 최소값을 고른다. 이 간선을 (u, v)라고 한다.
- 선택한 간선을 최소 스패닝 트리에 추가하고, 선택하지 않았던 정점 v를 선택한다.
- 2번으로 돌아간다
- Kruskal: 간선을 점점 확장해 나가는 방법
- 가중치가 작은 edge부터 살펴본다 --> 간선의 길이 순으로 먼저 정렬해야 한다. O(ElogE)
- edge e가 (u, v, c)일 때, u와 v가 서로 다른 집합이면 e를 최소 스패닝 트리에 추가한다. O(E) - union/find 연산
Prim 알고리즘 풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int v = in.nextInt();
int e = in.nextInt();
LinkedList<Edge>[] pair = new LinkedList[v + 1];
HashSet<Integer> vSet = new HashSet<Integer>();
for (int i = 1; i <= v; i++) {
pair[i] = new LinkedList<Edge>();
vSet.add(i);
}
for (int i = 0; i < e; i++) {
int start = in.nextInt();
int end = in.nextInt();
long cost = in.nextLong();
pair[start].add(new Edge(end, cost));
pair[end].add(new Edge(start, cost));
}
int currentNode = 1;
long ans = 0;
vSet.remove(1);
PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
pq.addAll(pair[currentNode]);
while (!vSet.isEmpty()) {
Edge minEdge = pq.poll();
if (vSet.contains(minEdge.v)) {
ans += minEdge.cost;
currentNode = minEdge.v;
vSet.remove(currentNode);
pq.addAll(pair[currentNode]);
}
}
System.out.println(ans);
}
}
class Edge implements Comparable<Edge> {
int v;
long cost;
public Edge(int v, long cost) {
this.v = v;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.cost, o.cost);
}
}
Kruskal 알고리즘 풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int v = in.nextInt();
int e = in.nextInt();
PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
int vSet[] = new int[v + 1];
for (int i = 1; i <= v; i++) {
vSet[i] = i;
}
for (int i = 0; i < e; i++) {
int start = in.nextInt();
int end = in.nextInt();
long cost = in.nextLong();
pq.add(new Edge(start, end, cost));
}
long ans = 0;
if (!pq.isEmpty()) {
Edge firstEdge = pq.poll();
ans += firstEdge.cost;
union(firstEdge.v1, firstEdge.v2, vSet);
}
while (!isFinished(vSet) && !pq.isEmpty()) {
Edge minEdge = pq.poll();
int v1Contains = find(minEdge.v1, vSet);
int v2Contains = find(minEdge.v2, vSet);
if (v1Contains != v2Contains) {
ans += minEdge.cost;
union(minEdge.v1, minEdge.v2, vSet);
}
}
System.out.println(ans);
}
public static void union(int x, int y, int[] vSet) {
int ux = find(x, vSet);
int uy = find(y, vSet);
vSet[uy] = ux;
}
public static int find(int x, int[] vSet) {
if (vSet[x] == x) {
return x;
}
vSet[x] = find(vSet[x], vSet);
return vSet[x];
}
public static boolean isFinished(int[] vSet) {
int now = vSet[1];
for (int i = 1; i < vSet.length; i++) {
if (vSet[i] != now) {
return false;
}
}
return true;
}
}
class Edge implements Comparable<Edge> {
int v1, v2;
long cost;
public Edge(int v1, int v2, long cost) {
this.v1 = v1;
this.v2 = v2;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.cost, o.cost);
}
}