Categories
Code Dump

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[0] << " <filename>" << std::endl;
  } else {
    // which should be a filename...
    std::ifstream file(argv[1]);
    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));
    }
  }
}

Leave a Reply

Your email address will not be published. Required fields are marked *