From a3e12953f34198004a960473538d9ed28be387dc Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 6 Oct 2016 19:38:51 +0200 Subject: Replacing Kruskal code to be compatible with union find implementation. --- graph/kruskal.cpp | 24 +++++++++--------------- 1 file changed, 9 insertions(+), 15 deletions(-) (limited to 'graph') diff --git a/graph/kruskal.cpp b/graph/kruskal.cpp index 124c8bb..a955632 100644 --- a/graph/kruskal.cpp +++ b/graph/kruskal.cpp @@ -1,15 +1,9 @@ -//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 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); -} +// Union-Find Implementierung von oben. Laufzeit: O(n*log(n)) +sort(edges.begin(), edges.end()); +vector mst; int cost = 0; +for (auto &e : edges) { + if (findSet(e.from) != findSet(e.to)) { + unionSets(e.from, e.to); + mst.push_back(ii(e.from, e.to)); + cost += e.cost; +}} -- cgit v1.2.3