kruskal algorithm [c++]

ㅇ 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결 하는 알고리즘

  -> 최소 비용 신장트리를 만들기 위함 ex) 여러 개의 도시들을 연결 하고자 할 때 비용을 최소한으로 하기 위해 사용

 

- 거리(cost)가 짧은 순서대로 그래프에 포함 시키면 됨

- 모든 노드를 최소비용으로 연결만 시키면 되기에 모든 간선 정보를 오름차순으로 정렬 한 뒤에 비용이 적은 간선부터

그래프에 포함

- 최소 비용 신장트리에서는 사이클이 발생하면 안 됨

 

 

1. 정렬된 순서에 맞게 그래프에 포함

2. 포함시키기 전에 사이클 테이블 확인

3. 사이클을 형성하는 경우 간선을 그래프에 포함시키지 않음

 

★ 사이클이 발생하는지 여부는 Union-Find 알고리즘을 사용

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// union-find
int findParent(int parent[], int x) {
if (parent[x] == x) return x; // 부모가 자신일 경우
return findParent(parent, parent[x]);
}

void unionParent(int parent[], int a, int b) {
a = findParent(parent, a);
b = findParent(parent, b);
if (a < b) parent[b] = a;   // a가 부모일 경우
else parent[a] = b;
}

 

class Edge {
public :
int node[2]; // 연결된 두 개 노드
int cost;

Edge(int a, int b, int cost) { // 생성자
this->node[0] = a;
this->node[1] = b;
this->cost = cost;
}

bool operator <(Edge& edge) { // 정렬기준
return this->cost < edge.cost;
}

};

 

 

int main() {

const int n = 7; // 정점의 개수
const 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, 25));
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()); // cost 오름차순 정렬(operator)

int parent[n+1];
for (int i = 1; i < n+1; i++) { // 각 정점의 위치 저장
parent[i] = i;
}

int sum = 0;
for (int i = 0; i < v.size(); i++) {
// 사이클이 발생하지 않는 경우 그래프에 포함
if (findParent(parent, v[i].node[0]) != findParent(parent, v[i].node[1])) {
sum += v[i].cost;
unionParent(parent, v[i].node[0], v[i].node[1]);
}
}

cout << sum;

/* 정렬 출력테스트 
for (auto iter = v.begin(); iter != v.end(); iter++) {
cout << iter->getCost() << " ";
}
*/
return 0;
}