#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); } Show 크루스칼 알고리즘 (Kruskal Algorithm)신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는
그러면 신장 트리란 뭘까?
최소 신장 트리(Minimum Spanning Tree)는 또 뭐지?
왼쪽 그래프에서 최소 신장 트리를 찾으면 25를 제외한 2개의 간선(23+13)으로 이루어진 신장 트리가 즉, 신장 트리의 조건을 만족하면서 최소 비용으로 만들 수 있는 신장 트리가 크루스칼 알고리즘 동작 과정크루스칼 알고리즘의 구체적인 동작 과정은 아래와 같다.
아래 그림을 통해 이해해보자. [step 0] 그래프의 모든 간선 정보만 따로 빼내어 정렬을 수행한다. [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)크루스칼 알고리즘을 코드로 구현할 때, 앞서 배운
|