#include <iostream> #include <algorithm> #include <vector> using namespace std; // 부모 노드를 가져옴 int getParent(int set[], int x) { if(set[x] == x) return x; return set[x] = getParent(set, set[x]); } // 부모 노드를 병합 void unionParent(int set[], int a, int b) { a = getParent(set, a); b = getParent(set, b); // 더 숫자가 작은 부모로 병합 if(a < b) set[b] = a; else set[a] = b; } // 같은 부모를 가지는지 확인 int find(int set[], int a, int b) { a = getParent(set, a); b = getParent(set, b); if(a == b) return 1; else return 0; } // 간선 클래스 선언 class Edge { public: int node[2]; int distance; Edge(int a, int b, int distance) { this->node[0] = a; this->node[1] = b; this->distance = distance; } bool operator <(Edge &edge) { return this->distance < edge.distance; } }; int main(void) { int n = 7; int m = 11; vector<Edge> v; v.push_back(Edge(1, 7, 12)); v.push_back(Edge(1, 4, 28)); v.push_back(Edge(1, 2, 67)); v.push_back(Edge(1, 5, 17)); v.push_back(Edge(2, 4, 24)); v.push_back(Edge(2, 5, 62)); v.push_back(Edge(3, 5, 20)); v.push_back(Edge(3, 6, 37)); v.push_back(Edge(4, 7, 13)); v.push_back(Edge(5, 6, 45)); v.push_back(Edge(5, 7, 73)); // 간선의 비용으로 오름차순 정렬 sort(v.begin(), v.end()); // 각 정점이 포함된 그래프가 어디인지 저장 int set[n]; for(int i = 0; i < n; i++) { set[i] = i; } // 거리의 합을 0으로 초기화 int sum = 0; for(int i = 0; i < v.size(); i++) { // 동일한 부모를 가르키지 않는 경우, 즉 사이클이 발생하지 않을 때만 선택 if(!find(set, v[i].node[0] - 1, v[i].node[1] - 1)) { sum += v[i].distance; unionParent(set, v[i].node[0] - 1, v[i].node[1] - 1); } } printf("%d\n", sum); }
크루스칼 알고리즘 (Kruskal Algorithm)
신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘이 있다.
크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다.
크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이다.
그리디 알고리즘으로 분류된다.
그러면 신장 트리란 뭘까?
- 신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
--> 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 함.
최소 신장 트리(Minimum Spanning Tree)는 또 뭐지?
크루스칼 알고리즘은 신장 트리 중에서도 최소한의 비용으로 만들 수 있는 최소 신장 트리를 찾는 알고리즘이다. 아래 그림을 통해 최소 신장 트리를 알아보자.
왼쪽 그래프에서 최소 신장 트리를 찾으면 25를 제외한 2개의 간선(23+13)으로 이루어진 신장 트리가 최소 신장 트리가 된다!
즉, 신장 트리의 조건을 만족하면서 최소 비용으로 만들 수 있는 신장 트리가 최소 신장 트리가 된다.
크루스칼 알고리즘 동작 과정
크루스칼 알고리즘의 구체적인 동작 과정은 아래와 같다.
- 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
① 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
② 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. (X)- 모든 간선에 대하여 2번의 과정을 반복한다.
아래 그림을 통해 이해해보자.
[step 0] 그래프의 모든 간선 정보만 따로 빼내어 정렬을 수행한다.
(원래는 비용을 기준으로 오름차순 정렬을 한다.--> 최소한의 비용으로 MST를 만들기 위해서이다.)
[step 1] 비용이 가장 최소인 (3, 4)를 선택한 후 3번 노드와 4번 노드에 대하여 union 함수를 수행한다.
[step 2] 방문하지 않은 간선들 중에서 가장 최소인 (4, 7)을 선택하여 처리한다.
[step 3] 방문하지 않은 간선들 중에서 가장 최소인 (4, 6)을 선택하여 처리한다.
[step 4] 방문하지 않은 간선들 중에서 가장 최소인 (6, 7)을 선택하여 처리한다. 하지만 (6, 7)을 방문할 경우(연결할 경우(=union() 함수)) 사이클이 발생하므로 (6, 7) 간선을 연결하지 않는다.
[step 5] 방문하지 않은 간선들 중에서 가장 최소인 (1, 2)을 선택하여 처리한다.
[step 6] 방문하지 않은 간선들 중에서 가장 최소인 (2, 6)을 선택하여 처리한다.
[step 7] 방문하지 않은 간선들 중에서 가장 최소인 (2, 3)을 선택하여 처리한다. 하지만, (2, 3)을 연결할 경우에도 사이클이 발생하므로 연결하지 않는다.
[step 8] 방문하지 않은 간선들 중에서 가장 최소인 (5, 6)을 선택하여 처리한다.
[step 9] 방문하지 않은 간선들 중에서 가장 최소인 (1, 5)을 선택하여 처리한다. 마찬가지로 (1, 5)를 연결하면 사이클이 발생하므로 연결하지 않는다.
[최종 결과]
또한, 최소 신장 트리에 포함되어 있는 간선의 비용만 모두 더하면, 그 값이 최종 비용에 해당한다. 위 예시에서는 총 비용이 159이다.
사진 출처 : 링크
크루스칼 알고리즘 코드 (Python)
크루스칼 알고리즘을 코드로 구현할 때, 앞서 배운 union-find 알고리즘을 이용하여 구현한다!
- 시간 복잡도는 O(ElogE)
크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가진다. 왜냐하면 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업이며, E개의 데이터를 정렬했을 때의 시간 복잡도는 O(ElogE)이기 때문이다. --> (Python에서 .sort()함수는 퀵 정렬을 기본으로 하며 퀵 정렬의 시간 복잡도는 O(NlogN)이다!)
크루스칼 내부에서 사용되는 서로소 집합 알고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도보다 작으므로 무시한다.