Categories

# Kruskals algorithm in C++

This is a faster version of the standard algorithm for finding a minimum spanning tree using a Union-Find datastructure.

``````#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using std::vector;

// A Branching object is a Union-Find-Structure with elements
// of type Branching::node (unsigned int).
// Union and Find are as in the lecture, but there is no MakeSet
// method as we know in advance how many elements we will need.
class Branching {
public:
using node = unsigned int;
// Create a Branching of size n.
Branching(unsigned int n) {
size = n;
rank = vector<node>(n,0); // Initially ranks are 0
parent = vector<node>(n,0);
for(node i = 0; i < n; ++i) {
parent[i] = i; // Initially each element is its own parent.
}
}

// Find with path-compression
node Find(node x) {
if(x != parent[x]) {
parent[x] = Find(parent[x]);
}
return parent[x];
}

// Union as in lecture
void Union(node x, node y) {
node x_bar = Find(x);
node y_bar = Find(y);
if(rank[x_bar] > rank[y_bar]) {
parent[y_bar] = x_bar;
} else {
parent[x_bar] = y_bar;
if(rank[x_bar] == rank[y_bar]) {
++rank[y_bar];
}
}
}
private:
unsigned int size;
vector<node> parent;
vector<node> rank;
};

struct edge {
Branching::node from; // from < 2^32
Branching::node to;   // to   < 2^32
long long cost;       // abs(cost) < 2^32
};

// Kruskals algorithm
vector<edge> kruskal(unsigned int n, vector<edge>& edges) {
// Lambda functions were introduced in C++11,
// enable -std=c++11 if this fails to compile.
std::sort(edges.begin(), edges.end(), [](edge e1, edge e2) {
return e1.cost < e2.cost;
});
Branching nodes(n);
vector<edge> mst(0);
for(auto e : edges) {
// We identify connected components in mst with components
// in the Branching structure.
// If the edge connects two disjoint components...
if(nodes.Find(e.from) != nodes.Find(e.to)) {
// add the edge to mst and union them in nodes.
nodes.Union(e.from, e.to);
mst.push_back(e);
}
}
return mst;
}

// Output the result of Kruskals algorithm.
void output(unsigned int n, vector<edge> mst) {
if(mst.size() != n - 1) {
// A minimum spanning tree has exactly n-1 edges
// if mst has less, the graph can't be connected.
std::cout << "Der Graph ist nicht zusammenhängend!" << std::endl;
} else {
long long sum = 0;
for(auto e : mst) {
sum += e.cost; // Sum the costs.
}
std::cout << "Es gibt einen MST mit Gewicht " << sum << "." << std::endl;
for(auto e : mst) {
// Give back each edge in the order in which they were added to mst.
std::cout << e.from << " -> " << e.to << " : "  << e.cost << std::endl;
}
}
}

int main(int argc, char *argv[]) {
if(argc != 2) {
// We expect exactly one argument...
std::cout << "Aufruf: " << argv << " <filename>" << std::endl;
} else {
// which should be a filename...
std::ifstream file(argv);
unsigned int n = 0;
vector<edge> edges(0);
if(!file.is_open()) {
// of a non-busy file.
std::cout << "Konnte Datei nicht öffnen." << std::endl;
} else {
file >> n; // First we read the number of nodes...
Branching::node a, b; long long c;
while(file >> a >> b >> c) {
// and then the edges...
edges.push_back(edge {a,b,c});
}
// and then we compute the MST.
output(n, kruskal(n, edges));
}
}
}``````