Adding Kruskal algorithm

1 files changed, 18 insertions, 0 deletions

diff --git a/graph/kruskal.cpp b/graph/kruskal.cpp
new file mode 100644
index 0000000..4703c45
--- /dev/null
+++ b/graph/kruskal.cpp
@@ -0,0 +1,18 @@
+typedef pair<int,int> ii;
+typedef vector<pair<int,ii>> graph;
+
+//Takes a Graph g (EdgeList!!!) with N nodes and computes the MST and Cost of it. Runtime: O(|E|*log(|E|))
+//Requires UnionFind-Datastructure!!!
+pair<graph,int> buildMST(int N, graph& g) {
+  UnionFind uf(N);
+  graph mst; int mst_cost = 0; int M = g.size();
+  sort(g.begin(),g.end());
+  for(int i = 0; i < M; i++) {
+    int u = g[i].second.first, v = g[i].second.second;
+    if(uf.findSet(u) != uf.findSet(v)) {
+      mst.push_back(g[i]); mst_cost += g[i].first;
+      uf.unionSets(u,v);
+    }
+  }
+  return make_pair(mst,mst_cost);
+}
\ No newline at end of file