크루스칼 알고리즘(Kruskal's algorithm)

목차

개요 최소 스패닝 트리 크루스칼 알고리즘 크루스칼 알고리즘의 구현 문제

개요

크루스칼 알고리즘은 무향 연결 그래프가 주어질 때, 최소 스패닝 트리라고 부르는 서브 그래프를 찾는 알고리즘입니다. 크루스칼 알고리즘은 유니온 파인드 자료구조에 사용합니다.

최소 스패닝 트리(minimum spanning tree)

해당 그래프의 모든 정점을 포함하는 트리 형태의 서브 그래프를 뜨샇ㅂ니다. 왼쪽 그래프에서 스패닝 트리를 하나 찾아보면 오른쪽 트리가 나옵니다. 스패닝 트리는 여러개 있을 수 있습니다. 그런 스패닝 트리들 중에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 최소 스패닝 트리라고 부릅니다. 최소 스패닝 트리 중 하나를 찾음으로서 간선의 가중치의 합의 최솟값을 찾는 알고리즘입니다.

크루스칼 알고리즘

크루스칼 알고리즘은 그리디 알고리즘입니다. 이 알고리즘을 따라가면 최소 스패닝 트리를 구할 수 있습니다.  1. 모든 간선을 끊어 놓는다 2. 가중치 순으로 간선들을 정렬한다. (오름차순) 3. 정렬된 간선을 순서대로 선택한다. 4. 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결합니다.

크루스칼 알고리즘의 구현

1. 모든 간선을 끊어 놓는다. 2. 가중치 순으로 간선들을 정렬합니다. 3. 정렬된 간선을 순서대로 선택합니다. 4. 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결합니다.   유니온 파인드는 오이로그이보다 빠르므로 크루스칼의 최종 시간 복잡도는 이로그이가 됩니다. 이는 브^2임이 보장되는 평범한 그래프라면 오이러그브이라고 할 수 있습니다.

연습문제

https://www.acmicpc.net/problem/1922 a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있습니다. 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있다. 최소 스패닝 트리.

#include<stdio.h> #include<algorithm> #include<vector> #include<iostream> using namespace std; const int N = 100005; // 유니온 파인드 시작 struct union_find_tree { vector<int> parent; vector<int> height; vector<int> group_size; void init(int uf_n) { parent.clear(), height.clear(); group_size.clear(); for (int i = 0; i<uf_n; i++) { parent.push_back(i); height.push_back(0); group_size.push_back(1); } } int get_root(int now) { if (parent[now] == now) return now; return parent[now] = get_root(parent[now]); } bool same_set(int v1, int v2) { return get_root(v1) == get_root(v2); } void merge(int v1, int v2) { v1 = get_root(v1), v2 = get_root(v2); if (v1 == v2) return; if (height[v1] < height[v2]) swap(v1, v2); parent[v2] = v1; group_size[v1] += group_size[v2]; if (height[v1] == height[v2]) height[v1]++; } }uf; // 유니온 파인드 끝 struct edge { int v1, v2, cost; bool operator < (const edge& e1) const { return cost < e1.cost; } }; vector<edge> e; int kruskal(int kn) { uf.init(kn + 1); sort(e.begin(), e.end()); int ret = 0; // 간선 가중치의 합의 최솟값 for (auto now : e) { if (!uf.same_set(now.v1, now.v2)) { // 두 정점이 끊어져 있는가? ret += now.cost; // 가중치를 ret에 더함 uf.merge(now.v1, now.v2); // 두 정점 연결 } } return ret; } int main() { int n, m; cin >> n >> m; //scanf("%d %d", &n, &m); while (m--) { edge in; cin >> in.v1 >> in.v2 >> in.cost; //scanf("%d %d %d", &in.v1, &in.v2, &in.cost); e.push_back(in); } cout << kruskal(n) << endl; // printf("%d", kruskal(n)); return 0; }

- 유니온 파인트 구조체를 그대로 사용합니다 (합병, 같은 그룹인지 확인) - 간선을 의미하는 구조체를 사용합니다. 여기에는 변수가 연결되는 정점 v1, v2, 그리고 비용 cost 입니다. - 그리고 구조체 안에 소팅하기 위한 operator < 가 들어갑니다.  - 그리고 엣지 e1 을 받아서 이것을 오름차순으로 정렬을 해주면 됩니다. - 벡터 에지 이를 받습니다. - 크루스칼 함수를 할때 동일하게 정점의 갯수를 받습니다.    그리고 유니온 파인트 구조를 초기화 합니다.    그리고 오름차순으로 순서를 정렬합니다.    그리고 간선 가중치의 합의 최솟값을 저장하는 ret 변수를 선언하고 초기화 합니다.    이제 for 문을 돌립니다. 아까 정렬 된 e를 중심으로 돌리는데요.    if 문을 사용해서 두 정점이 끊어져 있는지 확인을 합니다.    끊어져 있다면 ret+= 를 하고. 두 정점을 연결합니다. 이렇게 auto now : e 를 해서    모든 e 간선 정보를 처리해줍니다.