[그래프]Kruskal
Kruskal
어떤 그래프로부터 최소 신장 트리(Minimum Spanning Tree)를 도출해낼 때 사용하는 알고리즘
- 모든 간선을 원소로 갖는 집합 S를 만든다.
- S가 비어있지 않는 동안
- 가작 작은 가중치를 가진 간선 원소를 S에서 가져온다.
- 그 간선이 어떤 두 개의 서로 다른 tree를 연결한다면 두 tree를 연결하여 하나의 tree를 만든다.
- 그렇지 않다면 해당 간선을 버린다.
위의 프로세스는 Greedy Method 방식으로 진행이 된다.
Greedy Method
- 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것
- 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다.
- Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.
시간복잡도
O(ElogV)
예시 코드
두 트리를 연결하는 과정에서 union-find 알고리즘을 사용하면 쉽게 구현할 수 있다.
#define MAX_SIZE 100000
typedef struct Edge{
int from, to, cost;
}Edge;
bool cmp(const Edges &e1, const Edge &e2){
return e1.cost < e2.cost;
}
//index 0 is not used
int Set[MAX_SIZE + 1]; //소속한 집합의 루트값
vector<Edge> edges;
int find(int n){
if(Set[n] = n) return n;
return Set[n] = find(Set[n]); //path compression
}
void union(int a, int b){
int A(find(a));
int b(find(b));
if(A != B){
Set[A] = B;
}
}
int kruskal(int v, int e){
int mstCost = 0;
int selectCnt = 0;
for(int i = 1; i <= MAX_SIZE; i++) Set[i] = i;
sort(edges.begin(), edges.end(), cmp);
for(int i = 0; i < e; i++){
if(find(edges[i].from) != find(edges[i].to)){
mstCost += edges[i].cost;
selectCnt++;
union(edges[i].from, edges[i].to);
}
}
if(selectCnt == v - 1) return mstCost;
else return -1;
}
Author And Source
이 문제에 관하여([그래프]Kruskal), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rxjw95/그래프Kruskal저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)