최소 신장 트리(Minimum Spanning Tree)
그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리
📌 특징
- 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
- N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개다.
- 최소 신장 트리를 만드는 알고리즘으로 크루스칼과 프림이 있다.
📌 크루스칼(Kruskal) 알고리즘
최소 신장 트리를 만드는 알고리즘(Union-Find 이용)
🔎 에지 리스트(Edge List)
데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.
클래스는 일반적으로 출발, 도착 노드와 가중치 변수로 구성된다.
class Edge {
int start;
int end;
int weight;
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
✔ 사이클 처리를 위한 유니온 파인드 배열(⭐)
find 연산 결과가 동일할 경우, 동일 집합에 속하므로 두 정점 모두 동일한 정점과 연결된 상태라는 것이다.
위 그림과 같은 상태가 되므로, find 결과가 동일한 두 정점을 union 연산하게 되면 사이클이 발생하는 것이다.
static void union(int a, int b) {
flag = false;
int pa = find(a);
int pb = find(b);
if (pa == pb) return; //사이클
flag = true;
if (pa < pb) UF[pb] = pa;
else UF[pa] = pb;
}
static int find(int a) {
if (a == UF[a]) return a;
else return UF[a] = find(UF[a]);
}
🔎 가중치 기준으로 정렬
에지 리스트의 각 클래스를 가중치 기준으로 오름차순 정렬한다. 이를 위해 클래스가 Comparable() 함수를 구현하는 방법이 있으며, 최소 트리를 위해 최소 비용부터 탐색하는 것이다.
static class Edge implements Comparable<Edge> {
int start;
int end;
int weight;
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight; //가중치 오름차순
}
}
🔎 가중치가 낮은 에지부터 연결
가중치가 낮은 에지부터 find 연산을 통해 사이클을 확인하고, 사이클이 없을 경우 union 연산을 통해 두 정점을 연결한다.
🔎 바로 앞의 과정 반복
전체 노드의 개수가 N개일 때, 연결한 에지의 개수가 N - 1이 될 때까지 반복한다.
🔎 구현
import java.io.IOException;
import java.util.*;
public class Main {
static int V; //노드의 개수
static int E; //에지의 개수
static ArrayList<Edge> A; //에지 리스트
static int[] UF; //유니온-파인드 배열
static boolean flag; //사이클 여부
public static void main(String[] args) throws IOException {
V = readInt();
E = readInt();
A = new ArrayList<>();
UF = new int[V + 1];
int ans = 0;
int edge_cnt = 0; //연결되는 에지 개수
for (int i = 0; i < E; i++) {
int a = readInt();
int b = readInt();
int c = readInt();
A.add(new Edge(a, b, c));
}
//유니온 파인드 배열 초기화
for (int i = 1; i <= V; i++) {
UF[i] = i;
}
Collections.sort(A);
for (int i = 0; i < E; i++) {
int a = A.get(i).start;
int b = A.get(i).end;
union(a, b);
if (flag) {
ans += A.get(i).weight; //사이클이 없으므로 연결
edge_cnt++; //에지 추가
}
if (edge_cnt == V - 1) break; //에지 개수 == 노드 개수 - 1
}
System.out.println(ans);
}
static void union(int a, int b) {
flag = false;
int pa = find(a);
int pb = find(b);
if (pa == pb) return; //사이클
flag = true;
if (pa < pb) UF[pb] = pa;
else UF[pa] = pb;
}
static int find(int a) {
if (a == UF[a]) return a;
else return UF[a] = find(UF[a]);
}
static class Edge implements Comparable<Edge> {
int start;
int end;
int weight;
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight; //가중치 오름차순
}
}
static int readInt() throws IOException {
int c, n = System.in.read() & 15;
while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
return n;
}
}
🔎 수행 과정
두 정점 중 작은 숫자를 대표 노드로 한다.
✔ find(4) != find(5) //4 != 5 (union 수행)
✔ find(1) != find(3) //1 != 3 (union 수행)
✔ find(2) != find(4) // 2 != 4 (union 수행)
✔ find(2) = 2, find(5) -> find(4) -> 2 //동일 값이므로 사이클 발생
✔ find(1) != find(2) //1 != 2 (union 수행)
📌 프림(Prim) 알고리즘
최소 신장 트리를 만드는 알고리즘(우선순위 큐 이용)
🔎 에지 리스트
그래프를 에지 중심으로 저장하되, 크루스칼과 달리 인접 리스트 형태로 만든다.
클래스는 도착 정점과 가중치로 구성된다.
class Edge {
int end;
int weight;
public Edge(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
🔎 체크 배열
해당 정점이 완성된 트리에 포함되었는지 여부를 확인한다. 이것은 사이클 여부를 확인하는 용도로 사용될 수 있다. 트리에 포함되었다는 것은 서로 연결된 상태라는 의미이며, 연결된 정점끼리 다시 연결할 경우 사이클이 발생할 수 있다.
또한, 짧은 경로부터 찾기 때문에 이미 방문한 곳을 다시 방문할 필요가 없다.
🔎 우선순위 큐
가중치가 낮은 경로부터 찾기 위해 가중치 기준으로 정렬한다. 이는 우선순위 큐의 매개변수로 구현된 Comparator를 넣어주면 된다.
//기본 형태
PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
});
//람다
PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
//comparingInt()
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
🔎 가중치가 낮은 에지부터 연결
가중치가 낮은 에지부터 우선순위 큐에서 뽑아 방문 전이라면 체크한다. 뽑힌 정점에서 다시 연결된 에지를 보고 마찬가지로 다음 정점이 방문 전이라면 우선순위 큐에 넣는다.
🔎 모든 정점을 방문할 때까지
🔎 구현
import java.io.IOException;
import java.util.*;
public class Main {
static int V; //정점의 개수
static int E; //에지의 개수
static ArrayList<Edge>[] A; //에지 리스트
static int[] ch; //방문 배열
static int ans; //최소 경로
static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
public static void main(String[] args) throws IOException {
V = readInt();
E = readInt();
A = new ArrayList[V + 1];
ch = new int[V + 1];
ans = 0;
for (int i = 1; i <= V; i++) {
A[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
int a = readInt();
int b = readInt();
int c = readInt();
A[a].add(new Edge(b, c));
A[b].add(new Edge(a, c));
}
pq.offer(new Edge(1, 0));
Prim();
System.out.println(ans);
}
static void Prim() {
int ch_cnt = 0; //모든 정점 방문 여부
while (!pq.isEmpty() && ch_cnt < V) {
Edge n = pq.poll();
if (ch[n.end] == 0) { //방문 전
ch[n.end] = 1;
ch_cnt++;
ans += n.weight; //경로 계산
for (Edge edge : A[n.end]) //방문 장소랑 연결된 경로
if (ch[edge.end] == 0) pq.offer(edge); //방문 전
}
}
}
static class Edge {
int end;
int weight;
public Edge(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
static int readInt() throws IOException {
int c, n = System.in.read() & 15;
while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
return n;
}
}
🔎 수행 과정
✔ 1번 노드에서 시작 (가중치 0)
✔ 1번과 연결된 에지 중 방문 전인 노드를 우선순위 큐에 넣기
✔ 최소 경로인 (3, 3) 노드 방문
✔ 3번과 연결된 에지 중 방문 전인 노드를 우선순위 큐에 넣기
✔ 최소 경로인 (2, 8) 노드 방문
✔ 2번과 연결된 에지 중 방문 전인 노드를 우선순위 큐에 넣기
✔ 최소 경로인 (4, 4) 노드 방문
✔ 4번과 연결된 에지 중 방문 전인 노드를 우선순위 큐에 넣기
✔ 최소 경로인 (5, 2) 노드 방문
모든 정점을 방문했으므로 종료
Reference:
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의
자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성
www.inflearn.com
