Problem Solving/Algorithm
[알고리즘] 최소 신장 트리 - 크루스칼 알고리즘
se0m
2021. 6. 9. 02:38
신장 트리(Spanning Tree)
원래 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프
[자료구조] #7_1 트리
트리 구현시 로직이 많이 들어가서 알고리즘 같은 느낌을 준다. 구현하기 복잡하기 때문에 자료구조 중에서 면접에서 자주 질문이 나오는 편이다. ** 트리(Tree) 구조 Node와 Branch를 이용해서, 사이
itsanisland.tistory.com
- 신장 트리의 조건
- 본래의 그래프의 모든 노드를 포함해야 함
- 모든 노드가 서로 연결
- 트리의 속성을 만족시킴(사이클이 존재하지 않음)
최소 신장 트리(Minimum Spanning Tree, MST)
- 가능한 Spanning Tree 중에서 간선의 가중치 합이 최소인 Spanning Tree를 지칭함
최소 신장 트리 알고리즘
- 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함
- 대표적인 최소 신장 트리 알고리즘
- Kruskal’s algorithm(크루스칼 알고리즘)
- Prim's algorithm(프림 알고리즘)
크루스칼 알고리즘(Kruskal's algorithm)
- 모든 정점을 독립적인 집합으로 만든다.
- 모든 간선을 비용을 기준으로 정렬하고 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
- 두 정점의 최상위 정점을 확인하고 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로 사이클이 생기지 않도록 하는 것임)
탐욕 알고리즘을 기초로 하고 있음 ▶ 당장 눈앞의 최소 비용을 선택해서 결과적으로 최적의 솔루션을 찾음
[알고리즘] 탐욕(Greedy) 알고리즘
탐욕 알고리즘(Greedy algorithm)탐욕 알고리즘은 문제를 해결할 때마다 그 순간 가장 최적인(가장 좋아 보이는) 선택을 하는 알고리즘 전략전체적인 최적의 해를 보장하진 않지만 계산량을 줄이면
itsanisland.tistory.com
Union-Find 알고리즘
- Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘
- 간단하게 노드들 중에 연결된 노드를 찾거나 노드들을 서로 연결할 때(합칠 때) 사용
Disjoint Set이란?
서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
공통 원소가 없는 (서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미함
(Disjoint Set = 서로소 집합 자료구조)
1) 초기화
- n 개의 원소가 개별 집합으로 이뤄지도록 초기화
2) Union
- 두 개별 집합을 하나의 집합으로 합침(두 트리를 하나의 트리로 만듬)
3) Find
- 여러 노드가 존재할 때 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 각 그룹의 최상단 원소(루트 노드)를 확인 → 크루스칼 알고리즘에서 사이클 여부 확인할 수 있음
Union-Find 알고리즘의 고려할 점
- Union 순서에 따라서 최악의 경우, 링크드 리스트와 같은 형태가 될 수 있음
- 이 때는 Find/Union 시 루트 노드를 확인하기 위한 계산량이 `O(N)`이 될 수 있으므로 해당 문제를 해결하기 위해 union-by-rank와 path compression 기법을 사용함
1. union-by-rank 기법
- 각 트리에 대해 높이(rank)를 기억해 두고
- Union 시 두 트리의 높이(rank)가 다르면 → 높이가 작은 트리를 높이가 큰 트리에 붙임
- 즉 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 함
- 높이가 동일하면 → 높이가 (h - 1)인 두 개의 트리를 합칠 때는 한쪽의 트리 높이를 1 증가시켜 주고 다른 쪽의 트리를 해당 트리에 붙여줌
- 초기화 시 모든 원소는 높이(rank)가 0인 개별 집합인 상태에서 하나씩 원소를 합칠 때 union-by-rank 기법을 사용한다면
- 높이가 `h`인 트리가 만들어지려면, 높이가 `(h - 1)`인 두 개의 트리가 합쳐져야 함
- 높이가 `(h - 1)`인 트리를 만들기 위해 최소 n개의 원소가 필요하다면 높이가 `h`인 트리가 만들어지기 위해서는 최소 `2n`개의 원소가 필요함
- 따라서 union-by-rank 기법을 사용하면 Union-Find 연산의 시간복잡도는 `O(N)`이 아닌 `𝑂(𝑙𝑜𝑔𝑁)`으로 낮출 수 있음(`2n` 개씩 처리 가능하므로)
2. path compression
- Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법
- Find를 실행한 노드는 이후 루트 노드를 한 번에 알 수 있음
union-by-rank와 path compression 기법 사용 시 시간 복잡도는 다음 계산식을 만족함을 증명:
`𝑂(𝑀*𝑙𝑜𝑔𝑁)`
- `𝑙𝑜𝑔𝑁`은 다음 값을 가짐을 증명되었음
- N이 2^65536 값을 가지더라도(거의 무한) 𝑙𝑜𝑔𝑁의 값이 65536의 값을 가지므로 거의 `O(1)`로 상수값에 가깝다고 볼 수 있음
| N | 𝑙𝑜𝑔𝑁 |
| 1 | 0 |
| 2 | 1 |
| 4 | 2 |
| 16 | 3 |
| 65536 | 4 |
| 2^65536 | 65536 |
크루스칼 알고리즘 Java 구현
import java.util.*;
public class KruskalMST {
static class Edge implements Comparable<Edge> {
int weight;
String node1;
String node2;
Edge(int weight, String node1, String node2) {
this.weight = weight;
this.node1 = node1;
this.node2 = node2;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
@Override
public String toString() {
return "(" + weight + ", '" + node1 + "', '" + node2 + "')";
}
}
static class UnionFind {
Map<String, String> parent = new HashMap<>();
Map<String, Integer> rank = new HashMap<>();
public void makeSet(String node) {
parent.put(node, node);
rank.put(node, 0);
}
public String find(String node) {
if (!parent.get(node).equals(node)) {
parent.put(node, find(parent.get(node))); // path compression
}
return parent.get(node);
}
public void union(String node1, String node2) {
String root1 = find(node1);
String root2 = find(node2);
if (root1.equals(root2)) return;
// union by rank
if (rank.get(root1) > rank.get(root2)) {
parent.put(root2, root1);
} else {
parent.put(root1, root2);
if (rank.get(root1).equals(rank.get(root2))) {
rank.put(root2, rank.get(root2) + 1);
}
}
}
}
public static List<Edge> kruskal(List<String> vertices, List<Edge> edges) {
List<Edge> mst = new ArrayList<>();
UnionFind uf = new UnionFind();
for (String vertex : vertices) {
uf.makeSet(vertex);
}
Collections.sort(edges); // weight 기준 오름차순 정렬
for (Edge edge : edges) {
if (!uf.find(edge.node1).equals(uf.find(edge.node2))) {
uf.union(edge.node1, edge.node2);
mst.add(edge);
}
}
return mst;
}
public static void main(String[] args) {
List<String> vertices = Arrays.asList("A", "B", "C", "D", "E", "F", "G");
List<Edge> edges = Arrays.asList(
new Edge(7, "A", "B"),
new Edge(5, "A", "D"),
new Edge(7, "B", "A"),
new Edge(8, "B", "C"),
new Edge(9, "B", "D"),
new Edge(7, "B", "E"),
new Edge(8, "C", "B"),
new Edge(5, "C", "E"),
new Edge(5, "D", "A"),
new Edge(9, "D", "B"),
new Edge(7, "D", "E"),
new Edge(6, "D", "F"),
new Edge(7, "E", "B"),
new Edge(5, "E", "C"),
new Edge(7, "E", "D"),
new Edge(8, "E", "F"),
new Edge(9, "E", "G"),
new Edge(6, "F", "D"),
new Edge(8, "F", "E"),
new Edge(11, "F", "G"),
new Edge(9, "G", "E"),
new Edge(11, "G", "F")
);
List<Edge> mst = kruskal(vertices, edges);
System.out.println("최소 신장 트리 (MST) 간선 목록:");
for (Edge e : mst) {
System.out.println(e);
}
}
}최소 신장 트리 (MST) 간선 목록:
(5, 'A', 'D')
(5, 'C', 'E')
(6, 'D', 'F')
(7, 'A', 'B')
(7, 'B', 'E')
(9, 'E', 'G')
시간 복잡도
크루스칼 알고리즘의 시간 복잡도는 `O(ElogE)`
- 다음 단계에서 2번 간선을 비용 기준으로 정렬하는 시간에 좌우됨 (즉 간선을 비용 기준으로 정렬하는 시간이 가장 큼)
- 모든 정점을 독립적인 집합으로 만든다.
- 노드의 개수로 `O(V)`
- 모든 간선을 비용을 기준으로 정렬하고 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
- 퀵소트를 사용한다면 시간 복잡도는 `O(n log n)`이며 간선이 `n` 이므로 → `O(E log E)`
- 두 정점의 최상위 정점을 확인하고 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로 사이클이 생기지 않도록 하는 것임)
- union-by-rank와 path compression 기법 사용 시 시간 복잡도가 결국 상수값에 가까움 → `O(1)`
