728x90
신장 트리(Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm)
신장 트리(Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm)에 대해서 배워보자.
신장 트리
신장 트리(Spanning Tree)란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
를 의미한다.
크루스칼 알고리즘
크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree, MST)
를 구하기 위해서 사용되는 알고리즘 이다. 크루스칼 알고리즘은 그리디(Greedy)
알고리즘으로 분류된다. 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다.
크루스칼 알고리즘을 구현할 때에는 Union-Find 알고리즘을 사용하므로, 잘 모른다면 링크를 통해서 미리 배우도록 하자.
위 그림이 최소 신장 트리를 나타낸다. 위 그래프에서 각 A, B, C 도시간 도로를 건설하는 비용이 10, 11, 12라고 할때 최소 비용으로 모든 도로를 연결하기 위한 비용은 10 + 11 = 21
일 것이다. 따라서, 최소 신장 트리 알고리즘이란 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘이라고 할 수 있다.
시간 복잡도는 다음과 같다.
$$O(ElogE)$$
E 는 간선의 개수를 의미하며, 간선을 정렬하는 작업이 시간이 가장 오래 걸리는 작업니다. E 개의 데이터를 정렬 했을 때의 시간 복잡도가 바로 O(ElogE)
인 것이다.
동작 과정
- 간선 데이터를 비용에 따라 오름차순으로 정렬
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 O
- 사이클이 발생하면 최소 신장 트리에 포함 X
최소 신장 트리에서 간선의 개수는 노드의 개수 - 1
과 같다.
구현
// Edge : 간선에 연결되어 있는 노드들과 비용을 저장하기 위한 클래스
class Edge implements Comparable<Edge> {
private int cost;
private int nodeA;
private int nodeB;
public Edge(int cost, int nodeA, int nodeB) {
this.cost = cost;
this.nodeA = nodeA;
this.nodeB = nodeB;
}
public int getCost() {
return cost;
}
public int getNodeA() {
return nodeA;
}
public int getNodeB() {
return nodeB;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
public class Main {
private static int vertexCount; // 노드, 정점
private static int edgeCount; // 간선의 개수 = Union 연산의 횟수
private static int[] parents; // 부모 테이블
private static List<Edge> edges = new ArrayList<>();
private static int answer = 0; // 문제에서 구하고자 하는 답 : MST 를 만드는데 드는 비용
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
vertexCount = sc.nextInt();
edgeCount = sc.nextInt();
initParents();
for (int i = 0; i < edgeCount; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
edges.add(new Edge(cost, a, b));
}
// 간선을 비용순으로 정렬
Collections.sort(edges);
// Kruskal Algorithm 수행
kruskal();
System.out.println(answer);
}
// 부모 테이블을 자기 자신의 노드로 초기화
private static void initParents() {
parents = new int[vertexCount + 1];
for (int i = 1; i <= vertexCount; i++) {
parents[i] = i;
}
}
// Kruskal Algorithm
private static void kruskal() {
// 간선을 하나씩 확인하며
for (int i = 0; i < edges.size(); i++) {
int cost = edges.get(i).getCost();
int nodeA = edges.get(i).getNodeA();
int nodeB = edges.get(i).getNodeB();
// 사이클이 발생하지 않는 경우에만 집합에 포함(Union 연산 수행)
// 즉, nodeA 와 nodeB 에 대한 root 값이 달라야 한다는 의미
if (findParent(nodeA) != findParent(nodeB)) {
unionParent(nodeA, nodeB);
answer += cost; // 최종 비용을 구하기 위한 연산
}
}
}
// find 연산
// 특정 원소가 속한 집합을 찾기 : 경로 압축(Path Compression)
private static int findParent(int vertex) {
if (vertex == parents[vertex]) return vertex;
return parents[vertex] = findParent(parents[vertex]);
}
// union 연산
private static void unionParent(int nodeA, int nodeB) {
nodeA = findParent(nodeA);
nodeB = findParent(nodeB);
if (nodeA < nodeB) {
parents[nodeB] = nodeA;
} else {
parents[nodeA] = nodeB;
}
}
}
References
728x90
'Algorithms > 기본 지식' 카테고리의 다른 글
깊이 우선 탐색(DFS) (0) | 2022.01.03 |
---|---|
위상 정렬 (0) | 2021.12.14 |
서로소 집합 (0) | 2021.12.12 |
플로이드 워셜 알고리즘 (0) | 2021.12.12 |
최단 경로와 다익스트라 알고리즘 (0) | 2021.12.11 |