From 0c9ef64dbe211408f7a4ad26f3d9fab5fa941eba Mon Sep 17 00:00:00 2001
From: kittobi92 <Tobias.Heuer@gmx.net>
Date: Fri, 4 Dec 2015 12:30:51 +0100
Subject: Adding Kruskal algorithm

---
 graph/graph.tex   |  3 +++
 graph/kruskal.cpp | 18 ++++++++++++++++++
 2 files changed, 21 insertions(+)
 create mode 100644 graph/kruskal.cpp

(limited to 'graph')

diff --git a/graph/graph.tex b/graph/graph.tex
index 7a85337..f23db82 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -13,6 +13,9 @@ Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so
 Für jeden Kreis $K$ im Graphen gilt:
 Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
 
+\subsubsection{Kruskal}
+\lstinputlisting{graph/kruskal.cpp}
+
 \subsection{Kürzeste Wege}
 
 \subsubsection{Algorithmus von \textsc{Dijkstra}}
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
-- 
cgit v1.2.3