アルゴリズム導論-第23章-最小生成ツリー:Kruskalアルゴリズム(ランク別集計、経路圧縮による非交差集合に基づく)C++実装
#include
#include
#include
using namespace std;
static char elements_index{ 'a' };
using P = pair;
using PP = pair;
struct Element {
char index{ elements_index++ };
int rank{ 0 };
Element* parent{ this };
};
Element* FIND_SET(Element* x) {
if (x != x->parent) {
x->parent = FIND_SET(x->parent);
}
return x->parent;
}
void LINK(Element* x, Element* y) {
if (x->rank > y->rank) {
y->parent = x;
}
else {
x->parent = y;
if (x->rank == y->rank) {
y->rank++;
}
}
}
void UNION(Element* x, Element* y) {
LINK(FIND_SET(x), FIND_SET(y));
}
vector
MST_KRUSKAL(vector& v, Element* E) {
vector
A{};
for (auto edge : v) {
if (FIND_SET(&E[edge.first.first - 'a']) != FIND_SET(&E[edge.first.second - 'a'])) {
A.push_back({ edge.first.first, edge.first.second });
UNION(&E[edge.first.first - 'a'], &E[edge.first.second - 'a']);
}
}
return A;
}
int main(int argc, char* argv[]) {
size_t vertex_size{};
cout << "please input the numbers of vertex :" << endl;
cin >> vertex_size;
vector v{};
char v0{};
char v1{};
int weight{};
cout << "please input the edge as : v0 v1 weight( end up with 0 0 0 )" << endl;
while (true) {
cout << "edge :" << endl;
cin >> v0 >> v1 >> weight;
if (v0 == '0' || v1 == '0' || weight == 0) {
break;
}
P p{ v0, v1 };
PP pp{ p, weight };
v.push_back(pp);
}
sort(v.begin(), v.end(), [](const PP& x, const PP& y){ return x.second < y.second; });
Element* E = new Element[vertex_size]{};
vector
result = MST_KRUSKAL(v, E);
cout << "MST has edges as follow :" << endl;
for (auto a : result) {
cout << a.first << " " << a.second << endl;
}
delete[]E;
return 0;
}