* MST란?
Minimum Spanning Tree의 약자로, 직역하면 최소 신장 트리라고 불린다.
Spanning Tree는 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
앞에 Minimum을 붙이면 각 간선의 가중치가 다른 경우 최소의 가중치로 연결하여 모든 정점을 방문하는 것을 말한다.
즉, MST에서는 간선의 가중치가 최소로 모든 정점을 방문해야하며 사이클이 생겨서는 안된다.
MST에는 크게 Kruskal(크루스칼) 알고리즘과 Prim(프림) 알고리즘이 존재한다.
* 크루스칼 알고리즘 (+Union-Find)
1. 간선을 가중치에 따라 오름차순으로 정렬한다. (Comparable 사용)
2. 가장 가중치를 가지는 간선을 첫번째 간선으로 선택한다.
3. 가중치가 작은 간선을 선택한다.
4. 선택한 간선과 이전에 선택한 간선이 사이클을 이루는지 확인한다. (Union-Find(Disjoint-Set) 사용)
Union-Find 자료구조에서 Disjoint-Set 확인 방법은 다음과 같다.
1. 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화 합니다.
2. Union (합치기) 연산 : 두 원소 a, b 가 주어질 때, 이들이 속한 두 집합을 하나로 합칩니다.
3. Find (찾기) 연산 : 어떤 원소 a 가 주어질 때, 이 원소가 속한 집합을 반환합니다.
즉, disjoint를 통해 같은 집합여부를 확인할 수 있다.
이를 소스코드로 표현하면 다음과 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | // Disjoint 초기화 int[] disjoint = new int[n + 1]; for (int i = 0; i < n + 1; i++) { disjoint[i] = i; //disjoint[i]에는 부모의 정점의 번호를 } // Disjoint Find public static int find(int x) { if (disjoint[x] == x) return x; else return disjoint[x] = find(disjoint[x]); } //Disjoint Union int x = find(u); //find int y = find(v); //find if (x != y) { //union disjoint[x] = y; } | cs |
* 프림 알고리즘
1. 가중치가 낮은 간선을 선택한다.
2. 선택한 간선과 인접한 간선 중에서, 사이클을 생성하지 않는 간선 중에서 가중치가 작은 간선을 선택한다. (현재 간선의 가중치를 추가하면 다익스트라)
3. 위 과정을 반복하여 n-1개의 간선을 선택한다.
위 과정을 거치기 때문에 간선을 선택할 때마다 트리의 형태가 유지된다. (보통 우선순위큐를 이용하여 BFS로 구현한다.)
프림 알고리즘은 다익스트라(Dijkstra) 개념과 같이 이해하는게 편리하다.
cf) 프림 알고리즘 : MST를 만들 때 사용하는 알고리즘으로 BFS처럼 선마다 최소 가중치를 찾아 연결하는 방법
다익스트라 알고리즘 : 시작 정점 x에서 도착 정점 y까지 최단거리로 이동하는 방식
1 2 3 4 5 | // 프림 알고리즘 => 연결된 간선들 중 최소 가중치만 구한다. pq.add(new Edge(e.v, edge[e.v].get(i).v, edge[e.v].get(i).w)); // 다익스트라 알고리즘 => 현재 가중치를 계속 더해야 한다. pq.add(new Edge(e.v, edge[e.v].get(i).v, edge[e.v].get(i).w + e.w)); | cs |
'∙Algorithm Tech' 카테고리의 다른 글
| [Algorithm Tech] Segment Tree(세그먼트 트리) (0) | 2019.01.22 |
|---|---|
| [Algorithm Tech] 최단 경로 알고리즘 (0) | 2019.01.16 |
| [Algorithm Tech] Scanner vs BufferedReader (0) | 2019.01.10 |
| [Algorithm Tech] Dynamic Programming(동적 계획법) (0) | 2019.01.09 |